For this exam, you may use your textbook, Java language references, my sample code, your own programs and notes, and divine guidance, if any is available to you. You may not consult other books, web pages, or code. If you get stuck, talk to me, but you may not talk to anyone else (not even the lab assistants or sympathetic roommates) about the exam. You may discuss syntax and system problems with the lab assistants, but you must tell them that you are working on an exam.

Explain your answers clearly. Have fun.

1. (10 points) Imagine starting with an empty binary search tree whose nodes have characters for keys, and adding the letters F A C E T I O U S L Y to the tree in that order. Show the resulting tree if:

   • The tree is an ordinary binary search tree.

   • The tree is an AVL tree. Here, show all the intermediate trees as well as the final tree.

2. (6 points) Consider the following binary search tree, whose nodes' keys are letters of the alphabet:

   
   J
   E N
   C I K P
   B D G - - M O Q
   A - - - F H - - - - L - - - - R
   

   (In this representation of a tree, I have written each row of the tree from left to right, with a "-" wherever there is no node. So J is the root, the children of N are K and P, and Q has a right child R but no left child.)

   Show the tree that results when you delete the root (J) from the tree using the BST node deletion algorithm in your textbook.

3. (5 points) Start with an array of characters containing the letters FACETIOUSLY at indices 0 through 9. Now apply the heap formation algorithm that forms the first stage of Heapsort (using a min-heap). Show the resulting array. Then, delete the smallest item from the heap. Show the resulting array.

4. (12 points) For each of the following scenarios, recommend a data structure. Briefly justify your recommendation, using complexity arguments and big-oh notation where appropriate.

   • You have a database of a few hundred items, each of which has a single search key. You plan to do lots of adding and deleting, and millions of searches. It is essential that you keep search times as short as possible. You can have as much memory as you want.

   • You are going to do a word-frequency program as in your homework that was due 2/27, and run it on the text version of the English translation of Don Quixote (2.2MB). Unfortunately, you don't seem to be able to find your old code, and you have to get this program running in 45 minutes or you'll miss your bus home. You can let the program run overnight.

   • You have a database of a few million items, and it's mostly static. That is, you are seldom going to add items to or delete items from the database. Each item in the database has a single search key, and you plan to do lots of searches. Memory is extremely limited, though it is sufficient to hold all the items (this happens to PalmOS programmers with some frequency).

   • You have a database of a few hundred city names. You want to do frequent additions and searches, and you also want to be able to print out the items in sorted order.

5. (6 points) Suppose you have a binary tree node class, like this:

   
   class BTNode
   {
       public int data;
       public BTNode left;
       public BTNode right;
   }
   

   Write a method to compute the maximum data value in a binary tree:

   
   /**
    * Returns the largest data value in the specified
    * binary tree, or -1 if root is null.  Assumes the
    * data values of nodes are non-negative integers.
    *
    * @param root -- the root of the tree
    */
   static int max( BTNode root )
   

   Don't forget: (1) this is a binary tree, not necessarily a binary search tree, and (2) recursion can be your friend.

6. (9 points) Elmo, Zoe, and Grover are planning to implement a hash table that will have 1024 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.

   • Elmo advocates adding the letter numbers of the letters in the word together (e.g. ada-> 1 + 4 + 1).

   • Zoe wants to use a 32x32 2-dimensional array of slots, and take the ASCII values of the first two letters of the word, mod 32, as the indices of the slot into which the word will go.

   • Grover wants to consider the character string as a string of bits, break the bit string into 10-bit chunks, and XOR these chunks together to get the hash value.

7. (2 points) Please direct me to a web site that you find amusing or enlightening. Or just weird. Or stupid in an entertaining way. Or disturbing. You pick.

8. (12 points) Consider a graph G with 9 nodes numbered 0 through 8, whose edge set is {(0,3), (0,1), (0,7), (3,6), (3,4), (1,4), (4,5), (4,2), (7,5), (6,2), (8,2)}.

   • Draw the graph.

   • Using this breadth-first search algorithm, list the nodes in the order in which they will be visited in a search starting at node 0. Draw the resulting spanning tree.

   • Using this depth-first search algorithm, list the nodes in the order in which they will be visited in a search starting at node 0. Draw the resulting spanning tree.

   • Suppose the above edge list represents the edges in a directed graph (e.g. (0,3) represents an edge going from 0 to 3). Draw the graph again. Is this directed graph acyclic? If so, give a topological sort of the vertices. If not, explain why not.