Data structures worksheet with answers

In an undirected graph, what is the degree of a vertex?

1. AIts position in the adjacency list
2. BThe length of the longest path from it
3. CThe number of edges connected to it
4. DThe number of vertices in the graph

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

1. ARemoving the head element
2. BAccessing the element at index i
3. CInserting at the head
4. DReading the first element

Which data structure is most suitable for the "undo" feature in a text editor?

1. AStack
2. BHash set
3. CGraph
4. DQueue

How is a new element inserted into a binary heap?

1. APlace it at the root and sift it down
2. BRebuild the whole heap from scratch
3. CPlace it at the end of the array and sift it up while it violates the heap property
4. DInsert it at its sorted position by shifting all of the larger elements one place right

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A4 5 2 3 1
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D1 2 4 5 3

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most n / 2
2. BThe height is at most 2 log₂(n + 1)
3. CThe height is at most log₂ n + 1
4. DThe height is exactly log₂ n

Which statement about heapsort is correct?

1. AIt runs in O(n) time on any input
2. BIt needs a binary search tree as extra storage, so it uses O(n) extra memory
3. CIt sorts in place in O(n log n) worst-case time but is not stable
4. DIt is stable and needs O(n) extra memory