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

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

### Solutions

Problem 1. (8 points) Program Errors and Java Keywords.

a. The variable i has not been declared. Add an int i; (as a separate line or in the for statement).

The run-time exception (an ArrayIndexOutOfBoundsException) arises when Java tries to access the invalid array member a[i - 1] with i equal to zero. Fix it by taking advantage of short-circuiting in the if statement:

```
if (i != 0 && a[i].length() > a[i - 1].length()) {
```
The debugged program prints out the command-line parameters, appending a "9" to each parameter that is longer than the previous parameter.

b. These three lines won't compile.

```
Object o = new Comparable();
double d = ((Object) "string").length();
int i = Integer.parseInt(super.toString());
```
You cannot construct a Comparable object, because Comparable is a Java interface. The class Object has no length method. In a static method like main, there is no super.

c. static final.

d. continue and return.

Problem 2. (9 points) The Heap and the Stack.

Problem 3. (8 points) Transposing a Matrix Represented by Linked Lists.

In this sample solution, the index j counts down rather than up, because the inner loop builds a new list from tail to head. This simplifies the code a bit.

```
public class SListNode {
public int item;
public SListNode next;

public SListNode[] transpose(SListNode[] mx, int columns) {
SListNode[] t = new SListNode[columns];    // Transposed matrix goes here.
for (int i = 0; i < columns; i++) {
for (int j = mx.length - 1; j >= 0; j--) {
SListNode n = mx[j];
mx[j] = n.next;
n.next = t[i];
t[i] = n;
}
}
return t;
}
}
```

Mail inquiries to cs61b@cory.eecs