Data structures worksheet with answers

What does a map (dictionary) store?

1. APairs of equal keys
2. BKey-value pairs with unique keys
3. COnly values in insertion order
4. DValues sorted by size

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

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

In which order does a preorder traversal of a binary tree visit nodes?

1. ALeft subtree, then node, then right subtree
2. BLevel by level from the top
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then right subtree, then node

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. Ah²
2. B2h + 1
3. C2^h
4. D2^h+1 − 1

An in-order traversal of a binary search tree visits the keys in:

1. AAscending sorted order
2. BInsertion order
3. CDescending order always
4. DLevel order

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

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

In a hash table using open addressing, why is deletion often done with a "tombstone" marker?

1. ADeleted keys must be kept forever for security, so slots can never be reused
2. BTombstones speed up hashing
3. CIt makes the table sorted
4. DEmptying the slot could break the probe sequence for other keys

What are the time and extra space costs of reversing a singly linked list in place?

1. AO(n log n) time and O(1) extra space
2. BO(1) time and O(1) extra space
3. CO(n) time and O(1) extra space
4. DO(n) time and O(n) extra space