Fundamentals of Data Structures Flashcards
Define ‘static data structure’.
A collection of data in memory that has a fixed storage size determined at compile-time.
Define ‘dynamic data structure’.
A collection of data in memory that has the flexibility to grow or shrink at run-time.
Explain two differences between static and dynamic data structures.
Static data structures may waste memory if the number of data items stored is less than the allocated storage space. However, dynamic data structures only take up the amount of storage space required for the actual data.
Static data structures store data in contiguous memory locations, dynamic data structures do not.
Which type of data structure requires a pointer.
Dynamic data structures require memory to store a pointer to the next item which static data structures do not require.
What are the three types of queues?
Priority
Circular
Linear
What type of data structure is a stack
LIFO
Last item in is the first item out
What is an abstract data type?
A system described in terms of its behaviour, without regard to its implementation.
What type of data structure is a queue
FIFO
First item in is the first item out
How many pointers does a queue require?
Two pointers
One for the front of the queue, and another for the back.
How many pointers does a stack require?
One pointer
It points to the top of the stack.
What operations are implemented for a stack?
Push (add item)
Pop (remove item)
Peek (view item)
Describe the algorithm for insertion into a stack.
Check if stack is full.
If the stack is full report an error and stop.
Increment stack pointer.
Insert new data item into location pointed to by stack pointer and stop.
Do the opposite for deletion (empty, decrement). To peek, copy data item from location pointed to by stack pointer.
Describe the algorithm for insertion into a queue.
Check if queue is full.
If the queue is full report an error and stop.
Increment back pointer.
Insert new data item into location pointed to by back pointer and stop.
Describe the algorithm for deletion/reading from a queue.
Check if queue is empty.
If the queue is empty report an error and stop.
Copy data item from location pointed to by front pointer. (reading only)
Increment front pointer and stop. (deletion only)
What are the components of a graph
Vertex
Edge
State two advantages of using an adjacency matrix.
Very quick and easy to work with
Adding new edges / checking for presence of edges is simple and quick using a 2D array.
State two disadvantages of using an adjacency matrix.
If the graph is sparse (lots of nodes but very few edges), it results in lots of wasted memory.
Implementing it as a 2D array can make it difficult to add / delete nodes.
What is the best way to store a sparse graph?
Adjacency list, they are very space efficient.
State the components of a tree.
Root node
Children nodes
Branches
Leaf nodes
What are the properties of a binary tree.
No more than two children per node.
Each node consists of data, a left pointer, and a right pointer.
What is an array?
Stores data of the same type in contiguous memory locations.
What is a hash table?
A data structure that maps keys to values using a hash function.
It is used to insert, look up, and remove key-value pairs quickly.
What is a collision when working with hash tables?
Collisions happen when two or more keys point to the same array index.
What does a good hash function do?
Keep collisions to a minimum.
How are collisions handled in a hash table? Describe two methods
Open addressing, look for the next available empty space in the table. This may cause clustering.
Separate chaining, a linked list of objects that hash to each slot in the hash table is present. Two keys are included in the linked list if they hash to the same slot. This is good for handling several collisions.
Describe the algorithm for adding a value to a hash table.
Feed in key to hash function.
Go directly to array index.
If location is empty insert the value.
Otherwise, follow linked list in sequence until free space is found.
Insert value.
Describe the implementation of a dictionary.
Stores groups of objects using key value pairs. Each key has a single value associated with it, which is returned when the key is supplied.
State a use of dictionaries
Dictionary encoding
How can a vector with three components, drawn from the set of real numbers be represented?
3-vector over R
R^3
where R is the symbol for set of real numbers.
How can a vector be represented?
As a list
As a 1D array
As a dictionary (which can be considered to be representing it as a function)
Graphically (as an arrow)
Using set notation
a = (5, 13) b = (29, 5)
a + b = ?
(34, 18)
multiplying a = (5, 13) by 2 will give the vector…
(10, 26)
what is the expression for the convex combination of vectors?
(a * u) + (b * v)
OR
au + bv
a is alpha, and b is beta
a + b = 1
a and b are greater than or equal to zero
u and v are vectors
a = (2, -1) b = (-7, -4)
What is the dot product of a and b?
a.b = (2 * -7) + (-1 * -4) = -14 + 4 = -10
a.b = -10
What is the purpose of finding the dot product of two vectors?
Can be used to find the angle between them.
What is the formula for finding the angle between two vectors?
cos(theta) = a.b / |a|.|b|
