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.
 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
.
 (5 points) Write a complete BNF definition of “simple number”.
 (5 points) Write a regular expression to match simple numbers (and nothing else).
 (5 points) What are the instructor’s rules for recursion?
 (10 points) Here are some statements about an array, partway through sorting it:
 There is a part of the array in which all values are in their correct and final place.
 There is a part of the array in which all values are in the correct order, relative to one another.
 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).
 __ Bubble sort
 __ Heapsort
 __ Insertion sort
 __ Quicksort
 __ Selection sort
 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.
 (5 points) Write a recursive method to return the largest integer in a
BinarySearchTree
.
int largest(BinarySearchTree<Integer> root) {
 (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 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.
 (5 points) What are the three methods in the
Iterator
interface? (Give complete signatures.)

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;
}
 (5 points) Using BigO notation, what is the running time of this algorithm? Briefly defend your answer.
 (5 points) Describe (in English; don’t write code) a faster algorithm to test an array for duplicates.
 (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.
 (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.)
 (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)?
 (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
.
 (5 points) Name two garbage collection algorithms, and list one disadvantage of each.
 (5 points) Give a precise statement of what it means to say that a binary tree is balanced.
 (10 points) Briefly but precisely, define each of the following terms:
 Façade function
 Branching factor of a tree
 Serialization
 Heap (as in Heapsort)
 Heap (as in storage management)
 (5 points) Is Java's
LinkedList
class implemented using singlylinked lists or doublylinked lists? Tell why you think your answer is correct.