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

Solutions

Problem 1. (6 points) Quickies.

a. A final field is set by an initializer and cannot change. Since it usually has the same value for every object in the class, there's no point in having a separate copy of that value for every object.

b. Errors that might be produced by the code line Object o = s.subString(0);

No doubt there are other reasonable answers. (However, no error occurs if s references the empty string "". Sorry.)

c. The switch statement is buggy because it is missing break statements at the end of each case (or at least the first two). For instance, it will always report that i/3 has a remainder of 2, regardless of the value of i.

d.


  public void moveToEnd() {
    // Moves the first node of the list to the end of the list.
    if (head != null) {
      tail.next = head;
      head.prev = tail;
      tail = head;
      head = head.next;
      head.prev = null;
      tail.next = null;
    }
  }
}

Problem 2. (5 points) Inheritance.

a. No changes are necessary. No code in the DateAndPlace class attempts to access any fields in the Date class.

b. The last line causes a compile-time error, because the isSamePlace method isn't part of the Date class, and there is no cast to ``reassure'' the compiler that d references a DateAndPlace object.

c. Adding this constructor will cause a compile-time error because there is already a constructor with the same signature.

Problem 3. (5 points) Fields, objects, and the stack.

Problem 4. (6 points) Counting runs.


  public int countRuns() {
    int count = 1;
    int i;

    if (myArray.length == 0) {
      return 0;
    }
    for (i = 1; i < myArray.length; i++) {
      if (myArray[i] != myArray[i - 1]) {
        count++;
      }
    }
    return count;
  }
To get the classes to compile, you also need to add the following abstract method declaration to the List class.

  public abstract int countRuns();
(Alternatively, you could have added a non-abstract method with an implementation just so there's a method to override, but the implementation must return some int or it won't compile.)
Mail inquiries to cs61b@cory.eecs