COP 3530 				EXAM 2		June 27, 2002

Kraynek							Name:_______________

12 points
1. Consider the following tree:
				            A
				       /     |     \
				   B      C      D
				   |      /  |  \      |	
     				  E    F G H    I
				           /  \
				         J    K	
List the nodes of the tree in
 
i. preorder 

ii. inorder 

iii. postorder


5 points
2. Given the following BinarySearchTree, show the tree after the node containing 10 (the root) has been removed using a BinarySearchTree node removal algorithm. 


                                  10
                               /         \
                            7            15
                         /     \        /        \
                      3        9    12       17
                    /   \     /   \  /   \      /    \
8     13
                           /   \        /   \



10 points
3. Let A = { 3, 5, 10, 1, 6, 9, 8, 7, 2, 4 } be an array of ints. Show the resulting array after it has been built into a heap using either the pushDown method or the PushUp method. (Use one or the other but not both).

15 points
4. For the following graph, show the previous and distance values at each node after applying the all shortest paths for weighted graphs algorithm starting from 0.


8 points
5. 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(33);
insert(5);
insert(23);
insert(4);
insert(37);
insert(3);

15 points
6. Write a recursive method 
	boolean contains(Object x, Tree T);
that returns true if x is in the Tree T and false otherwise.
Some public methods of the Tree class are:
public class Tree {
	public void addChild(Tree t);
	public Object getData();
	public LinkedList getChildren();
	public boolean isLeaf();
	public String preorder();
	public Iterator preorderIterator();
} // end Tree


15 points
7. Write a preorder Iterator for the BinaryTree class. Hint: Recall the preorder Iterator from the Tree class.
The fields of the BinaryTreeNode class are:
class BinaryTreeNode {
	Object data;
	BinaryTreeNode left;
	BinaryTreeNode right;
} // end BinaryTreeNode 

20 points
8. The data file cities.data is a text file containing pairs of cities separated by a blank on each line. Each line means that there is a road between the pair of cities on that line. Write a main method to read the data file and output the shortest path of cities using those roads between Miami and Pittsburgh. Use the UnweightedGraph class and

public static void main(String[] args) throws IOException {
//your declarations
 

      BufferedReader in = new BufferedReader(new FileReader(“cities.data”));
      String aLine;
      while( (aLine = in.readLine()) != null ) {
  	StringTokenizer t = new StringTokenizer(aLine);
	String city1 = t.nextToken();
	String city2 = t.nextToken();
// your code