CS 61B: Data Structures (Spring 2005)
Midterm I

Solutions

Problem 1. (4 points) Quickies.

a. If you decide later that you want to make a subclass of the class where the instance variable appears, the new functionality that you add to the subclass might need to access the variable. If the variable is protected, you can access it from the subclass. If the variable is private, you'll have no choice but to go back and modify the superclass. (This could be very inconvenient if your company has already released the superclass to customers.)

b. Circle objects are immutable, because after one has been constructed, it is not possible to change any of its internal state. (The sole field radius is private, and no method of Circle modifies it.)

c. In a static method, you can never use the keyword this. (You can never use super either.)

d. Java's continue statement can only jump back to the beginning of a loop--namely for, while, or do.

Problem 2. (8 points) Inheritance.

a. M1 in C

b. M2 in C

c. Run-time error. (You can't cast an A object to static type C; not every A is a C.)

d. Compile-time error. (The interface B does not have a whichClass method.)

e. (This is the two-point question.)


New A
New C
M1 in C
f. M1 in A

g. Compile-time error. (You cannot create a B object.)

Problem 3. (6 points) Binary Search.

We'll accept a 2 written in the j field as well.

Problem 4. (7 points) Reordering a Singly-Linked List.


  public void reorder() {
    if (head != null) {
      SListNode evenhead = head.next;
      SListNode tail1 = head;
      SListNode tail2 = head.next;
      while ((tail2 != null) && (tail2.next != null)) {
        tail1.next = tail2.next;
        tail2.next = tail2.next.next;
        tail1 = tail1.next;
        tail2 = tail2.next;
      }
      tail1.next = evenhead;
    }
  }

Mail inquiries to cs61b@cory.eecs