Key to CSE143 Midterm, Spring 2008 handout #22
1. Method Call Output Produced
-----------------------------------------------
mystery(3, 3); =3=
mystery(5, 1); *
mystery(1, 5); 5 4 =3= 2 1
mystery(2, 7); 7 6 5 * 4 3 2
mystery(1, 8); 8 7 6 5 * 4 3 2 1
2. One possible solution appears below.
public String repeat(String s, int n) {
if (n < 0)
throw new IllegalArgumentException();
else if (n == 0)
return "";
else if (n == 1)
return s;
else if (n % 2 == 0) {
String temp = repeat(s, n / 2);
return temp + temp;
// alternative without temp: return repeat(s + s, n / 2);
} else
return s + repeat(s, n - 1);
}
3. One possible solution appears below.
public void removeLast(int n) {
if (front != null) {
ListNode current = front;
ListNode spot = null;
while (current.next != null) {
if (current.next.data == n)
spot = current;
current = current.next;
}
if (spot != null)
spot.next = spot.next.next;
else if (front.data == n)
front = front.next;
}
}
4. Statement Output
------------------------------------------------------------
var1.method2() Box 2
var2.method2() Jar 2
var3.method2() Cup 2/Box 2
var4.method2() Jar 2
var5.method2() compiler error
var6.method2() Pill 2
var1.method3() Box 2/Box 3
var2.method3() compiler error
var3.method3() Cup 2/Box 2/Box 3
var4.method3() Jar 2/Box 3
((Cup)var1).method1() runtime error
((Jar)var2).method1() Jar 1
((Cup)var3).method1() Cup 1
((Cup)var4).method1() runtime error
((Jar)var4).method2() Jar 2
((Box)var5).method2() Box 2
((Pill)var5).method3() compiler error
((Jar)var2).method3() Jar 2/Box 3
((Cup)var3).method3() Cup 2/Box 2/Box 3
((Cup)var5).method3() runtime error
5. One possible solution appears below.
public void interleave(Queue q) {
if (q.size() % 2 != 0)
throw new IllegalArgumentException();
Stack s = new ArrayStack();
int halfSize = q.size() / 2;
for (int i = 0; i < halfSize; i++)
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
for (int i = 0; i < halfSize; i++)
q.enqueue(q.dequeue());
for (int i = 0; i < halfSize; i++)
s.push(q.dequeue());
while (!s.isEmpty()) {
q.enqueue(s.pop());
q.enqueue(q.dequeue());
}
}
6. One possible solution appears below.
public void removeOddPositions() {
size = (size + 1) / 2;
for (int i = 0; i < size; i++)
elementData[i] = elementData[2 * i];
}