Data structures worksheet with answers

In a hash table, what is a collision?

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

What is the root of a tree?

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

What is the max-heap property?

1. AEvery parent's key is greater than or equal to its children's keys
2. BAll leaves contain the maximum key
3. CThe keys are sorted from left to right
4. DEvery left child's key is greater than or equal to its right sibling's key

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 postorder traversal?

1. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 2 5 1 3
4. D4 5 2 3 1

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

1. Ai + 1 and i + 2
2. Bi/2 and i/2 + 1
3. C2i + 1 and 2i + 2
4. D2i and 2i + 1

An in-order traversal of a binary search tree visits the keys in:

1. AInsertion order
2. BAscending sorted order
3. CLevel order
4. DDescending order always

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

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

Under simple uniform hashing, what is the expected time of a search in a hash table with chaining, n keys and m buckets?

1. AO(n)
2. BO(m)
3. CO(1 + α), where α = n / m
4. DO(log n)