You may use your textbook, a computer, your brain, and, if available, divine guidance. Don't discuss this test with anyone other than Jeff Ondich.

1. (8 points) Suppose you want to build a hash table of items whose keys are strings of letters. Let the slots be numbered 0 through 6, and let the hash function consist of taking the sum of the letters mod 7. For example, "dog" hashes to (4 + 15 + 7) mod 7, that is, 5. Suppose your table contains the items "dog", "bug", "ant", "bee", and "gnu".
   • If you use linear probing to resolve collisions, what does the table look like? How many key comparisons will the longest possible failed search require?
   • If you use chaining to resolve collisions, what does the table look like? How many key comparisons will the longest possible failed search require?

2. (6 points) Start with an empty max-heap and add the items D, Q, M, P, T, B, L, and R to the heap in that order, one at a time. What does the final heap look like? Now delete the maximum item twice (after which the T and the R will be gone). What does the resulting heap look like?

3. (6 points) Do parts (c), (e) and (f) of Problem E3 on page 410 of Kruse.

4. (6 points) Start with an empty AVL tree and add the items A, H, M, J, K, Q, F, D, G, I to it, in that order. What does the resulting tree look like?

5. (8 points) Suppose you have a graph with 8 vertices, labelled 1 through 8, and edges (1,2), (1,5), (5,6), (6,7), (7,8), (5,8), (2,3), (2,7), and (4,7).
   • Draw the graph.
   • List the vertices in the order in which they're visited by a depth-first search starting at vertex 1, assuming you move towards the smallest numbered vertex if you have a choice.
   • Draw the spanning tree generated by this depth-first search.
   • List the vertices and draw the spanning tree for a breadth-first search starting at vertex 1, assuming again that you move towards the smallest numbered vertex if you have a choice.

6. (3 points) I've been trying for several years to come up with new names for the Macintoshes in CMC 301. They have been named after McDonald's "food" items since we moved into the building. Please suggest a better theme for the machine names.

7. (9 points) Don, Edsger, and Grace are planning to implement a hash table that will have 2048 slots. They have agreed to resolve collisions with chaining. The items the hash table will contain will be English words. They are arguing over what hash function to use. Criticize (positively or negatively) each of these proposals.
   • Don advocates adding the letter numbers of the letters in the word together (e.g. ada-> 1 + 4 + 1).
   • Edsger wants to use a 64x64 2-dimensional array of slots, and take the ASCII values of the first two letters of the word, mod 64, as the indices of the slot into which the word will go.
   • Grace wants to consider the character string as a string of bits, break the bit string into 12-bit chunks, and XOR these chunks together to get the hash value.

8. (6 points) If you have an N-node binary tree, and you call Inorder() (see page 393 of Kruse) on the tree's root, how many times does Inorder() get called?

9. (12 points) For each of the following scenarios, tell me what data structure I should use, and defend your choice. If implementation details matter (such as whether you'll use an array or a linked structure), include them in your discussion.
   • I want to have a database into which I can quickly insert items, from which I can quickly delete items, and which I can access efficiently in sorted order. I must also be able to search for an item in this database, and it is essential that my worst-case search time be fast (linear search is not acceptable).
   • Memory is very tight, so I don't want to waste any. I want to maintain a database of items that will never change, and I know exactly how many items there are. I will be searching for items in the database often.
   • I want to maintain a database. Additions, deletions, and especially searches have to be very fast. I have lots of memory available.