Data structures worksheet with answers

Which data structure is used to perform a level-order traversal of a tree?

1. AQueue
2. BPriority queue
3. CHash table
4. DStack

What is a deque (double-ended queue)?

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

What is the name of the queue operation that removes the element at the front?

1. ADequeue
2. BEnqueue
3. CPush
4. DInsert

AVL trees and red-black trees guarantee:

1. AThat keys are stored in insertion order
2. BO(log n) height through rebalancing
3. CThat no node has two children
4. DConstant-time search in every case

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. Ai/2 and i/2 + 1
2. Bi + 1 and i + 2
3. C2i + 1 and 2i + 2
4. D2i and 2i + 1

What is the value of the postfix expression 3 4 + 2 * ?

1. A24
2. B14
3. C10
4. D11

Kahn's algorithm for topological sorting repeatedly removes vertices with in-degree 0. Which structure holds those vertices?

1. AAn adjacency matrix recording which vertices have already been removed
2. BA max-heap ordered by out-degree
3. CA queue (or any collection) of vertices whose in-degree is 0
4. DA stack of all visited edges

Which statement about heapsort is correct?

1. AIt runs in O(n) time on any input
2. BIt is stable and needs O(n) extra memory
3. CIt needs a binary search tree as extra storage, so it uses O(n) extra memory
4. DIt sorts in place in O(n log n) worst-case time but is not stable