Data structures worksheet with answers

How many edges does a tree with n nodes have?

1. An − 1
2. Bn + 1
3. Cn
4. D2n

Which structure is typically used to implement a priority queue?

1. AA heap
2. BA stack
3. CA singly linked list without order
4. DA string

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

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

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the postorder traversal?

1. A5 4 3 2 1
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

How does extract-min work in a binary min-heap?

1. ARemove the root and shift all elements one place left
2. BRemove the last element of the array
3. CMove the last element to the root and sift it down
4. DSearch all leaves for the new minimum

A circular buffer (ring buffer) is commonly used to implement:

1. AA graph traversal
2. BA binary search tree
3. CA fixed-size queue
4. DA hash function

What does a splay tree do after each access?

1. AMoves the accessed node to a leaf
2. BRebuilds the whole tree in balanced form
3. CRecolours the nodes on the search path
4. DRotates the accessed node up to the root

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

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