Data structures worksheet with answers

In which order does a postorder traversal of a binary tree visit nodes?

1. ARight subtree, then node, then left subtree
2. BLeft subtree, then right subtree, then node
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then node, then right subtree

The depth of a node in a tree is:

1. AThe number of edges from that node to the deepest leaf
2. BThe number of edges from the root to that node
3. CThe number of children of that node
4. DThe number of nodes in its subtree

What does a map (dictionary) store?

1. AValues sorted by size
2. BPairs of equal keys
3. COnly values in insertion order
4. DKey-value pairs with unique keys

How is a new element inserted into a binary heap?

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

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

1. AA single sorted array of vertices
2. BAdjacency list
3. CA binary heap of edges
4. DAdjacency matrix

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(1)

How long does it take to search for an arbitrary key in a binary min-heap of n elements?

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

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. BStore the front and rear in the same variable
3. CAlways clear the buffer whenever front equals rear, so the state is empty
4. DMake the buffer size a power of two