<![CDATA[
CSE143 Midterm
Spring 2010
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 allowed to abbreviate "compiler error" and "runtime error" for the
inheritance question (as in "ce" and "re" or "c.e." and "r.e."), but you should
otherwise NOT use any abbreviations on the exam.
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 static void mystery(int n) {
if (n < 0) {
mystery(-n);
} else if (n < 10) {
System.out.print(n);
} else {
mystery(n / 10);
int digit = n % 10;
System.out.print(", " + digit % 3);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(7); _____________________________________
mystery(38); ______________________________________
mystery(749); ______________________________________
mystery(-6842); ______________________________________
mystery(954023); ______________________________________
2. Recursive Programming, 20 points. Write a recursive method called
parenthesize that takes a String and an integer n as parameters and that
prints the string inside n sets of parentheses. For example, this code:
parenthesize("Joe", 2);
System.out.println(); // to complete line of output
parenthesize("The University of Washington", 6);
System.out.println(); // to complete line of output
parenthesize("midterm", 1);
System.out.println(); // to complete line of output
should produce these 3 lines of output:
((Joe))
((((((The University of Washington))))))
(midterm)
Your method should throw an IllegalArgumentException if passed a negative
number. It could be passed 0, as in:
parenthesize("CS143, Spring 2010", 0);
System.out.println(); // to complete line of output
In this case the output would have no (i.e., 0) parentheses:
CS143, Spring 2010
You are not allowed to construct any structured objects (no array,
ArrayList, String, StringBuilder, 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 called hasOddEven that returns true
if a list of integers contains at least one odd and at least one even and
that returns false otherwise. The table below indicates various possible
values for a variable list and the value that would be returned by the call
list.hasOddEven():
List Value List Value
Contents Returned Contents Returned
------------------------------- -------------------------------
[] false [1, 3, 2, 5] true
[2] false [42, 0, 38, 72, 4] false
[13] false [39, 71, 17, 3, 1] false
[4, 5] true [38, 40, 24, 4, 3] true
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
<constructors>
}
public class LinkedIntList {
private ListNode front;
<methods>
}
Your method is required to be efficient in that it should stop examining
list values once it has determined that the list has both an odd and an even
value. For example, if the first two values in a list are an odd and an
even, then the method should examine only those two values.
You may not call any other methods of the LinkedIntList class and you may
not construct any structured objects to solve this problem.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Gorge extends Cliff {
public void method2() {
System.out.println("Gorge 2");
}
public void method3() {
System.out.println("Gorge 3");
}
}
public class Hill extends Peak {
public void method2() {
System.out.println("Hill 2");
}
public void method3() {
System.out.println("Hill 3");
}
}
public class Peak {
public void method1() {
System.out.println("Peak 1");
method3();
}
public void method3() {
System.out.println("Peak 3");
}
}
public class Cliff extends Peak {
public void method3() {
System.out.println("Cliff 3");
super.method3();
}
}
And assuming the following variables have been defined:
Peak var1 = new Cliff();
Gorge var2 = new Gorge();
Peak var3 = new Hill();
Peak var4 = new Gorge();
Peak var5 = new Peak();
Object var6 = new Cliff();
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(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
((Gorge)var6).method1(); ____________________________
((Cliff)var1).method1(); ____________________________
((Cliff)var3).method2(); ____________________________
((Cliff)var4).method1(); ____________________________
((Gorge)var3).method2(); ____________________________
((Hill)var3).method2(); ____________________________
((Cliff)var4).method3(); ____________________________
((Peak)var6).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method called mirror that takes a stack
of integers as a parameter and that doubles the size of the stack by
appending the mirror image of the original sequence at the top of the stack.
The mirror image is the same sequence of values in reverse order. For
example, suppose that a variable called s stores the following values:
bottom [1, 3, 2, 7] top
and we make the following call:
mirror(s);
then it should store the following values after the call:
bottom [1, 3, 2, 7, 7, 2, 3, 1] top
Notice that it has been doubled in size by having the original sequence
appearing in reverse order at the top of the stack. If the original stack
is empty, your method should not change it.
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 may not use
recursion to solve this problem and your solution must run in O(n) time
where n is the size of the stack. Use the Stack and Queue interfaces and
the ArrayStack and LinkedQueue implementations discussed in lecture.
6. Array Programming, 10 points. Write a method reverseCopy that returns a new
ArrayIntList that contains a copy of the values in the original list in
reverse order. For example, if a variable list stores the following
sequence of values:
[17, 42, 3, 8, 9, 12]
and the following call is made:
ArrayIntList list2 = list.reverseCopy();
Then the variable list2 should store the following sequence of values:
[12, 9, 8, 3, 42, 17]
The original list should not be changed by the method. The new list should
have the same capacity as the original. Remember that there is a
constructor for ArrayIntList that takes a capacity as a parameter:
// pre : capacity >= 0
// post: constructs an empty list with the given capacity
public ArrayIntList(int capacity)
If the original list is empty, the result should be an empty list. 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
<methods>
}
You may call the ArrayIntList constructor, but otherwise you may not call
any other methods of the ArrayIntList class to solve this problem. You are
not allowed to call methods from the Arrays class like the copyOf method.
Your solution must run in O(n) time where n is the length of the list.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011