COP 3530 Section 1			EXAM 2			March 17, 1999

Kraynek								Name:_______________


20 points
1. Consider the following tree:

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


a. List the nodes in preorder.



b. List the nodes in inorder



c. List the nodes in postorder




d. Give the left-most child next-sibling binary tree representation of the tree.



 10 points
2. Given the following Binary Search Tree show the resulting tree after deleting F using one of the algorithms discussed in class.

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



15 points
3. 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 inorder. HINT: Use recursion.
Use the declaration:

static void inorder(TNode T) throws MyException;


10 points
4. 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(22);
insert(55);
insert(91);
insert(51);


 15 points
5. Part of Assignment Four was to complete the ThreadedBinarySearchTree delete method

TreeNode delete(Comparable x, TreeNode T) throws MyException {
                if( T == null ) return null;
                if( x.compareTo(T.data) == 0 ) {
                        if( T.left != null && !T.isThread ) {
                                T.data = findMax(T.left).data;
                                T.left = deleteMax(T.left);
                        }else if( T.left == null && !T.isThread ) {
                                T = T.right;
                        }else if( T.left !=null && T.isThread ) {
                                T = T.left;     
                        }else {
                                T = null;
                        }
                }else if( x.compareTo(T.data) < 0 ) {
                        if( T.left != null && x.compareTo(T.left.data)==0 ) {
		*****
		*****
                        }else {
                                T.left = delete(x,T.left);
                        }
                } else if( x.compareTo(T.data) > 0 ) {
                        if( T.right != null && x.compareTo(T.right.data)==0 ) {
                        }else {
                                T.right = delete(x,T.right);
                        }
                }
                return T;
        }

Give the code that goes where the *****'s are.
         
 15 points
6.  Give implementation of the method  public void next() throws MyException for the ThreadedPreorderItr class.

15 points
7. Let nextInt() be a method that returns a random int in the range 1 to 1000000000( 1 billion). Write a method 
public int[] getInts();

that returns an array of ints of size 500000 ( 1/2 million) of unique (none repeated) random     numbers in the range from 1 to 1000000000 (1 billion). The method must be as efficient as possible and you must assume that an array of ints of size 1000000000 (1 billion) cannot be allocated (but an array of ints of size 500000 can be allocated). What is the running time of your method?