CIT 594 First Midterm
Spring 2003, Dave Matuszek
Name _______________________________________
  1. (28 points) Assuming that A and B have the given values, evaluate each of the following:

    X Y undefined undefined (X . Y) undefined
    X (Y Z) undefined Y (X Y Z) undefined
    ( ) (Y Z) undefined
    (also accepted: NIL)
    Y (Y Z) (NIL Y Z) or
    (( ) Y Z)
    (X) (Y Z)  X Y ((X) Y Z) (X Y Z)
    (X) ( )  X  undefined
    (also accepted: NIL)
    ((X)) (X)
    ( ) ( ) undefined
    (also accepted: NIL)
    (also accepted: NIL)
    (( )) or (NIL) ( ) or NIL
    (( )) Y ( ) or NIL undefined ((( )) . Y) or ((NIL) . Y) undefined or (NIL . Y)
    "Error" will be accepted anywhere the correct answer is "undefined."

  2. (3 points) Evaluate: (EQUAL '(A B C) '(A . (B . (C . NIL))) )          T

  3. (3 points) Rewrite this S-expression with as few dots as possible: ((A . B) . (C . NIL))     ((A . B) C)
    Note: The answer key that I created incorrectly had (A . B) . C). We will regrade this question.

  4. (3 points) Diagram (with boxes and arrows) this S-expression: ((A . B) . (C . NIL))


  5. (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)     O(1)

    2. (CDR A)     O(1)

    3. (CONS A B)     O(1)

    4. (APPEND A B)     O(n)

  6. (5 points) Rules for writing recursive function in Lisp (fill in the blanks):

    1. Unless the function is extremely simple, begin with a    COND   .

    2. Test for a base case first—this usually means testing for   NULL   .

    3. Avoid having more than one   base case   .

    4. Do something with the    CAR   and recur with the    CDR   .

    5. In each case of a COND you can use the fact that   all previous tests have returned false   .

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

    for all x < i, array[i] == 0    (OK to have   <=   instead of   <   ).
    "All the array locations to the left of i have been set to zero."

  8. (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
      "Every element to the right (or left) of 'outer' (or 'the index,' or something like that) is in the correct place"
      That is, for all j > outer, if i < j, then a[i] <= a[j]

    2. Selection sort
      "Every element to the left of the index (or 'outer') is in the correct place"
      for all i <= outer, if i < j then a[i] <= a[j]

    3. Insertion sort
      "All elements to the left of the index (or 'outer') are sorted (or, relatively sorted)"
      For all i < outer, j < outer, if i < j then a[i] <= a[j]

  9. (5 points) Assume: Write one or more lines of Java to delete badNode from the list it is in. = badNode.previous; =; // order does not matter
         (OK but unnecessary if they set badNode,, badNode.previous to null.)

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

    boolean hasNext()
    Object next()
    void remove()

  11. (2 points) Name two methods in the Arrays class (java.util.Arrays). (Just names, please.)

    Any two of: asList, binarySearch, equals, fill, sort

  12. (5 points) Name five methods in the Collection interface.

    Any five of: add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray

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

    The variable v is put into the stack, the actual Vector object is put in the heap.

  14. (3 points) What does the acronym DRY stand for?
    Don't Repeat Yourself

  15. (2 points) What is the distinction between prototype code and tracer code?
    Prototype code is expected to be discarded; tracer code to be kept.

  16. (2 points) What does it mean to say that two classes are "orthogonal"?

    A change to one does not require a change to the other.

  17. (2 points) What should you say when asked for an estimate of how long it will take to complete a new project?

    "I'll get back to you."  (Or words to that effect.)

  18. (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?

    Insertion sort.

  19. (4 points) Name or describe four requirements that should be met when you override equals.

    Reflexive: for any x, x.equals(x) should return true
    Symmetric: for any non-null objects x and y, x.equals(y) should return the same result as y.equals(x)
    Transitive: if x.equals(y) and y.equals(z) are true, then x.equals(z) should also be true
    Consistent: x.equals(y) should always return the same answer

  20. (2 points) What exactly does it mean to say that compareTo is consistent with equals?
    x.compareTo(y)==0    gives the same boolean result as    x.equals(y)

  21. (2 points) Name one advantage of bucket hashing over open hashing.

    You never run out of room for new entries.
    OR: Elements can be removed.

  22. (5 points) Assume: Write one or more lines of code to count the number of cells in the list.

    int count = 0;
    Cell here = first;
    while (here != null) {
        here =;
    int count;
    for (count = 0, Cell here = first; here != null; here = count++;