CSE143 Sample Midterm Summer 2008 Name of Student_______________________________________________________________ Section (e.g., AA)___________________ TA_____________________________________ This is an open-book/open-note exam. Space is provided for your answers. Use the backs of pages if necessary. The exam is divided into six questions with the following points: # Problem Area Points Score --------------------------------------------- 1 Recursive Tracing 15 _____ 2 Recursive Programming 15 _____ 3 Linked Lists 15 _____ 4 More Linked Lists 15 _____ 5 Stacks/Queues 25 _____ 6 Array Programming 15 _____ ---------------------------- Total 100 _____ The exam is not, in general, graded on style and you do not need to include comments. For the stack/queue question, however, you are expected to use generics properly and to declare variables using interfaces when possible. You are NOT to use any electronic devices while taking the test, including calculators. Anyone caught using an electronic device will receive a 10 point penalty. Do not begin work on this exam until instructed to do so. Any student who starts early or who continues to work after time is called will receive a 10 point penalty. If you finish the exam early, please hand your exam to the instructor and exit quietly through the front door. 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 transferFrom for LinkedIntList that takes a second LinkedIntList list as a parameter and that moves values from the second list to this list. First you are to join them together, attaching the second list to the end of this list. Then you are to empty the second list. For example, if two lists store these sequences of values: list1: (8, 17, 2, 4) list2: (1, 2, 3) Then the following call: list1.transferFrom(list2); should leave the lists as follows: list1: (8, 17, 2, 4, 1, 2, 3) list2: () The order of the arguments in the call matters. For example: list2.transferFrom(list1); would have left the lists as follows: list1: () list2: (1, 2, 3, 8, 17, 2, 4) Either of the two lists could be empty, but you can assume that neither list is null. You are not to create any new nodes. Your method should simply change links of the lists to join them together. 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 to solve this problem and your solution must run in O(n) time. 4. More Linked Lists, 15 points. Write a method removeLast that removes the last occurrence of an integer (if any) from a list of integers. For example, suppose that a variable called "list" stores this sequence of values: [3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0, 3] If we repeatedly make the following call: list.removeLast(3); Then the list will take on the following sequence of values: [3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0] [3, 2, 3, 3, 19, 8, 43, 64, 1, 0] [3, 2, 3, 19, 8, 43, 64, 1, 0] [3, 2, 19, 8, 43, 64, 1, 0] [2, 19, 8, 43, 64, 1, 0] [2, 19, 8, 43, 64, 1, 0] Notice that once we reach a point where no more 3's occur in the list, then calling the method has no effect. 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 to solve this problem and your solution must run in O(n) time. 5. Stacks/Queues, 25 points. Write a method interleave that takes a queue of integers as a parameter and that rearranges the elements by interleaving the first half of the list with the second half of the list. For example, suppose a variable called q stores the following sequence of values: front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] back and we make the following call: interleave(q); Consider the two halves of this list: first half: [1, 2, 3, 4, 5] second half: [6, 7, 8, 9, 10] These are combined in an alternating fashion to form a sequence of interleave pairs: the first values from each half (1 and 6), then the second values from each half (2 and 7), then the third values from each half (3 and 8), and so on. In each pair, the value from the first half appears before the value from the second half. Thus, after the call, the queue stores the following values: front [1, 6, 2, 7, 3, 8, 4, 9, 5, 10] back This example uses sequential integers to make the interleaving more obvious, but the same process can be applied to any sequence of even length. For example, if q had instead stored these values: front [2, 8, -5, 19, 7, 3, 24, 42] back then the method would have rearranged the list to become: front [2, 7, 8, 3, -5, 24, 19, 42] back Your method should throw an IllegalArgumentException if the queue does not have even length. 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. 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, 15 points. Write a method removeOddPositions that removes the values in odd-numbered positions (if any) from a list of integers. For example if a variable called list stores these values: [8, 13, 17, 4, 9, 12, 98] and the following call is made: list.removeOddPositions(); The list should store this sequence after the call: [8, 17, 9, 98] The method removed the values at odd positions (positions 1, 3, and 5), otherwise preserving the order of the remaining elements. Notice that it doesn't matter whether the value itself is odd or even but instead whether it appears in an odd position or even position. 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 not call any other methods of the 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.