Key to CSE143 Sample Midterm, Summer 2008 handout #17 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 &lt; 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 transferFrom(LinkedIntList other) { if (front == null) front = other.front; else { ListNode current = front; while (current.next != null) current = current.next; current.next = other.front; } other.front = null; } 4. 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; } } 5. One possible solution appears below. public void interleave(Queue&lt;Integer&gt; q) { if (q.size() % 2 != 0) throw new IllegalArgumentException(); Stack&lt;Integer&gt; s = new ArrayStack&lt;Integer&gt;(); int halfSize = q.size() / 2; for (int i = 0; i &lt; halfSize; i++) s.push(q.dequeue()); while (!s.isEmpty()) q.enqueue(s.pop()); for (int i = 0; i &lt; halfSize; i++) q.enqueue(q.dequeue()); for (int i = 0; i &lt; 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 &lt; size; i++) elementData[i] = elementData[2 * i]; }
Stuart Reges