Data structures worksheet with answers

A graph consists of:

1. ARows and columns
2. BKeys and hashes only
3. COnly a root and leaves
4. DVertices (nodes) connected by edges

What does the peek (or top) operation on a stack do?

1. AReturns the bottom element of the stack
2. BRemoves the top element and returns it
3. CRemoves all elements from the stack
4. DReturns the top element without removing it

Which data structure is used to perform a level-order traversal of a tree?

1. AQueue
2. BHash table
3. CPriority queue
4. DStack

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

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

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. AArray elements are contiguous, so they make good use of the CPU cache
2. BArrays use fewer instructions to compare values
3. CLinked lists always store elements on disk
4. DArray traversal is O(1) in total, while linked list traversal is O(n)

What is the cost of inserting an element in the middle of an array of n elements?

1. AO(n²), because each element moves n times
2. BO(n), because later elements must shift
3. CO(log n), because of binary search
4. DO(1), because the index is known

A segment tree is typically used to:

1. ASort strings alphabetically by storing each prefix in a separate tree node
2. BAnswer range queries (such as range sums) and updates in O(log n)
3. CStore a graph's edges
4. DImplement a stack

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A40
2. B60
3. C80
4. D70