<![CDATA[
Key to CSE143 Midterm, Fall 2010 handout #20
1. Method Call Value Returned
-----------------------------------------------
mystery(18, 0) 0
mystery(8, 18) 1
mystery(25, 21) 1
mystery(305, 315) 2
mystery(20734, 1724) 2
2. One possible solution appears below.
public static boolean isPalindrome(String s) {
if (s.length() <= 1)
return true;
else
return s.charAt(0) == s.charAt(s.length() - 1) &&
isPalindrome(s.substring(1, s.length() - 1));
}
3. One possible solution appears below.
public int numUnique() {
if (front == null)
return 0;
else {
int count = 1;
ListNode current = front;
while (current.next != null) {
if (current.data != current.next.data)
count++;
current = current.next;
}
return count;
}
}
4. Statement Output
------------------------------------------------------------
var1.method2(); compiler error
var2.method2(); Bunch 2/Bunch 3
var3.method2(); Bunch 2/Bit 3
var4.method2(); Bunch 2/Page 3
var5.method2(); compiler error
var6.method2(); Bunch 2/Page 3
var1.method3(); compiler error
var2.method3(); Bunch 3
var3.method3(); Bit 3
var4.method3(); Page 3
var5.method3(); compiler error
var6.method3(); Page 3
((Bit)var6).method1(); runtime error
((Bunch)var1).method1(); compiler error
((Bunch)var1).method2(); Bunch 2/Folder 3/Bunch 3
((Folder)var1).method3(); Folder 3/Bunch 3
((Folder)var6).method1(); Folder 1
((Page)var1).method1(); runtime error
((Page)var4).method2(); Bunch 2/Page 3
((Folder)var3).method1(); runtime error
5. One possible solution appears below.
public int removeMax(Stack<Integer> s) {
if (s.isEmpty())
throw new IllegalArgumentException();
Queue<Integer> q = new LinkedQueue<Integer>();
int max = s.pop();
q.enqueue(max);
while (!s.isEmpty()) {
int next = s.pop();
if (next > max)
max = next;
q.enqueue(next);
}
while (!q.isEmpty()) {
int next = q.dequeue();
if (next != max)
s.push(next);
}
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
return max;
}
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;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011