<![CDATA[
Key to CSE143 Midterm, Spring 2013 handout #21
1. Method Call Output Produced
------------------------------------------------
mystery(4, 1); 4
mystery(4, 2); 8, 4, 8
mystery(8, 2); 16, 8, 16
mystery(4, 3); 12, 8, 4, 8, 12
mystery(3, 4); 12, 9, 6, 3, 6, 9, 12
2. One possible solution appears below.
public boolean sameDashes(String s1, String s2) {
if (s1.length() != s2.length()) {
throw new IllegalArgumentException();
} else if (s1.length() == 0 && s2.length() == 0) {
return true;
} else if (s1.charAt(0) == '-' || s2.charAt(0) == '-') {
return s1.charAt(0) == s2.charAt(0) &&
sameDashes(s1.substring(1), s2.substring(1));
} else {
return sameDashes(s1.substring(1), s2.substring(1));
}
}
3. before after code
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2]->[3] | p->[1]->[3] | q = p.next;
| | p.next = p.next.next;
| | q.next = null;
q | q->[2] |
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[3] | p->[1]->[2]->[3] | q.next = p.next;
| | p.next = q;
| | q = null;
q->[2] | q |
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next = p;
| | p = p.next;
q->[3]->[4] | q->[3]->[1] | q.next.next = null;
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2]->[3] | p->[3]->[1]->[5] | p.next.next.next = p;
| | ListNode temp = q.next;
| | q.next = p.next;
q->[4]->[5] | q->[4]->[2] | p.next = temp;
| | p = q.next.next;
| | q.next.next = null;
| |
-----------------------+-----------------------+-------------------------------
4. Statement Output
------------------------------------------------------------
var1.method1(); Wall 1
var2.method1(); Dragon 1/Raven 1
var3.method1(); Raven 1
var4.method1(); compiler error
var5.method1(); Wall 1
var6.method1(); compiler error
var1.method2(); Raven 2/Wall 1
var2.method2(); Raven 2/Dragon 1/Raven 1
var3.method2(); Raven 2/Raven 1
var4.method2(); compiler error
var5.method2(); Raven 2/Wall 1
var6.method2(); compiler error
((Dragon)var1).method3(); compiler error
((Hand)var6).method3(); Hand 3
((Wall)var4).method1(); runtime error
((Raven)var6).method2(); Raven 2/Raven 1
((Raven)var4).method1(); Dragon 1/Raven 1
((Wall)var6).method3(); runtime error
((Wall)var3).method3(); runtime error
((Wall)var5).method3(); Wall 3
5. One possible solution appears below.
public boolean isSorted(Stack<Integer> s) {
if (s.size() <= 1)
return true;
else {
Queue<Integer> q = new LinkedList<Integer>();
int prev = s.pop();
q.add(prev);
boolean ok = true;
while (!s.isEmpty()) {
int next = s.pop();
if (prev < next)
ok = false;
q.add(next);
prev = next;
}
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
return ok;
}
}
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