<![CDATA[
Key to CSE143 Midterm, Winter 2017 handout #17
1. Method Call Output Produced
------------------------------------------------
mystery(9); =9
mystery(42); 24=
mystery(703); 30=7
mystery(5821); 12=58
mystery(83105); 013=85
2. One possible solution appears below.
public int weave(int x, int y) {
if (x < 0 || y < 0) {
throw new IllegalArgumentException();
}
if (x == 0 && y == 0) {
return 0;
} else {
return 100 * weave(x / 10, y / 10) + 10 * (x % 10) + y % 10;
}
}
3. Statement Output
------------------------------------------------------------
var1.method1(); Cat 1
var2.method1(); Bell 1/Candle 1
var3.method1(); Bell 1/Candle 1
var1.method2(); Candle 2/Cat 1
var2.method2(); Book 2
var3.method2(); Candle 2/Bell 1/Candle 1
var4.method2(); compiler error
var5.method2(); Candle 2/Cat 1
var6.method2(); Book 2
var1.method3(); compiler error
var2.method3(); Book 3
var3.method3(); compiler error
((Cat)var5).method3(); Cat 3
((Bell)var1).method3(); compiler error
((Bell)var4).method1(); runtime error
((Cat)var1).method3(); Cat 3
((Candle)var4).method1(); Candle 1
((Book)var5).method3(); runtime error
((Bell)var6).method3(); compiler error
((Candle)var4).method2(); Candle 2/Candle 1
4. before after code
-----------------------+-----------------------+-------------------------------
p->[1] | p->[1]->[3] | p.next = q.next;
| | q.next = null;
q->[2]->[3] | q->[2] |
-----------------------+-----------------------+-------------------------------
p->[1] | p->[2]->[1] | ListNode temp = p;
| | p = q;
q->[2]->[3] | q->[3] | q = q.next;
| | p.next = temp;
-----------------------+-----------------------+-------------------------------
p->[1] | p->[1]->[3] | p.next = q.next;
| | q.next.next.next = q;
q->[2]->[3]->[4] | q->[4]->[2] | q = q.next.next;
| | q.next.next = null;
| | p.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2]->[4] | p.next.next = q.next;
| | q.next.next.next = q;
q->[3]->[4]->[5] | q->[5]->[3]->[1] | q.next = p;
| | q = p.next.next.next;
| | p = p.next;
| | p.next.next = null;
| | q.next.next.next = null;
-----------------------+-----------------------+-------------------------------
5. One possible solution appears below.
public void removeAll(int n) {
for (int i = 0; i < size; i++) {
if (elementData[i] == n) {
for (int j = i; j < size - 1; j++) {
elementData[j] = elementData[j + 1];
}
size--;
i--;
}
}
}
6. One possible solution appears below.
public void makeSortedSequence(Queue<Integer> q) {
Stack<Integer> s = new Stack<Integer>();
if (!q.isEmpty()) {
int last = q.remove();
s.push(last);
int oldSize = q.size();
for (int i = 0; i < oldSize; i++) {
int next = q.remove();
if (next < last) {
q.add(next);
} else {
s.push(next);
last = next;
}
}
while (!q.isEmpty()) {
s.push(q.remove());
}
while (!s.isEmpty()) {
q.add(s.pop());
}
while (!q.isEmpty()) {
s.push(q.remove());
}
while (!s.isEmpty()) {
q.add(s.pop());
}
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011