<![CDATA[
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.
]]>