CSE143 Sample Midterm 1. Recursive Tracing, 15 points. Consider the following method: public void mystery(int n) { if (n >= 10) { mystery(n / 10); } if (n % 2 == 0) { System.out.print("-"); } else { System.out.print("*"); } } For each call below, indicate what output is produced: Method Call Output Produced mystery(5); _____________________________________ mystery(15); ______________________________________ mystery(304); ______________________________________ mystery(9247); ______________________________________ mystery(43269); ______________________________________ 2. Recursive Programming, 15 points. Write a recursive method called substring that takes as parameters a string, a start index, and an ending index, and that returns a specified substring of the string. You are implementing a recursive alternative to the standard substring method. As with the standard substring method, your method should return the substring that begins at the start index and that extends to the character just before the ending index. For example: substring("hello", 0, 2) should return "he" substring("hamburger", 4, 8) should return "urge" substring("smiles", 1, 5) should return "mile" substring("howdy", 3, 3) should return "" The method should throw an IllegalArgumentException if the start index is negative or if the ending index is greater than the length of the string or if the start index is greater than the ending index. The method should return an empty string if the two indexes are equal. In implementing this method, you are restricted to the following string methods: charAt(index) returns the character at the given index equals(other) returns whether this String is equal to the other length() returns the length of the String 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 called isConsecutive that returns true if a list of integers contains a sequence of consecutive integers and that returns false otherwise. Consecutive integers are integers that come one after the other, as in 5, 6, 7, 8, 9, etc. For example, if a variable called list stores these values: [3, 4, 5, 6, 7, 8, 9, 10] then the call: list.isConsecutive() should return true. If the list had instead contained this sequence: [3, 4, 5, 6, 7, 8, 9, 10, 12] then the call should return false because the numbers 10 and 12 are not consecutive. The following sequence of values would be consecutive except for the fact that it appears in reverse order, so the method would return false in this case: [3, 2, 1] Any list with fewer than two values should be considered to be consecutive. You are writing a method for the LinkedIntList 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 } public class LinkedIntList { private ListNode front; } You may not call any other methods of the LinkedIntList class and you may not construct any structured objects to solve this problem. 4. Details of inheritance, 20 points. Assuming that the following classes have been defined: public class Water extends Earth { public void method1() { System.out.println("Water 1"); } public void method3() { System.out.println("Water 3"); } } public class Fire { public void method1() { System.out.println("Fire 1"); } public void method2() { System.out.println("Fire 2"); method1(); } } public class Earth extends Fire { public void method1() { System.out.println("Earth 1"); super.method1(); } } public class Air extends Fire { public void method3() { System.out.println("Air 3"); } } And assuming the following variables have been defined: Fire var1 = new Water(); Fire var2 = new Earth(); Fire var3 = new Fire(); Object var4 = new Earth(); Earth var5 = new Water(); Fire var6 = new Air(); 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.method1(); ____________________________ var2.method1(); ____________________________ var3.method1(); ____________________________ var4.method1(); ____________________________ var5.method1(); ____________________________ var6.method1(); ____________________________ var1.method2(); ____________________________ var2.method2(); ____________________________ var3.method2(); ____________________________ var4.method2(); ____________________________ var5.method2(); ____________________________ var6.method2(); ____________________________ ((Water)var4).method2(); ____________________________ ((Fire)var4).method2(); ____________________________ ((Air)var6).method3(); ____________________________ ((Earth)var1).method3(); ____________________________ ((Water)var1).method3(); ____________________________ ((Water)var2).method3(); ____________________________ ((Earth)var1).method2(); ____________________________ ((Water)var6).method3(); ____________________________ 5. Stacks/Queues, 25 points. Write a method called reverseByN that takes a queue of integers and an integer n as parameters and that reverses each successive sequence of length n in the queue. For example, suppose that a variable called q stores the following sequence of values: front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] back and we make the following call: reverseByN(q, 3); Then q should store the following values after the call: front [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13] back Notice that the first three values (1, 2, 3) have been reversed, as have the next three values (4, 5, 6), the next three values (7, 8, 9), and so on. If the size of the queue is not an even multiple of n, then there will be a sequence of fewer than n values at the end. This sequence should be reversed as well. For example, if q stores this sequence: front [8, 9, 15, 27, -3, 14, 42, 8, 73, 19] back and we make the call: reverseByN(q, 4); Then q should store the following values after the call: front [27, 15, 9, 8, 8, 42, 14, -3, 19, 73] back Notice that the two sequences of length 4 have been reversed along with the sequence of two values at the end (73, 19). If n is greater than the size of the queue, then the method should reverse the entire sequence. You are to use one stack 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 may not use recursion to solve this problem and your solution must run in O(n) time. Use the Stack and Queue interfaces and the ArrayStack and LinkedQueue implementations discussed in lecture. 6. Array Programming, 10 points. Write a method called fromCounts that converts an ArrayIntList of counts into a new ArrayIntList of values. Assume that the ArrayIntList that is called stores a sequence of integer pairs that each indicate a count and a number. For example, suppose that an ArrayIntList called list stores the following sequence of values: [5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17] This sequence of pairs indicates that you have 5 occurrences of 2, followed by two occurrences of -5, followed by 4 occurrences of 3, and so on. If we make the following call: ArrayIntList list2 = list.fromCounts(); Then the variable list2 should store the following sequence of values: [2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17] 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 } You may assume that the ArrayIntList that is called stores a legal sequence of pairs (which means it will always have an even size) and that the default constructor for ArrayIntList will construct an array of sufficient capacity to store the result. Your method should not change the original list. If the sequence of pairs is empty, the result should be an empty list. You may call the ArrayIntList constructor, but otherwise you may not call any other methods of the ArrayIntList class to solve this problem. You are not allowed to define any auxiliary data structures (no array, String, ArrayList, etc), and you may not change the original list.