For this exam, you may consult your textbook, C++ language references, my sample code, and your own programs and notes. You may not use other books, web pages, or code. If you get stuck, talk to me, but please don't talk to anyone else (not even the lab assistants) 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.

1. (10 points) Imagine starting with an empty binary search tree whose nodes have characters for keys, and adding the letters C A R L E T O N 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.

2. (5 points) Start with an array of characters containing the letters C A R L E T O N at indices 1 through 8. 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.

3. (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/19, 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.

4. (8 points) Suppose you have a Set class defined like this:

   
   template <class T>
   class Set
   {
   private:
   	// A list of unique items, sorted in increasing order.
   	list<T>		mItems;
   
   public:
   	...
   	// Modifies *this to be the union of *this with b. 
   	// For example, if both a and b are declared as type
   	// Set<int>, then a.Union( b ) changes a to be
   	// the union of a and b.
   	void		Union( const Set<T>& b );
   	...
   };
   

   Write an implementation for the Union function. Don't forget that a set is a collection of distinct items.

5. (9 points) Elmo, Zoe, and Grover 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.

   • Elmo advocates adding the letter numbers of the letters in the word together (e.g. ada-> 1 + 4 + 1).
   • Zoe 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.
   • Grover 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.

6. (2 points) Tell me a joke, if you wish.

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

   
   R
   J U
   D L S V
   C H - M - T - Y
   B - F I - - - - - - - - - - - -
   

   (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 R is the root, the children of U are S and V, and V has a right child Y but no left child.)

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

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

   • 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.