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).

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([ ],[ ])?
   2. What value is returned by mystery(['a', 'b'], ['d', 'e'])?
   3. What value is returned by mystery(['a', 'b'], ['d'])?
   4. In a sentence, describe what function mystery computes.

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)
   2. test(4)
   3. test(33)

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

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

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");
   2. Describe what foo does in one sentence.
   3. Rewrite foo so that it accomplishes its task using iteration.

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).

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

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