CIS5100 Fall 2005 Final Exam, open book, open notes. Name _________________

1. Suppose the root node of a heap is stored in a[0] (10 pts).
  What is the parent of a[10]?          ANSWER: a[4]
  What are the children of a[10]?       ANSWER: a[21], a[22]

2. Suppose the following array is to be sorted using quicksort.  Show
what the array looks like just before the two halves are quicksorted.
Use the last element (4) as the pivot (10 pts).

  +---+---+---+---+---+---+---+
  | 6 | 2 | 7 | 3 | 5 | 1 | 4 |
  +---+---+---+---+---+---+---+

ANSWER: start with lo at the first element (6) and hi at the last (4).
Move them toward each other until lo finds an element greater than the
pivot (4) and hi finds an element less than the pivot, then swap them:

  +---+---+---+---+---+---+---+
  | 1 | 2 | 7 | 3 | 5 | 6 | 4 |
  +---+---+---+---+---+---+---+
   lo                   hi

Repeat

  +---+---+---+---+---+---+---+
  | 1 | 2 | 3 | 7 | 5 | 6 | 4 |
  +---+---+---+---+---+---+---+
            lo  hi

Where lo and hi collide, swap with the pivot.  This is the ANSWER:

  +---+---+---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
  +---+---+---+---+---+---+---+
                lo
                hi

Then quicksort the left and right halves.  In this example the two halves
are already sorted, but in general they won't be.  Also, the two halves
might not have equal sizes.

  +---+---+---+   +---+---+---+
  | 1 | 2 | 3 |   | 5 | 6 | 7 |
  +---+---+---+   +---+---+---+


3. Write a method that adds up the data values in a binary tree and returns
the sum.  For example, sum(root) of the tree shown returns 16 (20 pts).
                                                       root
  class TreeNode {                                      |
    int data;                                           4
    TreeNode left, right;                              / \
  }                                                   2   7
  ...                                                  \
  int sum(TreeNode n) {  // your code here              3

    // ANSWER
    if (n == null)
      return 0;
    else
      return n.data + sum(n.left) + sum(n.right);
  }


4. Add a node 5 to the tree pictured above (5 pts).

  ANSWER:   root
             |
             4
            / \
           2   7
           \   /
            3 5


5. Write a method that concatenates a linked list of strings, returning a
string.  For example, cat(list) below returns "hello world" (20 pts).

  class ListNode {              list -> "hello" -> " " -> "world"
    String data;
    ListNode next;
  }
  ...
  String cat(ListNode n) {  // your code here

    // ANSWER
    String result = "";
    while (n != null) {
      result += n.data;  // concatenation
      n = n.next;
    }
    return result;
  }


6. Given classes Shape, Circle, Square, Area: (5 pts each)   ANSWERS:
  a. Which class should be the superclass?                   Shape
  b. Which class does not belong in the hierarchy?           Area
  c. Which class would declare a member of which class?      Shape has member of type Area

7. Circle True or False (2 pts each)

ANSWERS
T    A class containing an abstract method is abstract.
T    All methods of an interface are abstract.
T    If a method parameter is type X, you may pass a subclass of X.
T    Object is the superclass of all classes.
  F  String s;  creates a String.
  F  s == t is true if Strings s and t have the same value.
  F  new int[10] creates an array whose elements all equal 10.
T    A good practice for data abstraction is to make data members private.
T    A class may implement more than one interface.
  F  When an exception is caught, execution resumes from where it was thrown.