Data structures worksheet with answers

What is the root of a tree?

1. AThe node with the largest value
2. BAny node in the middle
3. CThe top node with no parent
4. DA node with no children

In a tree, what are sibling nodes?

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

Where is the smallest element of a binary min-heap found?

1. AAt the root
2. BIn any leaf, which must be searched
3. CIn the leftmost leaf
4. DIn the last array position

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A4 5 2 3 1
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D1 2 4 5 3

What is the purpose of a sentinel (dummy) node in a linked list?

1. ATo simplify code by removing special cases at the head or tail
2. BTo store the number of elements
3. CTo prevent the list from growing beyond a fixed maximum number of nodes
4. DTo make the list sorted

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

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

How does a radix tree (compressed trie) improve on a plain trie?

1. AIt merges chains of single-child nodes into one edge labelled with a string
2. BIt keeps only the first letter of each word
3. CIt sorts the children of each node by frequency
4. DIt stores each word in a hash table at the root instead of in separate nodes

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

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