Data structures worksheet with answers

What is the defining feature of a set as an abstract data type?

1. AIt allows access only at one end
2. BIt stores key-value pairs
3. CIt stores elements in sorted order
4. DIt stores elements without duplicates

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

1. AFinding the length of a fixed array
2. BReading the last element by index
3. CAccessing the 5th element
4. DInserting at the beginning

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

In a hash table using open addressing, what is the maximum possible load factor?

1. AThere is no maximum
2. B0.5
3. C2
4. D1

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

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

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index ⌊(i − 1) / 2⌋
2. BAt index 2i + 1
3. CAt index i − 1
4. DAt index ⌊i / 2⌋ + 1

For a hash table to work correctly, which rule must hash and equality follow?

1. AHash values must be prime numbers
2. BEqual keys must have equal hash values
3. CDifferent keys must have different hash values
4. DEqual hash values imply equal keys

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

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