Data structures worksheet with answers

In a binary search tree, values in the left subtree of a node are:

1. ASmaller than the node's value
2. BLarger than the node's value
3. CIn random order
4. DEqual to the node's value

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

The height of a tree is commonly defined as:

1. AThe number of leaves in the tree
2. BThe total number of nodes in the tree, counting the root and every leaf
3. CThe number of edges on the longest path from the root to a leaf
4. DThe number of children of the root

How long does a search for a word of length L take in a trie with a fixed alphabet?

1. AO(log n), where n is the number of words
2. BO(L), independent of how many words are stored
3. CO(L × n)
4. DO(n), where n is the number of words

How does extract-min work in a binary min-heap?

1. ARemove the last element of the array
2. BMove the last element to the root and sift it down
3. CSearch all leaves for the new minimum
4. DRemove the root and shift all elements one place left

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

1. AAdjacency list
2. BA single sorted array of vertices
3. CA binary heap of edges
4. DAdjacency matrix

You must keep the k smallest values from a stream of n numbers using O(k) memory. Which approach works in O(n log k) time?

1. AA max-heap of size k, replacing its root when a smaller value arrives
2. BA FIFO queue of the last k values
3. CA sorted array of all n values
4. DA min-heap holding all n values, from which the k smallest are popped at the end

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

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