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


Problem 1. (6 points) Quickies.

a. Another name for static fields is class variables.

b. Advantages of a linked list over an array (any one will suffice):

c. Advantages of an array over a linked list (any one will suffice):

d. Yes. myMethod can be overloaded by a second implementation of myMethod in MyClass that has a different signature. myMethod can be overrided by a third implementation of myMethod in a subclass of MyClass that has the same signature.

Problem 2. (8 points) Inheritance.

a. m returns 5

b. int i = ((XPlus) x).r();

c. return super.m();

d. The very last line of code causes a compile-time error. All the other lines compile and run without incident.

Problem 3. (5 points) Lists made of cons cells.

public static void main(String[] args) {
  Cons v = new Cons();
  v.cdr = new Cons();
  v.cdr.cdr = new Cons();
  v.cdr.cdr.cdr = v.cdr;
  v.car = 2;
  v.cdr.car = 3;
  v.cdr.cdr.car = 9;
Problem 4. (6 points) Loops made of cons cells.

public void breakLoop() {
  if (cdr != null) {
    if (cdr.car == -1) {
      cdr = null;
    } else {
      int i = car;
      car = -1;
      car = i;
Extra credit bonus point: Create a special Cons cell named dummyCons, which is not part of any list. Instead of marking Cons cells by setting car to -1, mark them by setting cdr to dummyCons.
Mail inquiries to cs61b@cory.eecs