Data structures worksheet with answers

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

1. AGraph
2. BQueue
3. CStack
4. DHash set

The height of a tree is commonly defined as:

1. AThe number of edges on the longest path from the root to a leaf
2. BThe number of children of the root
3. CThe total number of nodes in the tree, counting the root and every leaf
4. DThe number of leaves in the tree

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

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

How do you find the minimum key in a binary search tree?

1. ALook at the root only
2. BFollow left children from the root until there is no left child
3. CVisit every leaf and compare them
4. DFollow right children from the root until there is no right child

A node in a binary search tree has a right subtree. Where is its in-order successor?

1. AThe leftmost node of its right subtree
2. BIts parent, always
3. CThe rightmost node of its left subtree
4. DIts right child, always

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. A1
2. Bn (it becomes a linked list)
3. Clog₂ n
4. D√n

A segment tree is typically used to:

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

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

1. AChecking whether an edge's two endpoints are already connected
2. BChoosing the starting vertex
3. CSorting the edges by weight
4. DStoring each vertex's current distance from the source during the search