<![CDATA[
Key to CSE143 Midterm, Winter 2014 handout #21
1. Method Call Output Produced
------------------------------------------------
mystery(7); 7
mystery(38); 838
mystery(194); 49194
mystery(782); 28782
mystery(3842); 2483842
2. One possible solution appears below.
public void showSplit(int n) {
if (n < 0) {
throw new IllegalArgumentException();
} else if (n <= 1) {
System.out.print(n);
} else {
System.out.print(n + " = (");
showSplit(n / 2 + n % 2);
System.out.print(", ");
showSplit(n / 2);
System.out.print(")");
}
}
3. before after code
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[2] | q.next = p;
| | p = p.next;
| | q.next.next = null;
q->[3] | q->[3]->[1] |
-----------------------+-----------------------+-------------------------------
p->[1] | p->[3] | p.next = q;
| | q = p;
| | p = p.next.next;
q->[2]->[3] | q->[1]->[2] | q.next.next = null;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[3]->[2]->[1] | p.next.next = p;
| | ListNode temp = q.next;
| | q.next = p.next;
q->[3]->[4] | q->[4] | p.next = null;
| | p = q;
| | q = temp;
-----------------------+-----------------------+-------------------------------
p->[1]->[2] | p->[1]->[3]->[5] | ListNode temp = p.next;
| | p.next = q;
| | temp.next = q.next;
q->[3]->[4]->[5] | q->[2]->[4] | q.next = q.next.next;
| | q = temp;
| | q.next.next = null;
-----------------------+-----------------------+-------------------------------
4. Statement Output
------------------------------------------------------------
var1.method2(); Neck 2
var2.method2(); Leg 2
var3.method2(); Leg 2
var4.method2(); compiler error
var5.method2(); Head 2
var6.method2(); Neck 2
var1.method3(); Arm 3/Neck 2
var2.method3(); compiler error
var3.method3(); compiler error
var4.method3(); compiler error
var5.method3(); Arm 3/Head 2
var6.method3(); Arm 3/Neck 2
((Neck)var5).method1(); runtime error
((Arm)var3).method3(); Arm 3/Leg 2
((Arm)var4).method1(); compiler error
((Neck)var1).method1(); Head 1/Leg 2
((Head)var4).method1(); Head 1/Leg 2
((Arm)var2).method3(); runtime error
((Head)var3).method1(); runtime error
((Leg)var4).method2(); Head 2
5. One possible solution appears below.
public void rearrangeDuplicates(Queue<Integer> q) {
Stack<Integer> s = new Stack<Integer>();
if (q.size() > 1) {
int oldSize = q.size();
int prev = q.remove();
q.add(prev);
for (int i = 0; i < oldSize - 1; i++) {
int n = q.remove();
if (n != prev)
q.add(n);
else
s.push(n);
prev = n;
}
int newCount = q.size();
while (!s.isEmpty())
q.add(s.pop());
for (int i = 0; i < newCount; i++)
q.add(q.remove());
for (int i = 0; i < oldSize - newCount; i++)
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
}
}
6. One possible solution appears below.
public void removeLast(int n) {
int index = -1;
for (int i = 0; i < size; i++) {
if (elementData[i] == n) {
index = i;
}
}
if (index != -1) {
for (int j = index; j < size - 1; j++) {
elementData[j] = elementData[j + 1];
}
size--;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011