CS 117, Fall 2001, Exam #2 (100 points)	Name:_____________________________

1. Short answer questions

(a) We have looked at two search algorithms: sequential search and binary search. 
Which one is faster, and why? (13 points)

(b) Can this faster algorithm always be used instead of the slower one? If not, why not? (12 points)

2. Multidimensional arrays

The following method takes as input a two-dimensional array that holds a gradebook. Each row (first subscript) corresponds to a student, and each column (second subscript) corresponds to a project. Fill in the code to write the average of each row to the file whose name is passed in as a parameter. (25 points)

Here are the declarations for opening up a file for writing:

File dstFile = new File("K:\\location\\...\\filename");
PrintWriter out = new PrintWriter(new BufferedWriter
   (new FileWriter(dstFile)));

You may modify the following method header if you wish:

public void writeRowAverages(double[][] gradebook,
                             String filename)
{

continue in the back or on the last page of this exam if necessary

3. Recursion

(a) What does the following program output? Show your work for partial credit. (22 points)

Output:
class Problem3
{
  public int mystery(int number)
  {
    if (number == 1)
      return 0;

    return (1 + mystery(number / 2));
  }
}	

class Problem3Main
{
  public static void main(String[] args)
  {
    Problem3 prob = new Problem3();
    System.out.println(prob.mystery(4));
    System.out.println(prob.mystery(8));
    System.out.println(prob.mystery(16));
    System.out.println(prob.mystery(15));
    System.out.println(prob.mystery(9));
  }
}

(b) What is the actual purpose of this method? (What is it for?) (3 points)

4. Linked Lists

Consider the following class:

class CS117LinkedList
{
  class Node
  {
    private int data;
    private Node next;
  }

  // Data values
  private Node head;

  // ... Constructor and lots of other methods here ...

  public int enigmaMethod()
  {
    int n = 0;

    Node current = head;
    while (current != null)
    { 
      n++;
      current = current.next;
    }
    return n;
  }
}

(a) What is the purpose of enigmaMethod? Show a state of memory diagram with an example to illustrate. (11 points)

(b) Modify enigmaMethod to return the product of the data in all the nodes in the linked list. Make your changes right in the code on the previous page. (11 points)

(c) What value does enigmaMethod now return if the list is empty? (3 points)

___________________________________________________________________________
Additional scrap work: