CMPS 144 Spring 2026
Test #2 Sample Solutions

1. Two solutions are offered, the first of which uses a single cursor: 

/* Between any two nodes containing the same non-zero value, 
** inserts a new node containing zero.  
** Example: Suppose list is [5, 3, 3, 3, 7, 5, 5, 0, 0].
**   Then the effect is to change it to 
**   [5, 3, 0, 3, 0, 3, 7, 5, 0, 5, 0, 0],
*/
public static void splitDuplicates(ListWithCursors<Integer> list) {
   if (list.lengthOf() < 2) {
      // there is nothing to do
   }
   else {
      ListCursor<Integer> cursor = list.getCursor();
      cursor.toFront();
      int prevVal = cursor.getItem();
      while (!cursor.atRear()) {
         int currentVal = cursor.getItem();
         if (currentVal != 0 && currentVal == prevVal) {
            cursor.insert(0);
         }
         prevVal = currentVal;
         cursor.toNext();
      }
   }
   cursor.dispose();
}

The second solution uses two cursors: 
/* Comments omitted.
*/
public static void splitDuplicates(ListWithCursors<Integer> list) {
   if (list.lengthOf() < 2) {
      // there is nothing to do
   }
   else {
      // Place cursors at the first two nodes of the list.
      ListCursor<Integer> current = list.getCursor();
      current.toFront().toNext();
      ListCursor<Integer> prev = list.getCursor();
      prev.toFront();

      while (!current.atRear()) {
         int prevVal = prev.getItem();
         int currentVal = current.getItem();
         prev.toNext(); // Now prev is at same place as current
         if (currentVal != 0 && currentVal == prevVal) {
            current.insert(0);
         }
         current.toNext();
      }
      prev.dispose();
      current.dispose();
   }
}

In hindsight, the method should have had as a precondition that the list had at least two elements (or at least that it was not empty). But students' code assumed that anyway!

2.
Breadth-first
tree 
       2
      / \
     /   \
    /     \
   /       \
  7         8
 / \       / \
4   9     3   6
    |    / \
    5   1   11
    |
    0
            +---+---+---+---+---+---+---+---+---+----+---+
            | 2 | 7 | 8 | 4 | 9 | 3 | 6 | 5 | 1 | 11 | 0 |
            +---+---+---+---+---+---+---+---+---+----+---+

Enqueued at | 1 | 3 | 4 | 6 | 7 | 9 |10 |13 |15 |16  |19 |
            |   |   |   |   |   |   |   |   |   |    |   |
Dequeued at | 2 | 5 | 8 |11 |12 |14 |17 |18 |20 |21  |22 |


       0   1   2   3   4   5   6   7   8   9   10   11
     +---+---+---+---+---+---+---+---+---+---+----+----+
dist | 4 | 3 | 0 | 2 | 2 | 3 | 2 | 1 | 1 | 2 | -1 |  3 |
     +---+---+---+---+---+---+---+---+---+---+----+----+

3. Code needing to be inserted by student is in boldface. 

//RWM: Next line was incorrectly omitted on test.
import java.util.Comparator;  

public class CompareIntPairBySum implements Comparator<PairOfInt> {

   /* Returns a value that's negative, zero, or positive, respectivly,
   ** according to whether the sum of pairA's components is less than,
   ** equal to, or greater than the sum of pairB's components.
   */
   public int compare(PairOfInt pairA, PairOfInt pairB) {
      int sumA = pairA.first + pairA.second;
      int sumB = pairB.first + pairB.second;
      return sumA - sumB;
      // alternative to line above:
      // if (sumA < sumB) { return -1; }
      // else if (sumA > sumB) { return 1; }
      // else { return 0; }

import java.util.Comparator;

public class SortIntPairs {

   /* Uses an instance of the Sorter class to sort the given array
   ** into ascending order consistent with the ordering defined by
   ** the CompareIntPairBySum class.
   */
   public static void sortPairsBySum(PairOfInt[] a) {

      Comparator c = new CompareIntPairBySum();

      // Here insert code that creates an instance of the Sorter 
      // class and uses it to sort the elements of a[] as indicated.
      // Keep in mind that Sorter is a generic class.

      Sorter<PairOfInt> sorter = new Sorter(c);
      sorter.sort(a);
   }
}

4. This was, for almost every student, the most difficult problem in the exam.

The first iteration of the loop begins (as indicated in the instructions) with p referring to (or "pointing at") the 3-node (i.e., the node containing 3).

Here's what happens during the first loop iteration:

So the overall effect of the first loop iteration is two-fold:

  1. p has advanced two positions "forward", from the 3-node to the 1-node.
  2. The next field of the 8-node (the successor of the node originally pointed to by p) now points "backwards" to the 3-node (the node originally pointed to by p).

Each subsequent loop iteration continues this pattern, in which p advances two positions and the next field of the node that had been the successor of the one pointed to by p when the iteration began now points "backwards" to the node that had been pointed to by p.

So the overall effect of the loop's three iterations is to make the 8-node point back to the 3-node, the 6-node to point back to the 1-node, and the 5-node to point back to the 0-node.

The code would crash if applied to a chain of Link1 nodes of odd length, because during the last iteration the assignment q = p.next would result in q having "value" null and the subsequent assignment r = q.next would fail, as you cannot access the next field from null.

5. The next four events to happen are these:

  1. Customer 10 finishes at time 23, resulting in that customer being transferred from "being served" to "finished".
  2. The previous event having opened up a slot for a customer to be serviced, Customer 14 is transferred from the queue to "being served" (at time 23) and now has finish time 26.
  3. Customer 17 arrives and is placed into the queue at time 24.
  4. If the next customer's (#18) Arrival Time (which was free to be chosen by the student) is less than 26, Customer 18 is placed into the queue. (Of course, that arrival time could be no less than 24, due to that being Customer 17's Arrival Time.)

    Otherwise, Customer 14 finishes at time 26 and is transferred to the list of finished customers.

Perhaps the instructions should have emphasized more strongly that each state shown was to be the result of a single event occurring, as several students packed two or three events into each "change-of-state".

6. For the instructor's convenience, in the figure below the symbols v, ^, and - are used in place of, respectively, ∨, ∧, and ¬ 

|   | |   |    |   | |   |     |   | |   |    |   | |   |     |   | |   |
| T | |   |    |   | |   |     |   | |   |    |   | |   |     | T | | ^ |
| F | | ^ |    | F | |   |     | F | |   |    |   | |   |     | F | | - |
| F | | v |    | F | | v |     | F | | v |    | F | |   |     | F | | v |
+---+ +---+    +---+ +---+     +---+ +---+    +---+ +---+     +---+ +---+
before 1st      after 1st      before 2nd      after 2nd      before 3rd

|   | |   |    |   | |   |     |   | |   |    |   | |   |     |   | |   |
|   | |   |    |   | |   |     |   | |   |    |   | |   |     |   | |   |
| F | | - |    | F | | - |     | T | |   |    | T | |   |     |   | |   |
| F | | v |    | F | | v |     | F | | v |    | F | | v |     | T | |   |
+---+ +---+    +---+ +---+     +---+ +---+    +---+ +---+     +---+ +---+
 after 3rd     before 4th       after 4th     before 5th       after 5th