COP 3530			EXAM 3			April 1, 1998

Kraynek							Name:_______________

10 points
1. Consider the following tree:


						    A
				           /    |   \
				         /      |     \
				       B     C      D
				     /  |  \         /    \
				   /    |    \      /       \
				 E     F   G  H       I
				         |                  
				         |                
				         J              


a. List the nodes in preorder.


b. Give the binary tree representation of the tree.
20 points
2. Recall the Queue interface

public interface Queue {
     void enqueue(Object x);
     Object getFront();
      void dequeue();
      boolean isEmpty();
      void makeEmpty();
}

Let LevelItr be an implementation of the TreeIterator interface for a BinarySearchTree with a Queue data member Q and TreeNode data member current. Write the method to move current to the next position in the level order of the BinarySearchTree. Use the declaration

		public void next() throws MyException;

10 points
3. a). Suppose we have a closed hash table implemented as an array of ints with size = 10 and quadratic resolution of collisions. Show the array after the following operations have been performed:

insert(11);
insert(2);
insert(41);
insert(100);
insert(1);
      (b). Show the array after rehashing to a table with size = 20.




20 points
4. Consider the following class definition for a node of an arbitrary tree:
	public class TNode {
		Object data;
		LinkedList children;

		public TNode(Object data) {
			this.data = data;
			children = new LinkedList();
		}
		public void addChild(Object data) {
			TNode child = new TNode(data);
			children.addElement(child);
		}

		public LinkedList getChildren() {
			return children;
		}

		public Object getData() {
			return data;
		}
	}
Implement a method to output the nodes of the tree in preorder. HINT: Use recursion.
Use the declaration:
static void preorder(TNode T) throws MyException;
15 points
5. Suppose that H is a Hashtable with Strings as keys and Integers as values. Write the implementation of the method with declaration 
void update(Hashtable H, String code, int amount);
as follows; if code is a new key then insert it with amount as it's value else update it's                value in H by adding amount.
15 points
6. Suppose we have a PriorityQueue implemented by a BinaryHeap array. Show the array after the following operations are performed.

add(7);
add(37);
add(6);
add(23);
add(4);
add(11);
add(3);
add(12);
add(17);
add(26);
add(2);
heapify();
deleteMin();
deleteMin();
insert(9);




10 points
7. (a) Describe how a BinaryHeap can be used to sort an array. 

(b) What is the average case running time of your algorithm?