<![CDATA[
Key to CSE143 Midterm, Fall 2012 handout #21
1. Method Call Output Produced
------------------------------------------------
mystery(1) 1
mystery(4) 1, 2, 4
mystery(16) 1, 2, 4, 8, 16
mystery(30) 1, 3, 7, 15, 30
mystery(100) 1, 3, 6, 12, 25, 50, 100
2. Two possible solutions appear below.
public int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else if (x < 10 || y < 10) {
if (x % 10 == y % 10)
return 1;
else
return 0;
} else if (x % 10 == y % 10)
return 1 + digitMatch(x / 10, y / 10);
else
return digitMatch(x / 10, y / 10);
}
public static int digitMatch(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else {
int count = 0;
if (x % 10 == y % 10)
count++;
if (x >= 10 && y >= 10)
count+= digitMatch(x / 10, y / 10);
return count;
}
}
before after code
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2] | p->[1] | q = p.next;
| | p.next = null;
q | q->[2] |
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2] | p->[2] | q = p;
| | p = p.next;
q | q->[1] | q.next = null;
| |
-----------------------+-----------------------+-------------------------------
| |
p->[1]->[2]->[3] | p->[1]->[4]->[2]->[5] | ListNode temp = q;
| | q = p.next.next;
q->[4]->[5] | q->[3] | p.next.next = temp.next;
| | temp.next = p.next;
| | p.next = temp;
| |
-----------------------+-----------------------+-------------------------------
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 static void compressDuplicates(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
if (!q.isEmpty()) {
int last = q.remove();
int count = 1;
while (!q.isEmpty()) {
int next = q.remove();
if (next == last)
count++;
else {
s.push(count);
s.push(last);
count = 1;
last = next;
}
}
s.push(count);
s.push(last);
}
}
6. One possible solution appears below.
public boolean isConsecutive() {
for (int i = 0; i < size - 1; i++)
if (elementData[i + 1] != elementData[i] + 1)
return false;
return true;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011