CSC 122: Computer Science II, Spring 2006

Exam 2 Sample Questions

1. For this problem you are to implement a rational number abstract data type as a Java class according to the following characteristics:

   1. The name of the class is Rational.
   2. There are two int instance variables (fields) called numerator and denominator (representing the fraction numerator/denominator).
   3. The methods of the class are:
      • a constructor which initializes a rational number to 0/1
      • void display() which displays the rational number as numerator / denominator
      • void assign(int x, int y) where x will be the numerator value and y will be the denominator value, with the precondition that y cannot be zero (i.e., you need not worry about zero in the denominator)
      • boolean invert() which returns false if the original numerator is zero and otherwise swaps the numerator and denominator and returns true
      • void mult( rational p ) which multiplies the owner by p and stores the product in the owner. In case you forgot, 1/6 x 2/5 = 2/30. For extra credit, store the result in reduced form (e.g., 1/15).

   public class Rational
   {
       private int numerator;
       private int denominator;
       
       public Rational()
       {
           // initialise instance variables
           numerator = 0;
           denominator = 1;
       }
   
       public void display()
       {
           System.out.println(numerator + "/" + denominator);
       }
   
       public void assign(int x, int y)
       {
           numerator = x;
           denominator = y;
       }
       
       public boolean invert()
       {
           if (numerator == 0) {
               return false;
           }
           else {
               int tmp = numerator;
               numerator = denominator;
               denominator = tmp;
               return true;
           }
       }
       
       public void mult(Rational p)
       {
           numerator = numerator * p.numerator;
           denominator = denominator * p.denominator;
           // No extra credit here
       }
   }
   
   				

2. Consider the following Haskell function:

   mystery([ ],[ ]) = true
   mystery([ ],[h:t]) = false
   mystery([h:t],[ ]) = false
   mystery([h1:t1],[h2:t2]) = mystery(t1,t2)
   				

   1. What value is returned by mystery([ ],[ ])?
      true
   2. What value is returned by mystery(['a', 'b'], ['d', 'e'])?
      true
   3. What value is returned by mystery(['a', 'b'], ['d'])?
      false
   4. In a sentence, describe what function mystery computes.
      It determines if the two lists are equal in length.

3. Consider the following Haskell function:

   test(32)=0
   test(x) = 1 + test(2*x)
   				

   What is returned by each of the following?

   1. test(16)
      1
   2. test(4)
      3
   3. test(33)
      never terminates

4. Write a Haskell function, addup, which adds the first n integers. For example addup(3) would evaluate to 6.

   addup(0) = 0
   addup(n) = n + addup(n - 1)
   				

5. In one or two sentences, define what is meant by Abstract Data Type.
   See the text book.

6. Consider the following definitions:

   private Listcell myRef;
   
   private class Listcell {
       private char data;
       private Listcell next;
   }
   
   void fooAux(String str, int i, Listcell prevFront) {
       if (i == str.length()) {
           return;
       } else {
           Listcell tmp = new Listcell();
           tmp.data = str.charAt(i);
           tmp.next = prevFront;
           myRef = tmp;
           fooAux(str, i+1, myRef);
       }
   }
   
   void foo(String str) {
       myRef = null;
       fooAux(str, 0, myRef);
   }
   				

   1. What is the result of the call foo("cat hat");
      A linked list, myRef --> t --> a --> h -->   --> t --> a --> c
   2. Describe what foo does in one sentence.
      Foo generates a singly-linked list from a String where the characters of the string are linked in reverse order.
   3. Rewrite foo so that it accomplishes its task using iteration.

      void foo(String str)
      {
          myRef = null;
          for (int i = 0; i < str.length(); i++) {
              Listcell tmp = new Listcell();	
              tmp.data = str.charAt(i);
              tmp.next = myRef;
              myRef = tmp;
          }
      }
      					

7. Given the doubly linked list node definition

   private class Node {
       int elem;
       Node next;
       Node prev;
   }
   				

   write a code fragment which will delete the node referenced by p if that node has a node to its left (prev) and right (next).

   p.prev.next = p.next;
   p.next.prev = p.prev;
   				

8. List one advantage of a linked list implementation of a queue over an array implementation.

   It will grow and shrink according to the number of items in the queue.

Questions, short answer and otherwise, could also be asked about the following topics:

• Backtracking
• Stacks and stack applications (backtracking, recursion, method calls)
• Queues
• Memory management – garbage collection

DePauw University, Computer Science Department, Spring 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated