<![CDATA[
CSE143 Sample Midterm handout #17
Spring 2005
1. Recursive Tracing, 15 points. Consider the following method:
public void mystery(int n) {
if (n <= 0)
System.out.print("*");
else if (n % 2 == 0) {
System.out.print("(");
mystery(n - 1);
System.out.print(")");
} else {
System.out.print("[");
mystery(n - 1);
System.out.print("]");
}
}
For each call below, indicate what output is produced by the method:
Method Call Output Produced
mystery(0) _______________________
mystery(1) _______________________
mystery(2) _______________________
mystery(4) _______________________
mystery(5) _______________________
2. Recursive Programming, 15 points. Write a method writeChars that takes an
integer n as a parameter and that writes out n characters as follows. The
middle character of the output should always be an asterisk ("*"). If you
are asked to write out an even number of characters, then there will be two
asterisks in the middle. Before the asterisk(s) you should write out
less-than characters ("<"). After the asterisk(s) you should write out
greater-than characters (">"). You should write all of the characters on a
single line of output.
For example, the following calls:
writeChars(5);
System.out.println(); // to complete the line of output
writeChars(8);
System.out.println(); // to complete the line of output
Would produce the following output:
<<*>>
<<<**>>>
If your method is passed 1 or 2 as an argument, it should write out just
asterisks. 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 writeChars below.
3. Linked Lists, 15 points. Write a method min that returns the minimum value
in a list of integers. If the list is empty, return 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 min below.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Fee extends Fo {
public void method1() {
System.out.println("Fee 1");
super.method3();
}
public void method3() {
System.out.println("Fee 3");
}
}
public class Fie extends Fum {
public void method1() {
System.out.println("Fie 1");
}
public void method3() {
System.out.println("Fie 3");
super.method3();
}
}
public class Fo {
public void method2() {
System.out.println("Fo 2");
method3();
}
public void method3() {
System.out.println("Fo 3");
}
}
public class Fum extends Fo {
public void method3() {
System.out.println("Fum 3");
}
}
And assuming the following variables have been defined:
Fum var1 = new Fie();
Object var2 = new Fum();
Fo var3 = new Fee();
Object var4 = new Fie();
Object var5 = new Fo();
Fum var6 = new Fum();
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.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
var5.method3(); ____________________________
var6.method3(); ____________________________
((Fee)var3).method1(); ____________________________
((Fee)var4).method1(); ____________________________
((Fie)var1).method2(); ____________________________
((Fo)var3).method3(); ____________________________
((Fie)var6).method2(); ____________________________
((Fo)var2).method3(); ____________________________
((Fie)var3).method1(); ____________________________
((Fo)var5).method2(); ____________________________
5. Stacks/Queues, 25 points. Write a method reverseHalf that reverses the
order of half the elements of a queue of integers. Your method should
reverse the order of all the elements in even-numbered positions (position
2, 4, 6, etc) assuming that the first value in the queue has position 1.
For example, if the queue originally stores this sequence of integers when
the method is called:
(1, 8, 7, 2, 9, 18, 12, 0)
it should store the following values after the method finishes executing:
(1, 0, 7, 18, 9, 2, 12, 8)
Notice that numbers in odd positions (positions 1, 3, 5, 7) have not moved.
That subsequence of integers is still:
(1, 7, 9, 12)
But notice that the numbers in even positions (positions 2, 4, 6, 8) are now
in reverse order relative to the original. In other words, the original
subsequence:
(8, 2, 18, 0)
has become:
(0, 18, 2, 8)
You should use a single 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.
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.
Method reverseHalf should take a single parameter: the queue to modify.
Write your solution to reverseHalf below.
6. Array Programming, 10 points. Write a method stretch that takes an integer
n as a parameter and that stretches a list of integers to n times its
original size by replacing each integer with n of that integer. For
example, if a variable list stores the following sequence before the method
is called:
(1, 8, 2, 3, 9)
and we make the following call:
list.stretch(3);
Then it should store the following sequence after the call:
(1, 1, 1, 8, 8, 8, 2, 2, 2, 3, 3, 3, 9, 9, 9)
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>
}
Assume that the array has sufficient capacity to store the new list. 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 * m) time where n is the original size of the list and m is
the factor we are "stretching" by.
Your method might be passed a value of 0 (in which case it should make the
list empty), but it should throw an IllegalArgumentException if passed a
value less than 0.
]]>