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)