<![CDATA[
Key to Sample CSE143 Midterm, Spring 2008 handout #20
1. Method Call Output Produced
-----------------------------------------------
mystery(13); 13
mystery(42); 42, 21
mystery(40); 40, 20, 10, 5
mystery(60); 60, 30, 15
mystery(48); 48, 24, 12, 6, 3
2. One possible solution appears below.
public int indexOf(String source, String target) {
if (target.length() > source.length())
return -1;
else if (source.substring(0, target.length()).equals(target))
return 0;
else {
int pos = indexOf(source.substring(1), target);
if (pos == -1)
return pos;
else
return pos + 1;
}
}
3. One possible solution appears below.
public boolean hasAlternatingParity() {
if (front != null) {
ListNode current = front;
while (current.next != null) {
if (current.data % 2 == current.next.data % 2)
return false;
current = current.next;
}
}
return true;
}
4. Statement Output
------------------------------------------------------------
var1.method2(); Pen 2
var2.method2(); Stapler 2
var3.method2(); Stapler 2
var4.method2(); Paper 2
var5.method2(); compiler error
var6.method2(); Clip 2/Paper 2
var1.method1(); compiler error
var2.method1(); Stapler 1
var3.method1(); compiler error
var1.method3(); Paper 3/Pen 2
var2.method3(); Paper 3/Stapler 2
var3.method3(); Paper 3/Stapler 2
var4.method3(); Paper 3/Paper 2
((Pen)var1).method1(); Pen 1
((Stapler)var3).method1(); Stapler 1
((Clip)var3).method3(); Paper 3/Stapler 2
((Clip)var5).method1(); compiler error
((Pen)var5).method1(); runtime error
((Clip)var6).method2(); Clip 2/Paper 2
((Stapler)var6).method3(); runtime error
5. One possible solution appears below.
public int removeMin(Stack<Integer> s) {
if (s.isEmpty())
throw new IllegalArgumentException();
Queue<Integer> q = new LinkedQueue<Integer>();
int min = s.pop();
q.enqueue(min);
while (!s.isEmpty()) {
int next = s.pop();
if (next < min)
min = next;
q.enqueue(next);
}
while (!q.isEmpty()) {
int next = q.dequeue();
if (next != min)
s.push(next);
}
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
return min;
}
6. One possible solution appears below.
public void collapse() {
for (int i = 0; i < size / 2; i++)
elementData[i] = elementData[2 * i] + elementData[2 * i + 1];
if (size % 2 == 0)
size = size / 2;
else {
elementData[size / 2] = elementData[size - 1];
size = size / 2 + 1;
}
}
]]>