CSE143X Sample Midterm #2 handout #14 Autumn 2024 1. Expressions, 10 points. For each expression in the left-hand column, indicate its value in the right-hand column. Be sure to list a constant of appropriate type (e.g., 7.0 rather than 7 for a double, Strings in quotes). Expression Value 5 * 6 - (4 + 3) * 2 - 2 * 3 ________________ 208 / 20 / 4 + 12 / 10.0 + 0.4 * 2 ________________ 8 - 2 + "8 - 2" + 8 * 2 + 8 ________________ 4 * 5 % 6 + 297 % 10 + 4 % 8 ________________ 13 / 2 * 3.0 + 5.5 * 3 / 2 ________________ 2. Parameter Mystery, 12 points. Consider the following program. public class Mystery { public static void main(String[] args) { String x = "chair"; String y = "notes"; String z = "table"; String meeting = "x"; String notes = y + meeting; meeting(x, y, z); meeting(y, meeting, "notes"); meeting(y + z, y + meeting, notes); meeting = "boring"; meeting(meeting, "today", x); } public static void meeting(String z, String y, String x) { System.out.println(x + " and " + z + " like " + y); } } List below the output produced by this program. 3. Recursive Tracing, 13 points. Consider the following method: public void mystery(int n) { System.out.print("+"); 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); ______________________________________ 4. Recursive Programming, 15 points. Write a recursive method called doubleDigit that takes an integer n and a digit d as parameters and that returns the integer obtained by replacing all occurrences of d in n with two of that digit. For example, doubleDigit(3797, 7) would return 377977 because the two occurrences of the digit 7 are replaced with two of that digit. The table below includes more examples. Method Value Method Value Call Returned Call Returned --------------------------------- ---------------------------------- doubleDigit(2, 2) 22 doubleDigit(2001, 0) 200001 doubleDigit(0, 0) 0 doubleDigit(12345, 6) 12345 doubleDigit(8, 6) 8 doubleDigit(72773, 7) 77277773 doubleDigit(55, 2) 55 doubleDigit(3445, 5) 34455 doubleDigit(33, 3) 3333 doubleDigit(54224, 4) 5442244 doubleDigit(-101, 1) -11011 doubleDigit(-624243, 4) -62442443 doubleDigit(323, 3) 33233 doubleDigit(5340909, 0) 534009009 Notice that the number can be negative. Your method should throw an IllegalArgumentException if the value of d is not a 1-digit number (i.e., not between 0 and 9 inclusive). You are not allowed to construct any structured objects to solve this problem (no string, array, ArrayList, 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. 5. Details of inheritance, 20 points. Assuming that the following classes have been defined: public class Fork extends Pot { public void method2() { System.out.println("Fork 2"); super.method2(); } } public class Pot { public void method2() { System.out.println("Pot 2"); } public void method3() { System.out.println("Pot 3"); method2(); } } public class Bowl extends Fork { public void method1() { System.out.println("Bowl 1"); } public void method2() { System.out.println("Bowl 2"); } } public class Spoon extends Pot { public void method1() { System.out.println("Spoon 1"); } public void method2() { System.out.println("Spoon 2"); } } And assuming the following variables have been defined: Pot var1 = new Spoon(); Bowl var2 = new Bowl(); Pot var3 = new Bowl(); Pot var4 = new Pot(); Object var5 = new Bowl(); Pot var6 = new Fork(); 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.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(); ____________________________ ((Spoon)var1).method1(); ____________________________ ((Bowl)var3).method1(); ____________________________ ((Fork)var3).method3(); ____________________________ ((Fork)var5).method1(); ____________________________ ((Spoon)var5).method1(); ____________________________ ((Fork)var6).method2(); ____________________________ ((Bowl)var6).method3(); ____________________________ 6. Linked List Nodes, 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 and you are not allowed to construct any new nodes, but you are allowed to declare and use variables of type ListNode (often called "temp" variables). You are limited to at most two variables of type ListNode for each of the four subproblems below. 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 and the variables p and q have the value null when they do not point to anything. before after code -----------------------+-----------------------+------------------------------- p | p->[3] | | | | | q->[1]->[2]->[3] | q->[1]->[2] | | | -----------------------+-----------------------+------------------------------- | | | | p->[1] | p->[1] | | | | | q->[2]->[3] | q->[3]->[2] | | | -----------------------+-----------------------+------------------------------- | | | | p->[1]->[2] | p->[4]->[2] | | | | | q->[3]->[4] | q->[1]->[3] | | | | | | | | | -----------------------+-----------------------+------------------------------- | | | | p->[1]->[2]->[3] | p->[2]->[4] | | | | | q->[4]->[5] | q->[5]->[3]->[1] | | | | | | | | | | | | | | | | | -----------------------+-----------------------+------------------------------- 7. ArrayIntList, 12 points. Write a method called extractOddIndexes that constructs and returns a new ArrayIntList of values that contains the sequence formed by removing the values at odd indexes in an existing ArrayIntList of values. For example, suppose that an ArrayIntList called list stores the following sequence of values: [13, 5, 7, 12, 42, 8, 23, 31] If we make the following call on the method: ArrayIntList result = list.extractOddIndexes(); After the call, list and result would store the following: list : [13, 7, 42, 23] result: [5, 12, 8, 31] Notice that the values that were at odd indexes have been moved to the new ArrayIntList in the same order as in the original list and that the list now stores just values that were at even indexes also in the same order as in the original list. The list might have an odd number of values, as in: [14, -64, 16, 88, 21, 17, -93, 81, 17] in which case the lists would store the following after the call: list : [14, 16, 21, -93, 17] result: [-64, 88, 17, 81] Notice that list stores five values while result stores only four. 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 may use the zero-argument constructor for ArrayIntList and you may assume that it will construct an array of sufficient capacity to store the result. If the original list 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 other than the new ArrayIntList you are constructing (no array, String, ArrayList, etc). Your solution must run in O(n) time where n is the original list. 8. Stacks/Queues, 12 points. Write a method called mirrorSplit that takes a stack of integers as a parameter and that splits each value into two halves, adding new values to the stack in a mirror position. For example, suppose that a stack s stores the following values: bottom [14, 20, 8, 12] top If we make the following call: mirrorSplit(s); Then after the call, the stack should store the following values: bottom [7, 10, 4, 6, 6, 4, 10, 7] top ^ ^ ^ ^ ^ ^ ^ ^ | | | +--+ | | | | | +--------+ | | | +---------------+ | +----------------------+ mirror positions The first value 14 has been split in half into two 7s which appear in mirror positions (first and last). The second value 20 has been split in half into two 10s which appear in mirror positions (second and second-to-last). And so on. This example included just even numbers in which case you get a true mirror image. If the stack contains odd numbers, they should be split so as to add up to the original with the larger value appearing closer to the bottom of the stack. For example, if the stack stores these values: bottom [13, 5, 12] top After the call, it would store the following values: bottom [7, 3, 6, 6, 2, 6] top ^ ^ ^ ^ ^ ^ | | +--+ | | | +--------+ | +--------------+ mirror positions The first value 13 has been split into 7 and 6 with the 7 included as the first value and 6 included as the last value. The value 5 has been split into 3 and 2 with 3 appearing as the second value and 2 appearing as the second-to-last value. And so on. 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 (recall that you can't use the peek method or a foreach loop or iterator). You may assume that methods stackToQueue and queueToStack discussed in lecture are available to be called.
Stuart Reges
Last modified: Fri Nov 1 13:18:36 PDT 2024