Data structures worksheet with answers

How are the elements of an array stored in memory?

1. AIn random locations chosen by a hash
2. BIn a tree of memory pages
3. CScattered, linked by pointers
4. DIn one contiguous block, one after another

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

1. ALeft subtree, then node, then right subtree
2. BLeft subtree, then right subtree, then node
3. CNode, then left subtree, then right subtree
4. DRight subtree, then node, then left subtree

In a tree, what are sibling nodes?

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

How does extract-min work in a binary min-heap?

1. ARemove the root and shift all elements one place left
2. BMove the last element to the root and sift it down
3. CRemove the last element of the array
4. DSearch all leaves for the new minimum

AVL trees and red-black trees guarantee:

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

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

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

What does a splay tree do after each access?

1. AMoves the accessed node to a leaf
2. BRebuilds the whole tree in balanced form
3. CRecolours the nodes on the search path
4. DRotates the accessed node up to the root

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

1. AStoring each vertex's current distance from the source during the search
2. BSorting the edges by weight
3. CChoosing the starting vertex
4. DChecking whether an edge's two endpoints are already connected