CIT 594 Midterm
Spring 2005, Dave Matuszek
(Answer Key)
  1. (5 points) Write a short recursive method to count the number of nodes (self and all descendants) in a binary tree rooted at node. Assume you have methods getLeftChild() and getRightChild(). I've started it for you: 
    int countNodes(BinaryTree node) {
    if (node == null) return 0;
    return 1 + countNodes(node.getLeftChild( )) + countNodes(node.getRightChild( ));

}

  2. (3 points) What is the time required (using Big-O notation) to execute the method in the previous question? (Use n = number of nodes) as the "size" of the problem).
    O(n)

  3. (3 points) If we use n to mean the depth of the tree in question #1 (that is, how far it is from node to its deepest descendant), and we assume that the tree is balanced, what is the time required (using Big-O notation) to execute the method in question #1?
    O(2n) (in case this doesn't display properly, it's 2 to the power n)

  4. (4 points) A Vector has methods int size() and int capacity(). What is the difference?
    1. size() returns:
      The number of elements currently in the Vector
    2. capacity() returns:
      The number of elements the Vector can hold before it needs to be expanded.

  5. (5 points) We haven't yet studied linked lists, but all you need to know is that LinkedList implements Iterator. Write a loop to print all the elements of a LinkedList named myList.
    Iterator iter = myList.iterator( ); // using a while loop
while (iter.hasNext( )) {
    System.out.println(iter.next( ));
}
    		 
    // using a for loop
for (Iterator iter = myList.iterator( ); iter.hasNext( ); ) {
    System.out.println(iter.next( ));
}
    		 
    for (Object o : myList) { // using Java 5's enhanced for loop
    System.out.println(o);
}

  6. (12 points) True or false (T or F):
    1.  T  Java uses a stack to implement recursive methods.
    2.  T  Java uses a stack to implement non-recursive methods.
    3.  T  A Stack has both empty() and isEmpty() methods.
    4.  F  If you override equals(Object) you must also override hashCode().
    5.  T  If you override hashCode() you must also override equals(Object).
    6.  F  If you implement Observer you must have a class that extends Observable.
    7.  F  If you extend Observable you must have a class that implements Observer.
    8.  F  HTML tags are case sensitive.
    9.  T  You can put bulleted lists in a Javadoc comment.
    10.  F  No two objects in a hash table may have the same hash code.
    11.  T  Only String parameters can be passed to an applet.
    12.  T  Only the Java compiler, not the runtime, uses generic type information.

  7. (8 points) What are Dr. Dave's four rules for doing recursion?
    Do the base cases first.
    Only recur with a simpler case.
    Don't modify global variables or objects.
    Don't look down.

  8. (5 points) Draw lines to match up the Collection operations with the corresponding set operations:
    containsAll(Collection c) •
    containsAll --> subset
    		 • union
    addAll(Collection c) •
    addAll --> union
    		 • intersection
    removeAll(Collection c) •
    removeAll --> difference
    		 • difference
    retainAll(Collection c) •
    retainAll -> intersection
    		 • member

    contains(Object e) •

    contains -> member

    • subset

  9. (3 points) Why is the following code undesirable in a JUnit test method? 
        try {
          leafB2.setLeftChild(rootAB);
          fail();
    } catch (IllegalArgumentException e) {
          System.out.println("This call would form a loop.");
    }
    		 Because test methods that succeed shouldn't produce any output.
  10. (8 points) Give the complete signature and the return type of four methods specified by the Collection interface, other than the ones mentioned in the previous question. (Use the form return_type name(arg_types) ). Do not give more than four. 
    boolean add(Object o)
 void clear( )
 boolean equals(Object o)
 int hashCode( )
 boolean isEmpty( )
    		 
    Iterator iterator( )
 boolean remove(Object o)
 int size( )
 Object[] toArray( )
 Object[] toArray(Object[] a)

  11. (8 points) Give the complete signature and the return type of four methods specified by the Map interface. (Use the form return_type name(arg_types) ). Do not give more than four. 
    void clear( )
 boolean containsKey(Object key)
 boolean containsValue(Object value)
 Set entrySet( )
 boolean equals(Object o)
 Object get(Object key)
 int hashCode( )

     boolean isEmpty( )
 Set keySet( )
 Object put(Object key, Object value)
 void putAll(Map t)
 Object remove(Object key)
 int size( )
 Collection values( )

  12. (5 points) Rewrite the following class to use generics. Do not assume that x and y are the same type. 
    public class Pair {
        private Object x;
        private Object y;
        
        public Pair(Object x, Object y) {
            this.x = x;
            this.y = y;
        }
        public Object getX() { return x; }
        public Object getY() { return y;}
    }
    		 
    public class Pair<X, Y> {
        private X x;
        private Y y;
        
        public Pair(X x, Y y) {
            this.x = x;
            this.y = y;
        }
        public X getX( ) { return x; }
        public Y getY( ) { return y;}
    }

  13. (3 points) Using your generic class from the previous question, define a typesafe variable myPair with components of type Integer and Double, and assign some reasonable value to it.

    Pair<Integer, Double> pair = new Pair<Integer, Double>(5, 23.5);

  14. (3 points) The following code zeros out an array. In the space provided, write a suitable loop invariant. 
    for (int i = 0; i < myArray.length; i++) {
      myArray[i] = 0;
      // loop invariant: For all j <= i, myArray[j] == 0

}

  15. (2 points) log2 100 is between  6  (next lower integer) and   7  (next higher integer).

  16. (4 points) Mention one way you can use a HashMap without writing your own hashCode() method.
    Use only Strings as keys.
    Or, use keys for which == is an appropriate equality test.
  17. (4 points) Why is clustering less of a problem with a bucket hash than with an open hash?

    With an open hash, the larger a cluster gets, the more likely it is for new keys to hash into it, making the cluster larger. For a bucket hash, the size of the cluster does not affect the probability that new keys will hash into it.

  18. (5 points) Define a singleton class (a class having only one instance) named Add. Add should have a factory method makeAdd(), no other methods, and no instance variables. Write the complete class definition. 
    public class Add {
      static Add add = new Add( );
 
      private Add( ) { };
 
      public static Add makeAdd( ) {
          return add;
}

  19. (5 points) In Java, a hex number has the syntax 0xdigits or 0Xdigits, where digits is one or more hexadecimal digits (case insensitive). Write a BNF definition (simple or extended, your choice) for a hex number; do not worry about limiting the number of digits.

    <hex number> ::= 0x<hex digits> | 0X<hex digits>

    <hex digits> ::= <hex digit> { <hex digit> }
         OR
     <hex digits> ::= <hex digit> | <hex digit><hex digits>

    <hex digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | A | B | C | D | E | F

  20. (5 points) Write a recognizer for hex numbers, based on your answer to the previous question. Assume you have already written a boolean hexDigit() method. 

    boolean hexNumber( ) {
   // There are many possible variations on this method;
    // I've graded it mostly on whether the logic is correct
    
    if (!digit("0")) return false;
    if (!letter("x") && !letter("X")) return false;
    if (!hexDigit( )) return false;
    while (hexDigit( )) { }
    return true;    

}