CIT 594 Midterm Spring 2005, Dave Matuszek Name _______________________________________
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; }```

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

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?

4. (4 points) A `Vector` has methods` int size() `and``` int capacity()```. What is the difference?
1. `size() `returns:

2. `capacity() `returns:

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

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

7. (8 points) What are Dr. Dave's four rules for doing recursion?
8. (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

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

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.

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: }```

15. (2 points) `log2 100` is between ________ (next lower integer) and ________ (next higher integer).

16. (4 points) Mention one way you can use a `HashMap` without writing your own `hashCode()` method.

17. (4 points) Why is clustering less of a problem with a bucket hash than with an open hash?

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 { } ```

19. (5 points) In Java, a hex number has the syntax `0x`digits or `0X`digits, 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.

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( ) { } ```