Data structures worksheet with answers

What does a map (dictionary) store?

1. AOnly values in insertion order
2. BKey-value pairs with unique keys
3. CPairs of equal keys
4. DValues sorted by size

Which operation is slow in an array but fast at the head of a linked list?

1. AInserting at the beginning
2. BFinding the length of a fixed array
3. CAccessing the 5th element
4. DReading the last element by index

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

1. AEnqueue
2. BDequeue
3. CInsert
4. DPush

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. A1
2. B√n
3. Clog₂ n
4. Dn (it becomes a linked list)

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

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

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AAn unsorted linked list
2. BA hash table
3. CA balanced binary search tree
4. DA stack

The keys 5, 3, 8, 1 are inserted in this order into an empty array-based binary min-heap. What is the final array?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[3, 1, 8, 5]
4. D[1, 3, 8, 5]

Why might a server choose its hash function at random from a universal family?

1. ATo make it very unlikely that an attacker can pick many keys that all collide
2. BTo guarantee that no two keys can ever collide, whatever keys an attacker sends
3. CTo make the hash table sorted
4. DTo remove the need to resize the table