<![CDATA[
Key to CSE143 Sample Midterm, Spring 2004 handout #18
1. Recursive Tracing. The output produced is as follows:
Method Call Output Produced
---------------------------------------
mystery(0) *
mystery(1) [*]
mystery(2) ([*])
mystery(4) ([([*])])
mystery(5) [([([*])])]
2. Recursive Programming. One possible solution appears below.
public void writeChars(int n) {
if (n < 1)
throw new IllegalArgumentException();
else if (n == 1)
System.out.print("*");
else if (n == 2)
System.out.print("**");
else {
System.out.print("<");
writeChars(n - 2);
System.out.print(">");
}
}
3. Linked Lists. One possible solution appears below.
public int min() {
if (front == null)
return 0;
else {
int min = front.data;
ListNode current = front.next;
while (current != null) {
if (current.data < min)
min = current.data;
current = current.next;
}
return min;
}
}
4. Details of Inheritance. The output produced is as follows.
Statement Output
--------------------------------------------------
var1.method2(); Fo 2/Fie 3/Fum 3
var2.method2(); compiler error
var3.method2(); Fo 2/Fee 3
var4.method2(); compiler error
var5.method2(); compiler error
var6.method2(); Fo 2/Fum 3
var1.method3(); Fie 3/Fum 3
var2.method3(); compiler error
var3.method3(); Fee 3
var4.method3(); compiler error
var5.method3(); compiler error
var6.method3(); Fum 3
((Fee)var3).method1(); Fee 1/Fo 3
((Fee)var4).method1(); runtime error
((Fie)var1).method2(); Fo 2/Fie 3/Fum 3
((Fo)var3).method3(); Fee 3
((Fie)var6).method2(); runtime error
((Fo)var2).method3(); Fum 3
((Fie)var3).method1(); runtime error
((Fo)var5).method2(); Fo 2/Fo 3
5. Stacks/Queues. One possible solution appears below.
public void reverseHalf(Queue q) {
Stack s = new ArrayStack();
int oldLength = q.size();
// transfer elements in even spots to stack
for (int i = 1; i <= oldLength; i++)
if (i % 2 == 1)
q.enqueue(q.dequeue());
else
s.push(q.dequeue());
// reconstruct list, taking alternately from queue and stack
for (int i = 1; i <= oldLength; i++)
if (i % 2 == 1)
q.enqueue(q.dequeue());
else
q.enqueue(s.pop());
}
6. Array Programming. One possible solution appears below.
public void stretch(int n) {
if (n < 0)
throw new IllegalArgumentException();
for (int i = size - 1; i >= 0; i--)
for (int j = 0; j < n; j++)
elementData[i * n + j] = elementData[i];
size *= n;
}
]]>