Data structures worksheet with answers

What is the root of a tree?

1. AThe top node with no parent
2. BA node with no children
3. CAny node in the middle
4. DThe node with the largest value

Which operation is O(1) for an array but O(n) for a singly linked list?

1. AInserting at the head
2. BReading the first element
3. CRemoving the head element
4. DAccessing the element at index i

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

1. AQueue
2. BStack
3. CHash table
4. DPriority queue

A trie (prefix tree) is especially efficient for:

1. AStoring matrices
2. BSorting numbers
3. CPrefix searches such as autocomplete
4. DFinding shortest paths

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. BAt index 2i + 1
3. CAt index ⌊(i − 1) / 2⌋
4. DAt index ⌊i / 2⌋ + 1

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(1), because the index is known
3. CO(n), because later elements must shift
4. DO(log n), because of binary search

In Kruskal's minimum spanning tree algorithm, what is the union-find structure used for?

1. AChoosing the starting vertex
2. BSorting the edges by weight
3. CStoring each vertex's current distance from the source during the search
4. DChecking whether an edge's two endpoints are already connected

An AVL node is unbalanced because its left child's right subtree became too tall (left-right case). Which fix is applied?

1. AA right rotation at the left child, then a left rotation at the node
2. BA single left rotation at the node
3. CA single right rotation at the node
4. DA left rotation at the left child, then a right rotation at the node