Data structures worksheet with answers

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 number of edges on the longest path from the root to a leaf
3. CThe number of children of the root
4. DThe total number of nodes in the tree, counting the root and every leaf

Which operation is O(1) for an array but O(n) for a singly linked list?

1. AAccessing the element at index i
2. BInserting at the head
3. CRemoving the head element
4. DReading the first element

A trie (prefix tree) is especially efficient for:

1. APrefix searches such as autocomplete
2. BStoring matrices
3. CSorting numbers
4. DFinding shortest paths

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

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

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

A dynamic array doubles when full. Why do many implementations shrink it only when it is one quarter full, not half full?

1. ATo keep the array sorted
2. BBecause halving at one half would lose elements
3. CTo avoid repeated resizing when pushes and pops alternate near the boundary
4. DBecause the memory allocator can only release memory in quarters of a block

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most n / 2
2. BThe height is exactly log₂ n
3. CThe height is at most 2 log₂(n + 1)
4. DThe height is at most log₂ n + 1