Data structures worksheet with answers

How many edges does a tree with n nodes have?

1. An + 1
2. B2n
3. Cn
4. Dn − 1

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

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

In a hash table, what is a collision?

1. AA key cannot be hashed at all
2. BTwo equal keys are stored twice
3. CThe table runs out of memory
4. DTwo different keys map to the same index

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. AArrays use fewer instructions to compare values
2. BArray traversal is O(1) in total, while linked list traversal is O(n)
3. CArray elements are contiguous, so they make good use of the CPU cache
4. DLinked lists always store elements on disk

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. A2i and 2i + 1
2. Bi + 1 and i + 2
3. Ci/2 and i/2 + 1
4. D2i + 1 and 2i + 2

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

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

Which pair of traversals always determines a unique binary tree with distinct keys?

1. APreorder alone
2. BLevel-order alone
3. CPreorder and inorder
4. DPreorder and postorder

A Bloom filter can answer "is this element in the set?" with:

1. APossible false positives but no false negatives
2. BExact answers always
3. CAnswers only for numbers
4. DPossible false negatives but no false positives