<![CDATA[
CSE143 Midterm
Autumn 2006
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 Details of Inheritance 20 _____
5 Stacks/Queues 25 _____
6 Array Programming 10 _____
----------------------------
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.
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 int mystery(int n) {
if (n < 0) {
return mystery(-n);
} else if (n < 10) {
return n;
} else {
return n % 10 + mystery(n / 10);
}
}
For each call below, indicate what value is returned:
Method Call Value Returned
mystery(8) ______________
mystery(74) ______________
mystery(-52) ______________
mystery(3052) ______________
mystery(82534) ______________
2. Recursive Programming, 15 points. Write a method printRange that takes
integer parameters x and y and that prints the sequential integers between x
and y inclusive. The first half of the list should be printed with the
greater-than character (">") separating consecutive values. The second half
should be printed with the less-than character ("<") separating consecutive
values. All output should be on the current line of output.
For example, the following calls:
printRange(1, 9);
System.out.println(); // to complete the line of output
printRange(8, 20);
System.out.println(); // to complete the line of output
printRange(-8, -8);
System.out.println(); // to complete the line of output
should produce the following output:
1 > 2 > 3 > 4 > 5 < 6 < 7 < 8 < 9
8 > 9 > 10 > 11 > 12 > 13 > 14 < 15 < 16 < 17 < 18 < 19 < 20
-8
Notice that in the first output, 5 is in the middle with the numbers before
it separated by greater-than and the numbers after it separated by
less-than. In the second output, 14 is in the middle with numbers before it
separated by greater-than and numbers after it separated by less-than. The
third output has no separators because that range includes only one number.
When there are two values in the middle of the range, those two values
should be separated by a dash. For example:
printRange(1, 10);
System.out.println(); // to complete the line of output
printRange(13, 14);
System.out.println(); // to complete the line of output
should produce the following output:
1 > 2 > 3 > 4 > 5 - 6 < 7 < 8 < 9 < 10
13 - 14
You must exactly reproduce the format of these examples. Your method should
throw an IllegalArgumentException if the first parameter is greater than the
second. You may NOT use a while loop, for loop or do/while loop to solve
this problem; you must use recursion.
Write your solution to printRange below.
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 8 and 9).
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 occuring 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). Thefore, the following call:
list.maxCount()
should return 4 to indicate that the most frequently occuring 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
(handouts 3, 5 and 6):
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.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011