CIT594 Midterm I

CIT 594 First Midterm
Spring 2003, Dave Matuszek

Name _______________________________________

(28 points) Assuming that A and B have the given values, evaluate each of the following:

`A`	`B`	`(CAR A)`	`(CAR B)`	`(CONS A B)`	`(APPEND A B)`
`X`	`Y`
`X`	`(Y Z)`
`( )`	`(Y Z)`
`(X)`	`(Y Z)`
`(X)`	`( )`
`( )`	`( )`
`(( ))`	`Y`

(3 points) Evaluate: (EQUAL '(A B C) '(A . (B . (C . NIL))) )
(3 points) Rewrite this S-expression with as few dots as possible: ((A . B) . (C . NIL))
(3 points) Diagram (with boxes and arrows) this S-expression: ((A . B) . (C . NIL))
(4 points) Assuming that the length of list A is n and the length of list B is m, give the Big-O running time of each of the following:
1. (CAR A)
2. (CDR A)
3. (CONS A B)
4. (APPEND A B)
(5 points) Rules for writing recursive function in Lisp (fill in the blanks):
1. Unless the function is extremely simple, begin with a ________________________.
2. Test for a base case first—this usually means testing for ________________________.
3. Avoid having more than one ________________________.
4. Do something with the __________________ and recur with the __________________.
5. In each case of a COND you can use the fact that ________________________.
(2 points) State, either in English or in logic notation, the loop invariant for the following code:

for (int i = 0; i < array.length; i++) array[i] = 0;
(6 points) State, either in English or in logic notation, the loop invariant for the outer loop in each of the following:
1. Bubble sort
2. Selection sort
3. Insertion sort
(5 points) Assume:
- A doubly-linked list is composed of nodes, defined as:
  class Node {int value; Node previous; Node next; }
- badNode is a reference to a node in a doubly-linked list.
Write one or more lines of Java to delete badNode from the list it is in.
(4 points) List the names of all the methods in the Iterator interface, along with their parameter types and return types. Do not tell what each method does.
(2 points) Name two methods in the Arrays class (java.util.Arrays). (Just names, please.)
(5 points) Name five methods in the Collection interface.
(6 points) Java uses two types of memory when the statement Vector v = new Vector(10) is executed. Name the two types and tell what is put into each type.
(3 points) What does the acronym DRY stand for?
(2 points) What is the distinction between prototype code and tracer code?
(2 points) What does it mean to say that two classes are "orthogonal"?
(2 points) What should you say when asked for an estimate of how long it will take to complete a new project?
(2 points) Of the three sorting methods we studied--bubble sort, insertion sort, selection sort--which one would be preferable if we know the array is almost sorted, with just a few elements out of place?
(4 points) Name or describe four requirements that should be met when you override equals.
(2 points) What exactly does it mean to say that compareTo is consistent with equals?
(2 points) Name one advantage of bucket hashing over open hashing.
(5 points) Assume:
- class Cell is defined as class Cell { int value; Cell next; },
- several Cells are joined together to form a linked list,
- variable first is a reference to the first cell in the list
Write one or more lines of code to count the number of cells in the list.