Data structures worksheet with answers

What does each node in a doubly linked list contain?

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

What is the max-heap property?

1. AThe keys are sorted from left to right
2. BEvery parent's key is greater than or equal to its children's keys
3. CEvery left child's key is greater than or equal to its right sibling's key
4. DAll leaves contain the maximum key

Which operation is slow in an array but fast at the head of a linked list?

1. AAccessing the 5th element
2. BFinding the length of a fixed array
3. CReading the last element by index
4. DInserting at the beginning

Which data structure does a running program use to keep track of active function calls and their local variables?

1. AThe heap memory queue
2. BA hash table of functions
3. CThe call stack
4. DA binary search tree of frames

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

How long does it take to check whether the edge (u, v) exists using an adjacency matrix?

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

Kahn's algorithm for topological sorting repeatedly removes vertices with in-degree 0. Which structure holds those vertices?

1. AA stack of all visited edges
2. BA queue (or any collection) of vertices whose in-degree is 0
3. CA max-heap ordered by out-degree
4. DAn adjacency matrix recording which vertices have already been removed

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

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