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


Problem 1. (6 points) Quickies.

a. The class with no superclass is Object.

b. An immutable object cannot be modified.


d. The class MyHouse will compile if implementations are provided for both prototypes of throughTheRoof (each of which takes a different parameter).

e. Binary search begins by inspecting the middle element of a list or sublist thereof. If the list is linked, you will have to traverse half the nodes in the list/sublist to reach the middle one. Assuming you start traversing from the left end, it will take binary search just as long to reach any given node as it would take a naive search.

Problem 2. (12 points) Bug Hunt.

The compile-time errors and their fixes are as follows.

The logical errors are both in DList.copyList. Problem 3. (7 points) Condensing Alternate Pairs of Strings in a Singly-Linked List.

public void condense() {
  SListNode n = head;
  while (n != null) {
    if (n.next != null) {
      n.item = (String) n.item + (String) n.next.item;
      n.next = n.next.next;
    n = n.next;

Mail inquiries to cs61b@cory.eecs