1. Which of the following statements about graphs and path algorithms is true? Select zero or more of a, b, c, or d.

a. If breadth-first search is run on a graph in which vertex v is not reachable from the starting vertex s, the resulting distance from start for v is ?.

b. Dijkstras shortest path algorithm can use a priority queue to find the unvisited vertex with the smallest distance from start.

c. Depth-first search is a shortest path algorithm.

d. The running time of topological sort is O(V), where V is the number of vertices.

2. Provide the unique binary max heap that results from adding the items in the following list one at a time, in order: 43 -5 16 7 10 7. Give your answer as an array, which is the implicit representation of the resulting tree.

3. Which of the following statements about hash tables is true? Select zero or more of a, b, c, or d.

a. For quadratic probing, the size of the hash table should be a prime number.

b. For linear probing, the size of the hash table must be greater than 2N, where N is the number of items.

c. Separate chaining requires lazy deletion.

d. The running time of finding the minimum item in any hash table is O(N), where N is the number of items.

4. Give an example to demonstrate that heapsort is not a stable sorting algorithm. Provide text, as needed, to interpret your example; i.e., do not give a list of numbers and/or a drawing without explanation. It should be clear from your answer that you know both how heapsort works and what it means for a sorting algorithm to be stable.

5. Consider the following binary tree: Which of the following is true? Select zero or more of a, b, c, d, or e.

a. It is a complete binary tree.

b. It is a binary search tree.

c. It is an AVL tree.

d. It is a binary min heap.

c. It is a binary max heap.

6. Discuss the construction of a Huffman tree as a technique for file compression. Be sure to address the following:

What a Huffman tree is and how construction of the tree accomplishes variable-length encodings that are shorter for more frequently-occurring characters.

How and why the technique can result in a compressed file that is larger than the original file.

Why a tie-breaker for deciding among subtrees with the same weight is critical for consistent compression and decompression.

Give a complete, well-written answer that makes good use of examples. Do not give your answer in list or Q&A form and avoid a weak answer that provides only trivial information.

7. Items 6, 8, 4, 3, and 1 are inserted into a data structure in the exact order given. An item is deleted using only a basic data structure operation. For which of the following data structures (each coupled with its basic deletion operation) is the value of the deleted item 1? Select zero or more of a, b, c, or d.

a. hash table, remove(int x)

b. priority queue, deleteMin()

c. queue, dequeue()

d. stack, pop()