CIT594 Midterm I

CIT 594 Midterm
Spring 2005, Dave Matuszek

Name _______________________________________

(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; }
(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).
(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?
(4 points) A Vector has methods int size() andint capacity(). What is the difference?
1. size() returns:
2. capacity() returns:
(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.
(12 points) True or false (T or F):
1. ____ Java uses a stack to implement recursive methods.
2. ____ Java uses a stack to implement non-recursive methods.
3. ____ A Stack has both empty() and isEmpty() methods.
4. ____ If you override equals(Object) you must also override hashCode().
5. ____ If you override hashCode() you must also override equals(Object).
6. ____ If you implement Observer you must have a class that extends Observable.
7. ____ If you extend Observable you must have a class that implements Observer.
8. ____ HTML tags are case sensitive.
9. ____ You can put bulleted lists in a Javadoc comment.
10. ____ No two objects in a hash table may have the same hash code.
11. ____ Only String parameters can be passed to an applet.
12. ____ Only the Java compiler, not the runtime, uses generic type information.
(8 points) What are Dr. Dave's four rules for doing recursion?

(5 points) Draw lines to match up the Collection operations with the corresponding set operations:

containsAll(Collection c) •

addAll(Collection c) •

removeAll(Collection c) •

retainAll(Collection c) •

contains(Object e) •

• union

• intersection

• difference

• member

• subset

(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.");
    }

(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.
(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.

(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;}
}

(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.
(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: }
(2 points) log₂ 100 is between ________ (next lower integer) and ________ (next higher integer).
(4 points) Mention one way you can use a HashMap without writing your own hashCode() method.
(4 points) Why is clustering less of a problem with a bucket hash than with an open hash?
(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 { }
(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.
(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( ) { }