CSE143 Sample Midterm handout #20 Summer 2009 1. Recursive Tracing, 15 points. Consider the following method: public void mystery(int x, int y) { if (x > y) System.out.print("*"); else if (x == y) System.out.print("=" + y + "="); else { System.out.print(y + " "); mystery(x + 1, y - 1); System.out.print(" " + x); } } For each call below, indicate what output is produced: Method Call Output Produced mystery(3, 3); _____________________________________ mystery(5, 1); ______________________________________ mystery(1, 5); ______________________________________ mystery(2, 7); ______________________________________ mystery(1, 8); ______________________________________ 2. Recursive Programming, 15 points. Write a method repeat that takes a String s and an integer n as parameters and that returns a String composed of n copies of s. For example: repeat("hello", 3) returns "hellohellohello" repeat("this is fun", 1) returns "this is fun" repeat("wow", 0) returns "" repeat("hi ho!", 5) returns "hi ho!hi ho!hi ho!hi ho!hi ho!" Your method should throw an IllegalArgumentException if passed a negative value for n. You should solve this problem by concatenating Strings using the "+" operator. String concatenation is an expensive operation, so it is best to minimize the number of concatenation operations you perform. For example, for the call repeat("foo", 500), it would be inefficient to perform 500 different concatenation operations to obtain the result. Most of the credit (9 points) will be awarded on the correctness of your solution independent of efficiency. The remaining credit (6 points) will be awarded based on your ability to minimize the number of concatenation operations performed. You are not allowed to construct any structured objects other than Strings (no array, StringBuilder, ArrayList, 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 maxAdjacentPairSum that returns the maximum sum of adjacent values in a list of integers. For example, if a variable called list stores the following sequence of values: [1, 18, 2, 7, 18, 39, 12] then the call: list.maxAdjacentPairSum() should return 57 because it is the largest sum that can be obtained with adjacent values in this list (18 + 39). Your method should consider only adjacent pairs. For example, if the list instead had stored: [1, 18, 2, 7, 18, 39, 12, 40, 32, -9, 103, -13] then a call on the method should return 94 because the maximum sum that can be obtained from adjacent values in the list is 94 (-9 + 103). Your method should return 0 if the list contains fewer than two values. Assume that we are using a linked list that stores integers, as discussed in lecture (handouts 6 and 7). 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. Write your solution to maxAdjacentPairSum below. 4. Details of inheritance, 20 points. Assuming that the following classes have been defined: public class Green extends Red { public void method1() { System.out.println("Green 1"); } public void method3() { System.out.println("Green 3"); } } public class White extends Red { public void method2() { System.out.println("White 2"); } public void method3() { System.out.println("White 3"); } } public class Blue { public void method1() { System.out.println("Blue 1"); method2(); } public void method2() { System.out.println("Blue 2"); } } public class Red extends Blue { public void method2() { System.out.println("Red 2"); super.method2(); } } And assuming the following variables have been defined: Blue var1 = new Blue(); Green var2 = new Green(); Object var3 = new White(); Red var4 = new Green(); Blue var5 = new Red(); Blue var6 = new White(); 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(); ____________________________ var1.method2(); ____________________________ var2.method2(); ____________________________ var3.method2(); ____________________________ var4.method2(); ____________________________ var1.method3(); ____________________________ var2.method3(); ____________________________ var3.method3(); ____________________________ var4.method3(); ____________________________ ((Blue)var3).method1(); ____________________________ ((Red)var3).method2(); ____________________________ ((White)var3).method3(); ____________________________ ((White)var4).method3(); ____________________________ ((Green)var5).method3(); ____________________________ ((Red)var5).method1(); ____________________________ ((Blue)var6).method3(); ____________________________ ((Green)var6).method3(); ____________________________ 5. Stacks/Queues, 25 points. Write a method switchPairs that takes a Stack of integers as a parameter and that switches successive pairs of numbers starting at the bottom of the stack. For example, if the stack initially stores these values: bottom [3, 8, 17, 9, 99, 9, 17, 8, 3, 1, 2, 3, 4, 14] top your method should switch the first pair (3, 8), the second pair (17, 9), the third pair (99, 9), and so on, yielding this sequence: bottom [8, 3, 9, 17, 9, 99, 8, 17, 1, 3, 3, 2, 14, 4] top If there are an odd number of values in the stack, the value at the top of the stack is not moved. For example, if the original stack had stored: bottom [3, 8, 17, 9, 99, 9, 17, 8, 3, 1, 2, 3, 4, 14, 42] top It would again switch pairs of values, but the value at the top of the stack (42) would not be moved, yielding this sequence: bottom [8, 3, 9, 17, 9, 99, 8, 17, 1, 3, 3, 2, 14, 4, 42] top You may not make any assumptions about how many elements are in the stack. 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. In writing your method, assume that you are using the Stack and Queue interfaces and the ArrayStack and LinkedQueue implementations discussed in lecture. Write your solution to switchPairs below. 6. Array Programming, 10 points. Write a method maxCount that returns the number of occurrences of the most frequently occurring value in a sorted list of integers. Because the list will be sorted, all duplicates will be grouped together, which will make it easier to count duplicates. For example, suppose that a variable called list stores the following sequence of values: [1, 3, 4, 7, 7, 7, 7, 9, 9, 11, 13, 14, 14, 14, 16, 16, 18, 19, 19, 19] This list has values that occur just once (1, 3, 4, 11, 13, 18), values that occur twice (9, 16), values that occur three times (14, 19) and a single value that occurs four times (7). Therefore, the following call: list.maxCount() should return 4 to indicate that the most frequently occurring value occurs 4 times. It is possible that there will be a tie for the most frequently occurring value, but that doesn't affect the outcome because you are just returning the count, not the value. For example, if there are no duplicates in the list, then every value will occur exactly once and the maximum would be 1. If the list is empty, your method should return 0. 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. Your solution must run in O(n) time. You may not use any auxiliary data structures to solve this problem, although you can have as many simple variables as you like. Remember that you can assume that the values appear in sorted (nondecreasing) order. Write your solution to maxCount below.