What is a static data structure?
A data structure that reserves a fixed amount of memory, specified by the programmer in advance of its use. They store data in consecutive memory locations and do not need to store memory pointers
What is a dynamic data structure?
Data structures that have no fixed size. The memory used grows and shrinks as items are added/removed. They do not store data in consecutive memory locations and require storage for memory pointers
Give two advantages of static data structures over dynamic data structures:
- Data is quicker to access directly, with minimal overhead
- No additional memory is needed to store all of the pointers
Give two advantages of dynamic data structures:
- There is no wasted memory
- There is no theoretical limit on the number of items that can be added
Is a queue FIFO or LIFO?
FIFO (First in first out)
Describe the four key operations of a queue:
- Enqueue - adds item to rear of the queue
- Dequeue - removes item and returns item from the front of the queue
- IsEmpty - checks if the queue is empty
- IsFull - checks is the queue is full
Describe the data structures and pointers used by a linear queue:
- Linear queues are implemented with arrays (or lists)
- They use a front and rear pointers to point to:
- front → the next item to dequeue
- rear → last item enqueued
Describe the disadvantages of linear queues if you
1. Don’t shuffle down the items
2. If you do
- There is a limit on the number of items that can be added and removed (maxSize)
- Implementing a linear queue where you “shuffle” the items down each time an item is dequeued is very processing intensive
What is the key difference between a circular queue and a linear queue?
- Circular queues virtually connect the end to the start of the array
- This overcomes the problem of reusing spaces in the array
What happens to the rear pointer when enqueuing an item to a circular queue?
rear ← (rear + 1) % maxSize
What is a priority queue? Describe how enqueuing works.
- A queue where each element in the queue has a priority
- When new elements are enqueued, they are inserted ahead of those of lower priority and behind elements of equal or greater priority
Name an algorithm that can be implemented with a priority queue
Dijkstra’s Algorithm
Is a graph static or dynamic?
Dynamic, they can grow and shrink in size
What is a graph?
Graphs are sets of vertices (nodes) and the edges (arcs) that connect them
What is a graph with a high ratio of edges to vertices called?
Dense
What is a graph with a low ratio of edges to vertices called?
Sparse
What is a weighted graph?
A graph that has weights (number values) on each edge
What is a connected graph?
A graph where there is a path between each pair of vertices
Suggest three things that graphs could be used to model
- Social networking: the nodes could be individual people. An edge could represent that two people are acquaintances.
- Transport networks: the nodes could be towns. An edge could represent that a train line connects two towns.
- The internet: the nodes could be routers. An edge could represent that two routers are connected.
- Flows: the nodes could be connections. An edge could represent a path that fluid/goods can take. The weights could represent current/maximum flow.
Give two ways to represent graphs:
Adjacency matrix and adjacency list
How do you represent no edge for a weighted graph in an adjacency matrix?
“-” or “∞” (can’t use zero)
How could an adjacency list be implemented if graph is:
1. weighted
2. unweighted?
- List of dictionaries if weighted
- List of lists if unweighted
State two advantages of adjacency lists:
- Adjacency lists are very space efficient, as no memory is needed to store the empty spaces
- It is easy to add / delete nodes
State a disadvantage of using an adjacency list:
Slow to query (e.g. to check the presence of an edge), as each item in the list must be searched sequentially until the desired edge is found
