COP 3530 Section 1            EXAM 2              April 3, 2000

Kraynek                                      Name:_______________


10 points
1. Consider the following tree:

                       A
                               /     |    \
                             /       |      \
                          B       C       D
                        /  |  \            /     \
                      /    |    \        /        \
                    E     F   G     H        I
                     |      |                    /   \
                     |      |                  /       \
                     J     K              L         M
  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.

 20 points
2. 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.add(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) ;
 
 20 points
3.  Write the boolean add(Object x) method from Assignment 5. Assume the method int
binarySearch(Object[] A, Object x) that returns -1 if x is in the array A and the position where x should
be inserted to keep the array sorted if x is not in the array A.  
  

 5 points
4. 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      
                         /    \              /   \                /  \
                                                                   

 10 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(0);
insert(1);
insert(44);
insert(90);
insert(50);




20 points
6. Suppose we are implementing the Iterator interface for a Binary Search Tree class using an inorder
iteration. Write the method public Object next(). Use current as the TreeNode variable and S as the
Stack variable.


10 points
7.  Consider the following graph:























  At each node write the distance value and the previous value that would result in applying the all
unweighted shortest paths algorithm discussed in class using 0 as the start node.



5 points
8. Let g be a graph with n vertices and m edges. What is the running time of the all unweighted shortest
paths algorithm discussed in class?