CIT594 Midterm Exam Spring 2011 Name_________________________________________

Please keep all your answers short and to the point. Do not provide extra information that was not asked for. Where Java code is requested, minor syntax errors will be forgiven.

1. We will define a simple number as either a unsigned integer, or an unsigned real number with no exponent. Example simple numbers are:` 25`,` 3.5`,` 177.`, and` .0003`.

1. (5 points) Write a complete BNF definition of “simple number”.

2. (5 points) Write a regular expression to match simple numbers (and nothing else).

2. (5 points) What are the instructor’s rules for recursion?

3. (10 points) Here are some statements about an array, partway through sorting it:
1. There is a part of the array in which all values are in their correct and final place.
2. There is a part of the array in which all values are in the correct order, relative to one another.
3. There is a part of the array in which all values are smaller than in another part of the array.
For each of the following sort algorithms, choose the statement that best describes the array (fill in the correct letter from above).
1. __ Bubble sort
2. __ Heapsort
3. __ Insertion sort
4. __ Quicksort
5. __ Selection sort

4. Class ` BinarySearchTree<Integer> `defines a binary search tree for integers (smaller or equal numbers to the left, larger numbers to the right). The value, left child, and right child of a node` n `can be accessed with the functions `n.value()`,` n.leftChild()`, and` n.rightChild()`, respectively.

1. (5 points) Write a recursive method to return the largest integer in a `BinarySearchTree`.

`int largest(BinarySearchTree<Integer> root) {`

2. (5 points) Write a recursive method to print out all the numbers in the given `BinarySearchTree` in reverse order (that is, largest to smallest).

`void printRev(BinarySearchTree<Integer> root) {`

5. (5 points) Write a recursive LOL function to compute the factorial of a positive integer. Call the function to compute the factorial of 10, and tell the user the result.

6. (5 points) What are the three methods in the `Iterator` interface? (Give complete signatures.)

7. Consider the following method:
```    boolean hasDuplicates(int[] array) {
for (int i = 0; i < array.length; i++)
// loop invariant for part (c)goes here
for (int j = i + 1; j < array.length; j++)
if (array[i] == array[j]) return true;
return false;
}```
1. (5 points) Using Big-O notation, what is the running time of this algorithm? Briefly defend your answer.

2. (5 points) Describe (in English; don’t write code) a faster algorithm to test an array for duplicates.

3. (5 points) What is the loop invariant for the outer loop? State it formally if you can, but an informal statement, if sufficiently precise, will also be acceptable.

8. (5 points) If you define a class `Employee`, and you want to use `Employee` objects as keys into a `HashMap`, what two methods must you define? (Give complete signatures.)

9. (5 points) In order to put `Employee` objects into a `TreeSet`, what interface must `Employee` implement, and what method must you define (give complete signature)?

10. (5 points) Suppose `set` is a `TreeSet<String>`. Write a Java statement or statements (not a complete function) to create a `LinkedList<String> list` containing all the elements of `set`.

11. (5 points) Name two garbage collection algorithms, and list one disadvantage of each.

12. (5 points) Give a precise statement of what it means to say that a binary tree is balanced.

13. (10 points) Briefly but precisely, define each of the following terms:

2. Branching factor of a tree

3. Serialization

4. Heap (as in Heapsort)

5. Heap (as in storage management)

14. (5 points) Is Java's `LinkedList` class implemented using singly-linked lists or doubly-linked lists? Tell why you think your answer is correct.