<![CDATA[
Key to CSE143 Midterm, Autumn 2014 handout #21
1. Method Call Output Produced
------------------------------------------------
mystery(1); 1
mystery(3); 3, 10, 5, 16, 8, 4, 2, 1
mystery(4); 4, 2, 1
mystery(5); 5, 16, 8, 4, 2, 1
mystery(20); 20, 10, 5, 16, 8, 4, 2, 1
2. One possible solution appears below.
public static String collapseSequences(String s, char ch) {
if (s.length() < 2) {
return s;
} else {
char first = s.charAt(0);
if (first == ch && first == s.charAt(1)) {
return collapseSequences(s.substring(1), ch);
} else {
return s.charAt(0) + collapseSequences(s.substring(1), ch);
}
}
}
3. Statement Output
------------------------------------------------------------
var1.method1(); Soap 1/Dish 3/Soap 3
var2.method1(); Soap 1/Fork 3
var3.method1(); Soap 1/Bowl 3
var4.method1(); Soap 1/Fork 3
var5.method1(); Soap 1/Soap 3
var6.method1(); compiler error
var1.method2(); compiler error
var2.method2(); Fork 2
var3.method2(); compiler error
var1.method3(); Dish 3/Soap 3
var2.method3(); Fork 3
var3.method3(); Bowl 3
((Fork)var6).method1(); runtime error
((Dish)var3).method2(); compiler error
((Fork)var4).method2(); Fork 2
((Fork)var3).method2(); runtime error
((Bowl)var3).method2(); Bowl 2
((Fork)var1).method1(); runtime error
((Dish)var4).method3(); Fork 3
((Soap)var6).method3(); Dish 3/Soap 3
4. before after code
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[1]->[2] | q = p.next.next;
| | p.next.next = null;
q | q->[3] |
-----------------------+-----------------------+-------------------------------
p->[1]->[3] | p->[1]->[2]->[3] | q.next = p.next;
| | p.next = q;
q->[2] | q | q = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next = p;
q->[3]->[4] | q->[3]->[1] | p = p.next;
| | q.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2]->[3] | p->[2]->[1]->[4] | p.next.next.next = q.next;
| | ListNode temp = q;
q->[4]->[5] | q->[3]->[5] | q = p.next.next;
| | p.next.next = p;
| | p = p.next;
| | p.next.next = temp;
| | temp.next = null;
-----------------------+-----------------------+-------------------------------
5. One possible solution appears below.
public static int parityMatches(Stack<Integer> s1, Stack<Integer> s2) {
if (s1.size() != s2.size()) {
throw new IllegalArgumentException();
}
Queue<Integer> q = new LinkedList<Integer>();
int count = 0;
while (!s1.isEmpty()) {
int num1 = s1.pop();
int num2 = s2.pop();
if (num1 % 2 == num2 % 2)
count++;
q.add(num1);
q.add(num2);
}
while (!q.isEmpty())
s1.push(q.remove());
while (!s1.isEmpty())
q.add(s1.pop());
while (!q.isEmpty()) {
s2.push(q.remove());
s1.push(q.remove());
}
return count;
}
6. Two possible solutions appear below.
public void stutter() {
for (int i = size - 1; i >= 0; i--) {
elementData[2 * i + 1] = elementData[i];
elementData[2 * i] = elementData[i];
}
size *= 2;
}
public void stutter() {
size *= 2;
for (int i = size - 1; i >= 0; i--) {
elementData[i] = elementData[i / 2];
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011