Data structures worksheet with answers

In an adjacency list representation of a graph, what is stored for each vertex?

1. AThe shortest path to every other vertex
2. BThe total number of edges in the graph
3. CA list of its neighbouring vertices
4. DA row of V Boolean values

What is a deque (double-ended queue)?

1. AA structure that allows insertion and removal at both ends
2. BA queue sorted by priority
3. CTwo separate queues sharing one array
4. DA queue that only allows removal at the back

The height of a tree is commonly defined as:

1. AThe number of leaves in the tree
2. BThe total number of nodes in the tree, counting the root and every leaf
3. CThe number of edges on the longest path from the root to a leaf
4. DThe number of children of the root

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA set with no ordering
2. BA min-priority queue
3. CA FIFO queue
4. DA stack

What is true of the adjacency matrix of an undirected graph?

1. AIts main diagonal always contains ones
2. BIt is always upper triangular
3. CIt is symmetric about the main diagonal
4. DEach row has exactly one 1

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. ALinked lists always store elements on disk
2. BArrays use fewer instructions to compare values
3. CArray elements are contiguous, so they make good use of the CPU cache
4. DArray traversal is O(1) in total, while linked list traversal is O(n)

The union-find (disjoint set) structure with union by rank and path compression has an amortised cost per operation of:

1. AO(n²)
2. BO(log n) exactly
3. CO(α(n)), the inverse Ackermann function, which is practically constant
4. DO(n)

Which structure lets you compute the maximum of every window of size k in an array in O(n) total?

1. AA deque holding indices in decreasing order of value
2. BA singly linked list of the window's elements
3. CA min-heap rebuilt for every window
4. DA sorted array updated by shifting