Key to CSE143 Midterm, Spring 2008 handout #22 1. Method Call Output Produced ----------------------------------------------- mystery(3, 3); =3= mystery(5, 1); * mystery(1, 5); 5 4 =3= 2 1 mystery(2, 7); 7 6 5 * 4 3 2 mystery(1, 8); 8 7 6 5 * 4 3 2 1 2. One possible solution appears below. public String repeat(String s, int n) { if (n < 0) throw new IllegalArgumentException(); else if (n == 0) return ""; else if (n == 1) return s; else if (n % 2 == 0) { String temp = repeat(s, n / 2); return temp + temp; // alternative without temp: return repeat(s + s, n / 2); } else return s + repeat(s, n - 1); } 3. One possible solution appears below. public void removeLast(int n) { if (front != null) { ListNode current = front; ListNode spot = null; while (current.next != null) { if (current.next.data == n) spot = current; current = current.next; } if (spot != null) spot.next = spot.next.next; else if (front.data == n) front = front.next; } } 4. Statement Output ------------------------------------------------------------ var1.method2() Box 2 var2.method2() Jar 2 var3.method2() Cup 2/Box 2 var4.method2() Jar 2 var5.method2() compiler error var6.method2() Pill 2 var1.method3() Box 2/Box 3 var2.method3() compiler error var3.method3() Cup 2/Box 2/Box 3 var4.method3() Jar 2/Box 3 ((Cup)var1).method1() runtime error ((Jar)var2).method1() Jar 1 ((Cup)var3).method1() Cup 1 ((Cup)var4).method1() runtime error ((Jar)var4).method2() Jar 2 ((Box)var5).method2() Box 2 ((Pill)var5).method3() compiler error ((Jar)var2).method3() Jar 2/Box 3 ((Cup)var3).method3() Cup 2/Box 2/Box 3 ((Cup)var5).method3() runtime error 5. One possible solution appears below. public void interleave(Queue<Integer> q) { if (q.size() % 2 != 0) throw new IllegalArgumentException(); Stack<Integer> s = new ArrayStack<Integer>(); int halfSize = q.size() / 2; for (int i = 0; i < halfSize; i++) s.push(q.dequeue()); while (!s.isEmpty()) q.enqueue(s.pop()); for (int i = 0; i < halfSize; i++) q.enqueue(q.dequeue()); for (int i = 0; i < halfSize; i++) s.push(q.dequeue()); while (!s.isEmpty()) { q.enqueue(s.pop()); q.enqueue(q.dequeue()); } } 6. One possible solution appears below. public void removeOddPositions() { size = (size + 1) / 2; for (int i = 0; i < size; i++) elementData[i] = elementData[2 * i]; }
Stuart Reges
Last modified: Wed May 14 17:14:19 PDT 2008