Data structures worksheet with answers

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

1. AIn random order
2. BEqual to the node's value
3. CLarger than the node's value
4. DSmaller than the node's value

In an undirected graph, what is the degree of a vertex?

1. AThe length of the longest path from it
2. BIts position in the adjacency list
3. CThe number of edges connected to it
4. DThe number of vertices in the graph

A hash table stores data as:

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

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. A4 2 5 1 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D1 2 4 5 3

Which collision resolution method stores colliding keys in a list at the same bucket?

1. ASeparate chaining
2. BLinear probing
3. CQuadratic probing
4. DDouble hashing

How do you find the minimum key in a binary search tree?

1. ALook at the root only
2. BVisit every leaf and compare them
3. CFollow right children from the root until there is no right child
4. DFollow left children from the root until there is no left child

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AB+ trees store data only in the root
2. BAll records are in linked leaves, which makes range scans efficient
3. CB+ trees use binary internal nodes, which reduces the number of disk reads
4. DB+ trees do not need to be balanced

The time complexity of decrease-key in a binary heap (given the element's position) is:

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