<![CDATA[
CSE143 Midterm
Spring 2008
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 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 removeLast that removes the last
occurrence of an integer (if any) from a list of integers. For example,
suppose that a variable called "list" stores this sequence of values:
[3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0, 3]
If we repeatedly make the following call:
list.removeLast(3);
Then the list will take on the following sequence of values:
[3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0]
[3, 2, 3, 3, 19, 8, 43, 64, 1, 0]
[3, 2, 3, 19, 8, 43, 64, 1, 0]
[3, 2, 19, 8, 43, 64, 1, 0]
[2, 19, 8, 43, 64, 1, 0]
[2, 19, 8, 43, 64, 1, 0]
Notice that once we reach a point where no more 3's occur in the list, then
calling the method has no effect.
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>
}
You may not call any other methods of the LinkedIntList class to solve this
problem and your solution must run in O(n) time.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Cup extends Box {
public void method1() {
System.out.println("Cup 1");
}
public void method2() {
System.out.println("Cup 2");
super.method2();
}
}
public class Pill {
public void method2() {
System.out.println("Pill 2");
}
}
public class Jar extends Box {
public void method1() {
System.out.println("Jar 1");
}
public void method2() {
System.out.println("Jar 2");
}
}
public class Box extends Pill {
public void method2() {
System.out.println("Box 2");
}
public void method3() {
method2();
System.out.println("Box 3");
}
}
And assuming the following variables have been defined:
Box var1 = new Box();
Pill var2 = new Jar();
Box var3 = new Cup();
Box var4 = new Jar();
Object var5 = new Box();
Pill var6 = new Pill();
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 (you may abbreviate these as "ce" and "re" or "c.e." and "r.e.").
Statement Output
------------------------------------------------------------
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
((Cup)var1).method1(); ____________________________
((Jar)var2).method1(); ____________________________
((Cup)var3).method1(); ____________________________
((Cup)var4).method1(); ____________________________
((Jar)var4).method2(); ____________________________
((Box)var5).method2(); ____________________________
((Pill)var5).method3(); ____________________________
((Jar)var2).method3(); ____________________________
((Cup)var3).method3(); ____________________________
((Cup)var5).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method interleave that takes a queue of
integers as a parameter and that rearranges the elements by interleaving
the first half of the list with the second half of the list. For example,
suppose a variable called q stores the following sequence of values:
front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] back
and we make the following call:
interleave(q);
Consider the two halves of this list:
first half: [1, 2, 3, 4, 5] second half: [6, 7, 8, 9, 10]
These are combined in an alternating fashion to form a sequence of
interleave pairs: the first values from each half (1 and 6), then the second
values from each half (2 and 7), then the third values from each half (3 and
8), and so on. In each pair, the value from the first half appears before
the value from the second half. Thus, after the call, the queue stores the
following values:
front [1, 6, 2, 7, 3, 8, 4, 9, 5, 10] back
This example uses sequential integers to make the interleaving more obvious,
but the same process can be applied to any sequence of even length. For
example, if q had instead stored these values:
front [2, 8, -5, 19, 7, 3, 24, 42] back
then the method would have rearranged the list to become:
front [2, 7, 8, 3, -5, 24, 19, 42] back
Your method should throw an IllegalArgumentException if the queue does not
have even length. You are to use one 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.
Your solution must run in O(n) time. Use the Stack and Queue interfaces and
the ArrayStack and LinkedQueue implementations discussed in lecture.
6. Array Programming, 10 points. Write a method removeOddPositions that removes
the values in odd-numbered positions (if any) from a list of integers. For
example if a variable called list stores these values:
[8, 13, 17, 4, 9, 12, 98]
and the following call is made:
list.removeOddPositions();
The list should store this sequence after the call:
[8, 17, 9, 98]
The method removed the values at odd positions (positions 1, 3, and 5),
otherwise preserving the order of the remaining elements. Notice that it
doesn't matter whether the value itself is odd or even but instead whether
it appears in an odd position or even position.
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 not call any other methods of the ArrayIntList methods to solve this
problem, you are not allowed to define any auxiliary data structures (no
array, ArrayList, etc), and your solution must run in O(n) time.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011