<![CDATA[
CSE143 Sample Midterm handout #19
Spring 2005
1. Recursive Tracing, 15 points. Consider the following method:
public void mystery(int n) {
if (n > 100)
System.out.print(n);
else {
mystery(2 * n);
System.out.print(", " + n);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(113) _______________________________
mystery(70) _______________________________
mystery(42) _______________________________
mystery(30) _______________________________
mystery(10) _______________________________
2. Recursive Programming, 15 points. Write a method writeNums that takes an
integer n as a parameter and that writes the first n integers starting with
1 to System.out in sequential order and separated by commas. All output
should be on the current line of output.
For example, the following calls:
writeNums(5);
System.out.println(); // to complete the line of output
writeNums(12);
System.out.println(); // to complete the line of output
should produce the output:
1, 2, 3, 4, 5
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
You must exactly reproduce the format of the examples above. Your method
should throw an IllegalArgumentException if passed a value less than 1.
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 writeNums below.
3. Linked Lists, 15 points. Write a method evenSum that returns the sum of the
values in even indexes in a list of integers. Assume we are using 0-based
indexing where the first value in the list has index 0, the second value has
index 1 and so on. The values we are interested in are the ones with even
indexes (the value at index 0, the value at index 2, the value at index 4,
and so on). For example, if a variable called list stores the following
sequence of values:
(1, 18, 2, 7, 39, 8, 40, 7)
then the call:
list.evenSum()
should return the value 82 (1 + 2 + 39 + 40). Notice that what is important
is the position of the numbers (index 0, index 2, index 4, etc), not whether
the numbers themselves are even. If the list is empty, your method should
return a sum of 0.
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 evenSum below.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Frodo extends Bilbo {
public void method1() {
System.out.println("Frodo 1");
super.method1();
}
public void method3() {
System.out.println("Frodo 3");
}
}
public class Gandalf {
public void method1() {
System.out.println("Gandalf 1");
}
public void method2() {
System.out.println("Gandalf 2");
method1();
}
}
public class Bilbo extends Gandalf {
public void method1() {
System.out.println("Bilbo 1");
}
}
public class Gollum extends Gandalf {
public void method3() {
System.out.println("Gollum 3");
}
}
And assuming the following variables have been defined:
Gandalf var1 = new Frodo();
Gandalf var2 = new Bilbo();
Gandalf var3 = new Gandalf();
Object var4 = new Bilbo();
Bilbo var5 = new Frodo();
Object var6 = new Gollum();
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(); ____________________________
var5.method1(); ____________________________
var6.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
((Bilbo)var1).method3(); ____________________________
((Gandalf)var1).method2(); ____________________________
((Frodo)var4).method1(); ____________________________
((Gandalf)var6).method2(); ____________________________
((Gandalf)var4).method1(); ____________________________
((Frodo)var6).method3(); ____________________________
((Frodo)var3).method3(); ____________________________
((Frodo)var5).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method collapse that takes a Stack of
integers as a parameter and that collapses it by replacing each successive
pair of integers with the sum of the pair. For example, suppose a stack
stores this sequence of values:
bottom (7, 2, 8, 9, 4, 13, 7, 1, 9, 10) top
Assume that stack values appear from bottom to top. In other words, 7 is on
the bottom, with 2 on top of it, with 8 on top of it, and so on, with 10 at
the top of the stack.
The first pair should be collapsed into 9 (7 + 2), the second pair should be
collapsed into 17 (8 + 9), the third pair should be collapsed into 17 (4 +
13) and so on to yield:
bottom (9, 17, 17, 8, 19) top
As before, stack values appear from bottom to top (with 9 on the bottom of
the stack, 17 on top of it, etc). If the stack stores an odd number of
elements, the final element is not collapsed. For example, the sequence:
bottom (1, 2, 3, 4, 5) top
would collapse into:
bottom (3, 7, 5) top
with the 5 at the top of the stack unchanged.
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. As a result, values will be stored as Integer objects, not simple
ints.
Your method should take a single parameter: the stack to collapse.
6. Array Programming, 10 points. Write a method longestSortedSequence that
returns the length of the longest sorted sequence within a list of integers.
For this problem sorted means non-decreasing. For example, if a variable
called list stores the following sequence of values:
(1, 3, 5, 2, 9, 7, -3, 0, 42, 308, 17)
then the call:
list.longestSortedSequence()
would return the value 4 because it is the length of the longest sorted
sequence within this list (the sequence -3, 0, 42, 308). If the list is
empty, your method should return 0. Notice that for a non-empty list the
method will always return a value of at least 1 because any individual
element constitutes a sorted sequence.
You are writing a method for the IntList class discussed in lecture
(handouts 3 and 5):
public class IntList {
private int[] elementData; // list of integers
private int size; // current # of elements in the list
<methods>
}
You are not to call any other IntList methods to solve this problem. You
also may not use another data structure like a temporary array and your
method must run in O(n) time where n is the size of the list.
Write your solution to longestSortedSequence below.
]]>