Data structures worksheet with answers

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

1. AQueue
2. BGraph
3. CHash set
4. DStack

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

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

Which data structure works on the principle "last in, first out"?

1. AStack
2. BLinked list
3. CQueue
4. DHash table

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

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA FIFO queue
2. BA stack
3. CA set with no ordering
4. DA min-priority queue

An adjacency matrix for a graph with V vertices uses how much memory?

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

Which property must a red-black tree satisfy?

1. AEvery red node must have red children, so red nodes always form unbroken chains to the leaves
2. BEvery node must be red
3. CEvery path from a node to its descendant leaves has the same number of black nodes
4. DThe root must be red

In a circular buffer, front == rear can mean either empty or full. What is a common way to tell them apart?

1. AMake the buffer size a power of two
2. BKeep a separate element count, or always leave one slot unused
3. CAlways clear the buffer whenever front equals rear, so the state is empty
4. DStore the front and rear in the same variable