CS 61B: Data Structures (Autumn 2006)
Midterm I

If you want to relive taking the midterm, here it is in PostScript or PDF.


Problem 1. (6 points) Java bugs.

public class Quantity {
  public String thing;       // The thing being measured.
  public double amount;      // Its numerical quantity.

  // Constructor.
  public Quantity(String thingString, double amount) {
    thing = thingString;
    this.amount = amount;

  // Constructor for thing with quantity 100.  Calls the other constructor.
  public Quantity(String thingString) {
    this(thingString, 100.0);

  public static void main(String[] args) {
    Quantity q = new Quantity("I love Java this much:  ");
    System.out.println(q.thing + q.amount);
Problem 2. (7 points) Inheritance.

a. Meow


What up fool?
c. Compile-time error. (Tomcat t = c; needs a cast.)

d. Meeeeow!

e. Compile-time error. (The Cat class does not have a method with the signature greet(Cat).)

f. Run-time error. (Attempt to cast a Siamese object to a Tomcat.)

g. Compile-time error. (Cannot create an instance of the abstract class Cat.)

Problem 3. (7 points) The heap and the stack.

Problem 4. (5 points) Creating a Doubly-Linked List.

This sample solution builds the list backward, from tail to head. That way, no special cases are needed to handle a zero-length array or an array whose ints are all zero.

  public static DListNode makeList(int[] counts) {
    DListNode l = null;
    for (int i = counts.length - 1; i >= 0; i--) {
      for (int j = 0; j < counts[i]; j++) {
        l = new DListNode(counts[i], null, l);
        if (l.next != null) {
          l.next.prev = l;
    return l;

Mail inquiries to cs61b@cory.eecs