CSE143 Sample Midterm handout #18 Spring 2008 1. Recursive Tracing, 15 points. Consider the following method: public void mystery(int n) { if (n % 2 == 1) System.out.print(n); else { System.out.print(n + ", "); mystery(n / 2); } } For each call below, indicate what output is produced: Method Call Output Produced mystery(13); _____________________________________ mystery(42); ______________________________________ mystery(40); ______________________________________ mystery(60); ______________________________________ mystery(48); ______________________________________ 2. Recursive Programming, 15 points. Write a method indexOf that takes two Strings as parameters and that returns the starting index of the first occurrence of the second String inside the first String (-1 if not found). For example: indexOf("Barack Obama", "Bar") returns 0 indexOf("Barack Obama", "ck") returns 4 indexOf("Barack Obama", "a") returns 1 indexOf("Barack Obama", "BAR") returns -1 Notice that case matters, as in the last example that returns -1 because the second String does not occur inside the first String. The String class includes an indexOf method and you are not allowed to simply call it to solve this problem. You are limited to the following String methods: equals(other) Returns whether this String is equal to the other object length() Returns the length of the String substring(fromIndex, toIndex) Returns a new string that is a substring of this string from startIndex (inclusive) to stopIndex (exclusive) substring(fromIndex) Returns a new string that is a substring of this string from startIndex (inclusive) to the end of the String For example, if a String s stores the text "hello", then: s.equals("hello") returns true s.length() returns 5 s.substring(1, 3) returns "el" s.substring(2) returns "llo" You are not allowed to construct any structured objects other than Strings (no array, StringBuilder, Scanner, 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. Write a method hasAlternatingParity that returns whether or not a list of integers has alternating parity (true if it does, false otherwise). The parity of an integer is 0 for even numbers and 1 for odd numbers. To have alternating parity, a list would have to alternate between even and odd numbers, as in the following list: [3, 2, 19, 8, 43, 64, 1, 0, 3] If a variable called list stores the values above, then the call: list.hasAlternatingParity() would return true. If instead the list stored the following values: [2, 13, 4, 1, 0, 9, 2, 7, 4, 12, 3, 2] then the call would return false because the list has two even numbers in a row (4 and 12). By definition, an empty list or a list of one element has alternating parity. You may assume that the values in the list are greater than or equal to 0. Assume that we are using a linked list that stores integers, as discussed in lecture (handout 8). public class ListNode { public int data; // data stored in this node public ListNode next; // link to next node in the list <constructors> } public class LinkedIntList { private ListNode front; <methods> } You are writing a method that will become part of the LinkedIntList class. You may not call any other methods of the class to solve this problem and your method cannot change the contents of the list. 4. Details of inheritance, 20 points. Assuming that the following classes have been defined: public class Clip extends Paper { public void method2() { System.out.println("Clip 2"); super.method2(); } } public class Paper { public void method2() { System.out.println("Paper 2"); } public void method3() { System.out.println("Paper 3"); method2(); } } public class Stapler extends Clip { public void method1() { System.out.println("Stapler 1"); } public void method2() { System.out.println("Stapler 2"); } } public class Pen extends Paper { public void method1() { System.out.println("Pen 1"); } public void method2() { System.out.println("Pen 2"); } } And assuming the following variables have been defined: Paper var1 = new Pen(); Stapler var2 = new Stapler(); Paper var3 = new Stapler(); Paper var4 = new Paper(); Object var5 = new Stapler(); Paper var6 = new Clip(); 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 (you may abbreviate these as "ce" and "re" or "c.e." and "r.e."). Statement Output ------------------------------------------------------------ var1.method2(); ____________________________ var2.method2(); ____________________________ var3.method2(); ____________________________ var4.method2(); ____________________________ var5.method2(); ____________________________ var6.method2(); ____________________________ var1.method1(); ____________________________ var2.method1(); ____________________________ var3.method1(); ____________________________ var1.method3(); ____________________________ var2.method3(); ____________________________ var3.method3(); ____________________________ var4.method3(); ____________________________ ((Pen)var1).method1(); ____________________________ ((Stapler)var3).method1(); ____________________________ ((Clip)var3).method3(); ____________________________ ((Clip)var5).method1(); ____________________________ ((Pen)var5).method1(); ____________________________ ((Clip)var6).method2(); ____________________________ ((Stapler)var6).method3(); ____________________________ 5. Stacks/Queues, 25 points. Write a method 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 we 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. Your method should throw an IllegalArgumentException if the stack is empty. In writing your method, assume that you are using the Stack and Queue interfaces and the ArrayStack and LinkedQueue implementations discussed in lecture. 6. Array Programming, 10 points. Write a method collapse that collapses a list of integers by replacing each successive pair of integers with the sum of the pair. For example, if a variable called list stores this sequence of values: [7, 2, 8, 9, 4, 13, 7, 1, 9, 10] and the following call is made: list.collapse(); The first pair should be collapsed into 9 (7 + 2), the second pair should be collapsed into 17 (8 + 9), the third pair should be collapsed into 17 (4 + 13) and so on to yield: [9, 17, 17, 8, 19] If the list stores an odd number of elements, the final element is not collapsed. For example, the sequence: [1, 2, 3, 4, 5] would collapse into: [3, 7, 5] with the 5 at the end of the list unchanged. You are writing a method for the ArrayIntList class discussed in lecture (handout 3): 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), and your solution must run in O(n) time.
Stuart Reges
Last modified: Mon May 5 16:14:26 PDT 2008