COP 3530                 Exam 1              July 25, 2000

Kraynek                                      Name:________________

5 points
1. Which function grows faster, n*(logn)2 or n2*logn ?

5 points
2. What is the running time of the following method?

     void problem2(int[] A, int left, int right) {
         if( left > right) return;
         int middle = (left+right) / 2;
         for( int i = left; i < right ; i++ ) {
          if( A[i] < A[i+1] ) {
             int s = A[i];
             A[i] = A[i+1];
             A[i+1] = s;
          } // end if
          } // end for
          problem2(A, left, middle-1);
     } // end problem2

10 points
3. Let T be a binary search tree. Suppose that the size() method is not available. Write a
method int numberOfNodes(TreeNode T) that returns the number of nodes in T.
5 points
4. Do problem 3 for a threaded binary search tree.
5 points
5. Let T be a binary tree of n nodes. What is the running time of the inorder traversal
algorithm for T as a function of n? Why? You do not need to do a computation here. Think
about walking around the tree.

15 points
6. Write a Java main class to read a file named Problem6.txt and output to the screen all the
unique words in the file in alphabetic order. Assume the String DELIMITERS has been
defined.
10 points
7.  Consider the following tree:

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


  a. List the nodes in inorder.
  b. Give the left-most child next-sibling binary tree representation of the tree.
5 points
8. Consider the following class definition for a node of an arbitrary tree:
  public class TreeNode {
       Object data;
       List children;
       public TreeNode(Object data) {
            this.data = data;
            children = new LinkedList();
       }
  }

Implement a method to output the nodes of the tree in postorder. HINT: Use recursion.
Use the declaration:
static void postorder(TreeNode T) ;
15 points
9. Write the method TreeNode getMax(TreeNode T) that returns the TreeNode with the
maximum data value in a threaded binary search tree.
15 points
10. Suppose we are implementing some of the abstract Java data structure classes so that
they are modifiable.
  a. What methods do we need to implement when extending AbstractCollection?
  b. What methods do we need to implement when extending AbstractSet? 
  c. What methods do we need to implement when extending AbstractList? 
  d. What methods do we need  to implement when extending AbstractSequentialList? 
  e. What methods do we need to implement when implementing the Iterator class?