CIT594 First Quiz
Fall, 2003		 Name_________________________________________

Please answer all questions briefly and to the point. You have plenty of room for correct answers.

Part I: Eclipse (30 points)

  1. (3 points) What happens when you double-click a line number in the Eclipse editor?
    You set a breakpoint on that line, denoted by a small blue circle.
    (The line also highlights.)
  2. (3 points) What happens when you select a method name and hit F2?
    A pop-up window appears showing a summary of the Javadoc for that method.

  3. (3 points) What happens when you double-click a method name in the Package Explorer view?
    That method is shown in the edit window (with its name highlighted).

  4. (3 points) How do you compare the current version of a method with an earlier version?
    Select the name of the method, right-click to get the context menu, choose Local History -> Compare With...

  5. (3 points) Tell one way you can add a task to the Tasks view.
    1. Right-click in left margin of edit view, choose Add task...
    2. Choose Edit -> Add Task...
    3. Put the word TODO in a comment
    4. Click on the "New Task" icon in the Tasks toolbar

  6. (3 points) Tell one way you can invoke the Eclipse code formatter.
    Select the lines you want to reformat, and either
    1. Hit Control-Shift-F, or
     2. Choose Source -> Format from the main menu, or
    3. Choose Source -> Format from the context (pop-up) menu
  7. (3 points) What happens if you type the name of an object, then a period, then hit control-space?
    You get a pop-up menu of available fields and methods.
  8. (2 points) Rename... is one refactoring provided by Eclipse. Name another.
    Move Encapsulate field Extract interface Extract method Inline
    Push down Convert anonymous class to nested Use supertype where possible Extract local variable Extract constant
    Pull up Convert nested type to top level Convert local variable to field Change method signature
  9. (3 points) Name one perspective other than the Java Perspective.
    Debug, Java browsing, Resource, CVS, Install/Update, Java Type Hierarchy, Plug-in Development
  10. (4 points) In the Package Explorer view, what is indicated by a green circle? By a red square?
    Green circle: public
    Red square: private

Part II: JUnit (12 points)
  1. (2 points) When you compare two objects with assertEquals(___, ___), which object should be first?
    The expected value.
  2. (3 points) Name (don't describe) three different JUnit "assert..." test methods (other than assertEquals).
    assertTrue, assertFalse, assertSame, assertNotSame, assertNull, assertNonNull, fail

  3. (3 points) Every JUnit test method has two versions, one with an optional first parameter. What is that first parameter?
    A message (String).
  4. (4 points) What is the JUnit setUp() method used for?
    Creating structures to be used in the tests.

Part III: Data Structures (58 points)
  1. (6 points) Write a BNF rule or rules to recognize strings of balanced parentheses, such as (), ((())), and (()(())). Unbalanced strings should be rejected. You can assume the strings contain no other characters but parentheses.

    <balanced> ::= "(" ")" | "(" <balanced> ")" | <balanced> <balanced>

  2. (6 points) Mark each of the following as either a class (C) or an interface (I):

    Set I TreeSet C Iterator I
    Stack C Comparator I Comparable I

  3. (8 points) Name (don't describe) four methods declared in the Collections interface.
    Collection: add, addAll, clear, contains, containsAll, [equals], [hashCode], isEmpty, iterator, remove, removeAll, retainAll, size, toArray

    Collections: binarySearch, copy, enumeration, fill, indexOfSubList, lastIndexOfSubList, list, max, min, nCopies, replaceAll, reverse, reverseOrder, rotate, shuffle, singleton, singletonList, singletonMap, sort, swap, synchronizedCollection, synchronizedList, synchronizedMap, synchronizedSet, synchronizedSortedMap, synchronizedSortedSet, unmodifiableCollection, unmodifiableList, unmodifiableMap, unmodifiableSet, unmodifiableSortedMap, unmodifiableSortedSet
  4. (6 points) Name (don't describe) the three methods declared in the Iterator interface.
    hasNext, next, remove

  5. (4 points) Put the following in order, best to worst: O(n2), O(2n), O(n), O(1), O(log n), O(n log n).

    (best) 
    O(1)
    O(log n)
    O(n)
    O(n log n)
    O(n2)
    O(2n)
     (worst)



  6. (5 points) How long (big O notation) do you expect the following method to take, given a completely random array? Briefly explain your answer. 
    static int getIt(int[] a) {
    int target = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] > target) return i;
    }
    return -1;
}
    		 O(1)

    Because for a random value a[0], there is a 50% chance of any other value being larger.
    Average time to find a larger value = 2 tries.
  7. (8 points) State Dr. Dave's four rules for doing recursion.

    1. Do the base case(s) first

    2. Recur only with a simpler case

    3. Don't modify globally accessible values

    4. Don't look down

  8. (3 points) In what order would you visit the nodes of the following binary tree:

    1. In preorder?   A B D E C F G
    2. In inorder?   D B E A F C G

    3. In postorder?   D E B F G C A


  9. (6 points) Complete the following method to copy a binary tree (hint: 3 more lines needed): 
    public BinaryTree copyTree(BinaryTree bt) {
    if (bt == null) return null;
    BinaryTree leftSide = copyTree(bt.leftChild);
    BinaryTree rightSide = copyTree(bt.rightChild);
    return new BinaryTree(bt.value, leftSide, rightSide);
    }
  10. (6 points) Name the Set methods corresponding to:

    1. Set union
           addAll
    2. Set intersection
           retainAll
    3. Set difference
           removeAll