CIT 594 Second Quiz
Spring 2002, Dave Matuszek
Name __________________________________________
  1. (5 points each) True or false:

    1. _____ In Java, the length of an array is part of its type definition.

    2. _____ In Java, arrays are objects.

    3. _____ In Java, accessing an array element requires constant time.

    4. _____ The time complexity of an algorithm is usually more important than its space complexity.

    5. _____ Space complexity can be important in a doubly-recursive algorithm.

    6. _____ An operation op is reflexive if op(x, x) returns true for all x.

    7. _____ An operation op is transitive if, whenever op(x, y) is true, op(y, x) is also true.

    8. _____ A recursive and a non-recursive binary search have the same time complexity.

    9. _____ Certain data sets can make quicksort take O(n2) time.

    10. _____ In a doubly-linked list, every node has both a successor and a predecessor.

  2. (5 points each) Give a brief definition (without examples) of each of the following terms:

    1. reflective (when describing a data type)

    2. stable (when describing a sorting algorithm)

  3. (8 points) A certain algorithm takes exactly 43n2+24n+17 time units. What is its time complexity?

  4. (10 points) What does it mean to say that compareTo is consistent with equals ? (Be precise)

  5. (10 points) Rewrite the following list of functions in order of increasing Big-O complexity:
              n     n log n     63     n2     2n     n5     log n

  6. (12 points) Name (don't describe) the three kinds of nodes in a tree.