<![CDATA[
Key to CSE143 Sample Midterm, Autumn 2004 handout #21
1. Recursive Tracing. The output produced is as follows:
Method Call Output Produced
----------------------------------------
mystery(113) 113
mystery(70) 140, 70
mystery(42) 168, 84, 42
mystery(30) 120, 60, 30
mystery(10) 160, 80, 40, 20, 10
2. Recursive Programming. One possible solution appears below.
public void writeNums(int n) {
if (n < 1)
throw new IllegalArgumentException();
else if (n == 1)
System.out.print(1);
else {
writeNums(n - 1);
System.out.print(", " + n);
}
}
3. Linked Lists. One possible solution appears below.
public int evenSum() {
int sum = 0;
boolean even = true;
ListNode current = front;
while (current != null) {
if (even)
sum += current.data;
even = !even;
current = current.next;
}
return sum;
}
4. Details of Inheritance. The output produced is as follows.
Statement Output
--------------------------------------------------
var1.method1(); Frodo 1/Bilbo 1
var2.method1(); Bilbo 1
var3.method1(); Gandalf 1
var4.method1(); compiler error
var5.method1(); Frodo 1/Bilbo 1
var6.method1(); compiler error
var1.method2(); Gandalf 2/Frodo 1/Bilbo 1
var2.method2(); Gandalf 2/Bilbo 1
var3.method2(); Gandalf 2/Gandalf 1
var4.method2(); compiler error
var5.method2(); Gandalf 2/Frodo 1/Bilbo 1
var6.method2(); compiler error
((Bilbo)var1).method3(); compiler error
((Gandalf)var1).method2(); Gandalf 2/Frodo 1/Bilbo 1
((Frodo)var4).method1(); runtime error
((Gandalf)var6).method2(); Gandalf 2/Gandalf 1
((Gandalf)var4).method1(); Bilbo 1
((Frodo)var6).method3(); runtime error
((Frodo)var3).method3(); runtime error
((Frodo)var5).method3(); Frodo 3
5. Stacks/Queues. One possible solution appears below.
public static void collapse(Stack<Integer> s) {
Queue<Integer> q = new LinkedQueue<Integer>();
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
while (q.size() > 1)
s.push(q.dequeue() + q.dequeue());
if (!q.isEmpty())
s.push(q.dequeue());
}
6. Array Programming. One possible solution appears below.
public int longestSortedSequence() {
if (size == 0)
return 0;
int max = 1;
int current = 1;
for (int i = 1; i < size; i++)
if (elementData[i] >= elementData[i - 1]) {
current++;
if (current > max)
max = current;
} else
current = 1;
return max;
}
]]>