CSE143 Sample Midterm handout #16 Fall 2012 1. Recursive Tracing, 15 points. Consider the following method: public void mystery(int n) { if (n == 1) { System.out.print(n); } else { System.out.print(n + ", "); if (n % 2 == 0) { mystery(n / 2); } else { mystery(3 * n + 1); } } } For each call below, indicate what output is produced: Method Call Output Produced mystery(1); ___________________________________________ mystery(2); ____________________________________________ mystery(4); ____________________________________________ mystery(8); ____________________________________________ mystery(10); ____________________________________________ 2. Recursive Programming, 15 points. Write a recursive method called printDashed that takes an integer as a parameter and that prints the integer with dashes in between the digits. The table below shows sample calls and the output that should be produced: Method call Output Method call Output ------------------------------ --------------------------------- printDashed(-834) -8-3-4 printDashed(6) 6 printDashed(-17) -1-7 printDashed(42) 4-2 printDashed(-4) -4 printDashed(983) 9-8-3 printDashed(0) 0 printDashed(29348) 2-9-3-4-8 Notice that no dashes are printed for positive one-digit numbers and that a leading dash is printed only for negative numbers. You are not allowed to construct any structured objects (no array, ArrayList, String, StringBuilder, etc) and you may not use a while loop, for loop, or do/while loop to solve this problem; you must use recursion. 3. Linked Lists, 15 points. Fill in the "code" column in the following table providing a solution that will turn the "before" picture into the "after" picture by modifying links between the nodes shown. You are not allowed to change any existing node's data field value. You are writing code for the ListNode class discussed in lecture: public class ListNode { public int data; // data stored in this node public ListNode next; // link to next node in the list <constructors> } As in the lecture examples, all lists are terminated by null. before after code +-----------------------+-----------------------+----------------------------- | | | | | | | | | p->[1]->[2] | p->[2] | | | | | | | | | | | q->[3]->[4] | q->[3]->[4]->[1] | | | | | | | | | | +-----------------------+-----------------------+-----------------------------+ | | | | | | | | | p->[1]->[2] | p->[2]->[1] | | | | | | | | | | | q->[3]->[4] | q->[4]->[3] | | | | | | | | | | +-----------------------+-----------------------+-----------------------------+ | | | | | | | | | p->[1]->[2]->[3] | p->[1]->[4] | | | | | | | | | | | q->[4] | q->[3]->[2] | | | | | | | | | | +-----------------------+-----------------------+-----------------------------+ 4. Details of inheritance, 20 points. Assuming that the following classes have been defined: public class Gorge extends Cliff { public void method2() { System.out.println("Gorge 2"); } public void method3() { System.out.println("Gorge 3"); } } public class Hill extends Peak { public void method2() { System.out.println("Hill 2"); } public void method3() { System.out.println("Hill 3"); } } public class Peak { public void method1() { System.out.println("Peak 1"); method3(); } public void method3() { System.out.println("Peak 3"); } } public class Cliff extends Peak { public void method3() { System.out.println("Cliff 3"); super.method3(); } } And assuming the following variables have been defined: Peak var1 = new Cliff(); Gorge var2 = new Gorge(); Peak var3 = new Hill(); Peak var4 = new Gorge(); Peak var5 = new Peak(); Object var6 = new Cliff(); In the table below, indicate in the right-hand column the output produced by the statement in the left-hand column. If the statement produces more than one line of output, indicate the line breaks with slashes as in "a/b/c" to indicate three lines of output with "a" followed by "b" followed by "c". If the statement causes an error, fill in the right-hand column with either the phrase "compiler error" or "runtime error" to indicate when the error would be detected. Statement Output ------------------------------------------------------------ var1.method1(); ____________________________ var2.method1(); ____________________________ var3.method1(); ____________________________ var4.method1(); ____________________________ var5.method1(); ____________________________ var6.method1(); ____________________________ var1.method2(); ____________________________ var2.method2(); ____________________________ var3.method2(); ____________________________ var1.method3(); ____________________________ var2.method3(); ____________________________ var3.method3(); ____________________________ ((Gorge)var6).method1(); ____________________________ ((Cliff)var3).method2(); ____________________________ ((Gorge)var4).method2(); ____________________________ ((Gorge)var3).method2(); ____________________________ ((Hill)var3).method2(); ____________________________ ((Gorge)var1).method1(); ____________________________ ((Cliff)var4).method3(); ____________________________ ((Peak)var6).method3(); ____________________________ 5. Stacks/Queues, 25 points. Write a method called removeMin that takes a stack of integers as a parameter and that removes and returns the smallest value from the stack. For example, if a variable called s stores the following sequence of values: bottom [2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, -8, 4] top and you make the following call: int n = removeMin(s); the method removes and returns the value -8 from the stack, so that the variable n will be -8 after the call and s will store the following values: bottom [2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, 4] top If the minimum value appears more than once, all occurrences of the minimum should be removed from the stack. For example, given the ending value of the stack above, if we again call removeMin(s), the method would return 2 and would leave the stack in the following state: bottom [8, 3, 19, 7, 3, 42, 9, 3, 7, 12, 4] top You are to use one queue as auxiliary storage to solve this problem. You may not use any other auxiliary data structures to solve this problem, although you can have as many simple variables as you like. You also may not solve the problem recursively. Your solution must run in O(n) time where n is the size of the stack. Use the Stack and Queue structures described in the cheat sheet and obey the restrictions described there. 6. Array Programming, 10 points. Write a method called mirror that doubles the size of a list of integers by appending the mirror image of the original sequence to the end of the list. The mirror image is the same sequence of values in reverse order. For example, if a variable called list stores this sequence of values: [1, 3, 2, 7] and you make the following call: list.mirror(); then it should store the following values after the call: [1, 3, 2, 7, 7, 2, 3, 1] Notice that it has been doubled in size by having the original sequence appearing in reverse order at the end of the list. You are writing a method for the ArrayIntList class discussed in lecture: public class ArrayIntList { private int[] elementData; // list of integers private int size; // current # of elements in the list <methods> } You are not to call any other ArrayIntList methods to solve this problem, you are not allowed to define any auxiliary data structures (no array, ArrayList, etc). You may assume that the array has sufficient capacity to store the new values.
Stuart Reges
Last modified: Mon Oct 29 17:16:14 PDT 2012