Data structures worksheet with answers

A hash table stores data as:

1. AA tree with ordered keys
2. BKey–value pairs located by a hash function
3. CA sorted list only
4. DA fixed-length string

What is the root of a tree?

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

In a singly linked list, what does the next pointer of the last node contain?

1. AThe number of nodes in the list
2. BThe address of the previous node
3. CThe address of the first node
4. DNull (no node)

A trie (prefix tree) is especially efficient for:

1. AStoring matrices
2. BSorting numbers
3. CFinding shortest paths
4. DPrefix searches such as autocomplete

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. Alog₂ n
2. B√n
3. Cn (it becomes a linked list)
4. D1

A circular buffer (ring buffer) is commonly used to implement:

1. AA binary search tree
2. BA graph traversal
3. CA fixed-size queue
4. DA hash function

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is exactly log₂ n
2. BThe height is at most 2 log₂(n + 1)
3. CThe height is at most log₂ n + 1
4. DThe height is at most n / 2

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(m)
2. BO(1 + α), where α = n / m
3. CO(n)
4. DO(log n)