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

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

### Solutions

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

b.

```
What up fool?
Meeeeow!
```
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