Data structures worksheet with answers

Which data structure is most suitable for the "undo" feature in a text editor?

1. AStack
2. BQueue
3. CHash set
4. DGraph

What is a weighted graph?

1. AA graph with more edges than vertices
2. BA graph in which some vertices are heavier than others because they have more edges
3. CA graph in which each edge has a numeric value such as a cost or distance
4. DA graph that is stored on disk

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

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

AVL trees and red-black trees guarantee:

1. AO(log n) height through rebalancing
2. BThat keys are stored in insertion order
3. CConstant-time search in every case
4. DThat no node has two children

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 5 2 3 1
2. B5 4 3 2 1
3. C4 2 5 1 3
4. D1 2 4 5 3

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

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

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

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

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 min-heap holding all n values, from which the k smallest are popped at the end
3. CA sorted array of all n values
4. DA FIFO queue of the last k values