Data structures worksheet with answers

The depth of a node in a tree is:

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

Which structure is typically used to implement a priority queue?

1. AA singly linked list without order
2. BA heap
3. CA string
4. DA stack

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 happens when a hash table rehashes after its load factor exceeds a threshold?

1. AThe oldest keys are deleted to make room
2. BA larger table is allocated and every key is inserted again
3. CThe existing keys are sorted in place
4. DOnly the colliding keys are moved to a new overflow list at the end of the table

Which data structure is used by depth-first search (iterative version)?

1. AA heap
2. BA hash table only
3. CA queue
4. DA stack

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

1. A2i + 1
2. B(i + 1) mod n
3. C(i − 1) mod n
4. Di + 1

For a hash table to work correctly, which rule must hash and equality follow?

1. ADifferent keys must have different hash values
2. BEqual hash values imply equal keys
3. CEqual keys must have equal hash values
4. DHash values must be prime numbers

What does a splay tree do after each access?

1. ARebuilds the whole tree in balanced form
2. BRecolours the nodes on the search path
3. CMoves the accessed node to a leaf
4. DRotates the accessed node up to the root