Data structures worksheet with answers

What does a map (dictionary) store?

1. APairs of equal keys
2. BOnly values in insertion order
3. CKey-value pairs with unique keys
4. DValues sorted by size

What does each node in a doubly linked list contain?

1. ATwo copies of the data and one pointer
2. BData, a pointer to the next node and a pointer to the previous node
3. CData and two pointers, one to the next node and one to the node after that
4. DData and a pointer to the next node only

What is a deque (double-ended queue)?

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

What happens when a hash table rehashes after its load factor exceeds a threshold?

1. AThe oldest keys are deleted to make room
2. BThe existing keys are sorted in place
3. COnly the colliding keys are moved to a new overflow list at the end of the table
4. DA larger table is allocated and every key is inserted again

How long does a search for a word of length L take in a trie with a fixed alphabet?

1. AO(L), independent of how many words are stored
2. BO(n), where n is the number of words
3. CO(log n), where n is the number of words
4. DO(L × n)

An in-order traversal of a binary search tree visits the keys in:

1. AInsertion order
2. BDescending order always
3. CLevel order
4. DAscending sorted order

For each element of an array you want the next greater element to its right, in O(n) total time. Which structure helps?

1. AA stack that keeps elements waiting for their answer
2. BA binary search tree rebuilt for each element
3. CA hash table of all elements
4. DA queue that holds every pair of elements

How long does it take to search for an arbitrary key in a binary min-heap of n elements?

1. AO(log n)
2. BO(1)
3. CO(log log n)
4. DO(n)