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

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

    2. true    In Java, arrays are objects.

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

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

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

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

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

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

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

    10. false   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)

      The data type carries information about itself.

    2. stable (when describing a sorting algorithm)

      Equal elements retain their relative positions after sorting.

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

           O(n2)

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

           x.compareTo(y) == 0 gives the same boolean result as x.equals(y)
           (This has nothing to do with the reflexive, symmetric, transitive restrictions on equals!)

  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

           63     log n     n     n log n     n2     n5     2n
  6. (12 points) Name (don't describe) the three kinds of nodes in a tree.

           root, internal nodes, leaves