Data structures worksheet with answers

In a tree, what is a leaf?

1. AA node with no children
2. BA node with no parent
3. CThe node with the largest value
4. DA node with exactly one child

In a tree, what are sibling nodes?

1. ANodes that have no children
2. BA node and its parent
3. CNodes at the same depth in different subtrees
4. DNodes that share the same parent

What does each node in a doubly linked list contain?

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

How is a new element inserted into a binary heap?

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

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

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

AVL trees and red-black trees guarantee:

1. AThat no node has two children
2. BConstant-time search in every case
3. CThat keys are stored in insertion order
4. DO(log n) height through rebalancing

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

What is the running time of breadth-first search on a graph with V vertices stored as an adjacency matrix?

1. AO(V + E)
2. BO(V²)
3. CO(E log V)
4. DO(V)