Data structures worksheet with answers

What does a map (dictionary) store?

1. AOnly values in insertion order
2. BValues sorted by size
3. CPairs of equal keys
4. DKey-value pairs with unique keys

What is a weighted graph?

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

What does a hash function do in a hash table?

1. ASorts the keys in the table
2. BCounts how many keys are stored
3. CMaps a key to an index in the table
4. DEncrypts the values in the table

A trie (prefix tree) is especially efficient for:

1. AFinding shortest paths
2. BStoring matrices
3. CSorting numbers
4. DPrefix searches such as autocomplete

A node in a binary search tree has a right subtree. Where is its in-order successor?

1. AThe rightmost node of its left subtree
2. BIts right child, always
3. CIts parent, always
4. DThe leftmost node of its right subtree

Which data structure is used by depth-first search (iterative version)?

1. AA stack
2. BA heap
3. CA hash table only
4. DA queue

Which statement about heapsort is correct?

1. AIt is stable and needs O(n) extra memory
2. BIt runs in O(n) time on any input
3. CIt sorts in place in O(n log n) worst-case time but is not stable
4. DIt needs a binary search tree as extra storage, so it uses O(n) extra memory

For each element of an array you want the next greater element to its right, in O(n) total time. Which structure helps?

1. AA queue that holds every pair of elements
2. BA hash table of all elements
3. CA binary search tree rebuilt for each element
4. DA stack that keeps elements waiting for their answer