Key to Sample CSE143 Midterm, Spring 2008 handout #20 1. Method Call Output Produced ----------------------------------------------- mystery(13); 13 mystery(42); 42, 21 mystery(40); 40, 20, 10, 5 mystery(60); 60, 30, 15 mystery(48); 48, 24, 12, 6, 3 2. One possible solution appears below. public int indexOf(String source, String target) { if (target.length() > source.length()) return -1; else if (source.substring(0, target.length()).equals(target)) return 0; else { int pos = indexOf(source.substring(1), target); if (pos == -1) return pos; else return pos + 1; } } 3. One possible solution appears below. public boolean hasAlternatingParity() { if (front != null) { ListNode current = front; while (current.next != null) { if (current.data % 2 == current.next.data % 2) return false; current = current.next; } } return true; } 4. Statement Output ------------------------------------------------------------ var1.method2(); Pen 2 var2.method2(); Stapler 2 var3.method2(); Stapler 2 var4.method2(); Paper 2 var5.method2(); compiler error var6.method2(); Clip 2/Paper 2 var1.method1(); compiler error var2.method1(); Stapler 1 var3.method1(); compiler error var1.method3(); Paper 3/Pen 2 var2.method3(); Paper 3/Stapler 2 var3.method3(); Paper 3/Stapler 2 var4.method3(); Paper 3/Paper 2 ((Pen)var1).method1(); Pen 1 ((Stapler)var3).method1(); Stapler 1 ((Clip)var3).method3(); Paper 3/Stapler 2 ((Clip)var5).method1(); compiler error ((Pen)var5).method1(); runtime error ((Clip)var6).method2(); Clip 2/Paper 2 ((Stapler)var6).method3(); runtime error 5. One possible solution appears below. public int removeMin(Stack<Integer> s) { if (s.isEmpty()) throw new IllegalArgumentException(); Queue<Integer> q = new LinkedQueue<Integer>(); int min = s.pop(); q.enqueue(min); while (!s.isEmpty()) { int next = s.pop(); if (next < min) min = next; q.enqueue(next); } while (!q.isEmpty()) { int next = q.dequeue(); if (next != min) s.push(next); } while (!s.isEmpty()) q.enqueue(s.pop()); while (!q.isEmpty()) s.push(q.dequeue()); return min; } 6. One possible solution appears below. public void collapse() { for (int i = 0; i < size / 2; i++) elementData[i] = elementData[2 * i] + elementData[2 * i + 1]; if (size % 2 == 0) size = size / 2; else { elementData[size / 2] = elementData[size - 1]; size = size / 2 + 1; } }
Stuart Reges
Last modified: Fri May 9 20:01:18 PDT 2008