<![CDATA[
CSE143 Sample Midterm handout #18
Winter 2006
1. Recursive Tracing, 15 points. Consider the following method:
public static int mystery(int x, int y) {
if (x < 0) {
return -mystery(-x, y);
} else if (y < 0) {
return -mystery(x, -y);
} else if (y < x) {
return 0;
} else {
return 1 + mystery(x, y - x);
}
}
For each call below, indicate what value is returned:
Method Call Value Returned
mystery(10, 28) _______________________________
mystery(5, 17) _______________________________
mystery(2, 10) _______________________________
mystery(4, -15) _______________________________
mystery(-3, -23) _______________________________
2. Recursive Programming, 15 points. Write a method printTwos that takes an
integer n as a parameter and that prints an expression composed of a single
odd number multiplied by twos that is equal to n. The twos should surround
the odd number with an equal number of twos on either side if possible. For
example, the call:
printTwos(80);
should produce the following output:
2 * 2 * 5 * 2 * 2
If the expression has an odd number of twos, then the "extra" two should
appear at the front of the expression. For example, the call:
printTwos(96);
should produce the following output:
2 * 2 * 2 * 3 * 2 * 2
If the number is odd to begin with, it should simply be printed. It is
possible that the odd number to print will be 1. For example, the following
calls:
printTwos(1);
System.out.println(); // to complete the line of output
printTwos(2);
System.out.println(); // to complete the line of output
printTwos(32);
System.out.println(); // to complete the line of output
should produce the following output:
1
2 * 1
2 * 2 * 2 * 1 * 2 * 2
You must exactly reproduce the format of the examples above. Your method
should throw an IllegalArgumentException if passed a value less than 1.
You may NOT use a while loop, for loop or do/while loop to solve this
problem; you must use recursion.
Write your solution to printTwos below.
3. Linked Lists, 15 points. Write a method hasTwoConsecutive that returns
whether or not a list of integers has two adjacent numbers that are
consecutive integers (returning true if such a pair exists and returning
false otherwise). For example, if a variable called list stores the
following sequence of values:
(1, 18, 2, 7, 8, 39, 18, 40)
then the call:
list.hasTwoConsecutive()
should return true because the list contains the adjacent numbers (7, 8)
which are a pair of consecutive numbers. If instead the list had stored
this sequence of values:
(1, 18, 17, 2, 7, 39, 18, 40, 8)
then the method should return false. This sequence contains some pairs of
numbers that could represent consecutive integers (e.g., 1 and 2, 7 and 8,
39 and 40), but those pairs of numbers are not adjacent in the sequence.
The list also has a pair of adjacent numbers (18, 17) that are not in the
right order to be considered consecutive.
You may not make any assumptions about how many elements are in the list.
Assume that we are using a linked list that stores integers, as discussed in
lecture (handouts 8 and 9).
public class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
<constructors>
}
public class LinkedIntList {
private ListNode front;
<methods>
}
You are writing a method that will become part of the LinkedIntList class.
You may not call any other methods of the class to solve this problem.
Write your solution to hasTwoConsecutive below.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Drink extends Bite {
public void method3() {
System.out.println("Drink 3");
}
}
public class Sip extends Gulp {
public void method1() {
System.out.println("Sip 1");
}
public void method3() {
System.out.println("Sip 3");
}
}
public class Bite extends Gulp {
public void method1() {
System.out.println("Bite 1");
}
public void method3() {
System.out.println("Bite 3");
super.method3();
}
}
public class Gulp {
public void method2() {
System.out.println("Gulp 2");
method3();
}
public void method3() {
System.out.println("Gulp 3");
}
}
And assuming the following variables have been defined:
Object var1 = new Bite();
Gulp var2 = new Gulp();
Gulp var3 = new Sip();
Bite var4 = new Drink();
Object var5 = new Gulp();
Gulp var6 = new Drink();
In the table below, indicate in the right-hand column the output produced by
the statement in the left-hand column. If the statement produces more than one
line of output, indicate the line breaks with slashes as in "a/b/c" to indicate
three lines of output with "a" followed by "b" followed by "c". If the
statement causes an error, fill in the right-hand column with either the phrase
"compiler error" or "runtime error" to indicate when the error would be
detected.
Statement Output
------------------------------------------------------------
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
var5.method3(); ____________________________
var6.method3(); ____________________________
((Sip)var6).method1(); ____________________________
((Gulp)var1).method1(); ____________________________
((Gulp)var1).method2(); ____________________________
((Bite)var1).method3(); ____________________________
((Bite)var6).method1(); ____________________________
((Drink)var1).method1(); ____________________________
((Drink)var4).method2(); ____________________________
((Bite)var3).method1(); ____________________________
5. Stacks/Queues, 25 points. Write a method rearrange that takes a Queue of
integers as a parameter and that rearranges the order of the values so that
all of the even values appear before the odd values and that otherwise
preserves the original order of the list. For example, suppose a Queue
called q stores this sequence of values:
front [3, 5, 4, 17, 6, 83, 1, 84, 16, 37] back
Then the following call:
rearrange(q);
should rearrange the order so that the queue stores the following sequence
of values:
front [4, 6, 84, 16, 3, 5, 17, 83, 1, 37] back
Notice that all of the evens appear at the front of the queue followed by
the odds and that the order of the evens is the same as in the original list
and the order of the odds is the same as in the original list.
You are to use one stack as auxiliary storage to solve this problem. You
may not use any other auxiliary data structures to solve this problem,
although you can have as many simple variables as you like. You also may
not solve the problem recursively.
In writing your method, assume that you are using the Stack and Queue
interfaces and the ArrayStack and LinkedQueue implementations discussed in
lecture. As a result, values will be stored as Integer objects, not ints.
If you are running short of time, you can receive 15 points for a solution
that puts all of the evens before the odds without preserving the original
order of the evens and the odds. Your method should take a single
parameter: the queue to rearrange.
Write your solution to rearrange below.
6. Array Programming, 10 points. Write a method runningTotal that returns a
new IntList that contains a running total of the original list. In other
words, the i-th value in the new list should store the sum of elements 0
through i of the original list. For example, if a variable list stores the
following sequence of values:
[2, 3, 5, 4, 7, 15, 20, 7]
and the following call is made:
IntList list2 = list.runningTotal();
Then the variable list2 should store the following sequence of values:
[2, 5, 10, 14, 21, 36, 56, 63]
The original list should not be changed by the method. The new list should
have the same capacity as the original. Remember that there is a
constructor for IntList that takes a capacity as a parameter:
// pre : capacity >= 0
// post: constructs an empty list with the given capacity
public IntList(int capacity)
If the original list is empty, the result should be an empty list.
You are writing a method for the IntList class discussed in lecture
(handouts 3 and 5):
public class IntList {
private int[] elementData; // list of integers
private int size; // current # of elements in the list
<methods>
}
You are not to call any IntList methods other than a constructor to solve
this problem and your method must run in O(n) time where n is the size of
the list.
Write your solution to runningTotal below.
]]>