Data structures worksheet with answers

What is a deque (double-ended queue)?

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

What does each node in a doubly linked list contain?

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

What is the main difference between a static array and a dynamic array?

1. AA static array allows slower index access
2. BA dynamic array stores its elements in linked nodes so it can grow one at a time
3. CA static array can only store numbers
4. DA dynamic array can grow by moving to a larger block of memory

Why can a binary heap be stored in an array without any pointers?

1. AArrays automatically keep the keys in sorted order, so no pointers are needed
2. BHeaps never contain more than 100 elements
3. CAll keys in a heap are equal
4. DIt is a complete binary tree, so positions follow simple index formulas

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

1. A0.5
2. B2
3. C1
4. DThere is no maximum

A circular buffer (ring buffer) is commonly used to implement:

1. AA hash function
2. BA graph traversal
3. CA fixed-size queue
4. DA binary search tree

What are the time and extra space costs of reversing a singly linked list in place?

1. AO(n) time and O(n) extra space
2. BO(n) time and O(1) extra space
3. CO(n log n) time and O(1) extra space
4. DO(1) time and O(1) extra space

The union-find (disjoint set) structure with union by rank and path compression has an amortised cost per operation of:

1. AO(log n) exactly
2. BO(n²)
3. CO(n)
4. DO(α(n)), the inverse Ackermann function, which is practically constant