<![CDATA[
CSE143 Midterm
Autumn 2007
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 n) {
if (n == 1) {
System.out.print(n);
} else {
System.out.print(n + ", ");
if (n % 2 == 0) {
mystery(n / 2);
} else {
mystery(3 * n + 1);
}
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(1); _____________________________________
mystery(3); ______________________________________
mystery(4); ______________________________________
mystery(5); ______________________________________
mystery(20); ______________________________________
2. Recursive Programming, 15 points. Write a method evens that takes an
integer parameter n and that returns the integer formed by removing the odd
digits from n. For example:
evens(8342116) returns 8426
evens(4109) returns 40
evens(8) returns 8
If a negative number with even digits other than zero is passed to the
method, the result should also be negative, as in:
evens(-34512) returns -42
evens(-163505) returns -60
Any leading zeros in the result should be ignored and if there are no even
digits other than zero in the number, the method should return zero, as in:
evens(3052) returns 2
evens(7010496) returns 46
evens(35179) returns 0
evens(5307) returns 0
evens(7) returns 0
Write your solution to evens below.
3. Linked Lists, 15 points. Write a method printInversions that lists all
inversions in a list of integers. An inversion is defined as a pair of
numbers where the first appears before the second in the list, but the first
is greater than the second. Thus, for a sorted list such as (1, 2, 3, 4)
there are no inversions at all, and printInversions would produce no output.
Suppose that a variable called list stores a list in reverse order, as in
(4, 3, 2, 1). Then the call:
list.printInversions();
would print many inversions:
(4, 3)
(4, 2)
(4, 1)
(3, 2)
(3, 1)
(2, 1)
You must reproduce this format exactly, but the inversions can appear in any
order. Notice that any given number (e.g., 4 in the list above) can produce
several different inversions, because there might be several numbers after
it that are less than it (all of 1, 2, and 3 in the example).
For a list that is partially sorted, as in (3, 1, 4, 2), there are only a
few inversions, and printInversions would produce output like this:
(3, 1)
(3, 2)
(4, 2)
You may assume that the list has no duplicates. Assume that we are using a
linked list that stores integers, as discussed in lecture (handout 8).
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. Your
solution is not allowed to take more than O(n^2) time to run.
Write your solution to printInversions below.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Juice extends Fruit {
public void method2() {
System.out.println("Juice 2");
super.method3();
}
public void method3() {
System.out.println("Juice 3");
}
}
public class Egg extends Milk {
public void method2() {
System.out.println("Egg 2");
}
public void method3() {
System.out.println("Egg 3");
}
}
public class Milk {
public void method1() {
System.out.println("Milk 1");
method3();
}
public void method3() {
System.out.println("Milk 3");
}
}
public class Fruit extends Milk {
public void method3() {
System.out.println("Fruit 3");
super.method3();
}
}
And assuming the following variables have been defined:
Milk var1 = new Fruit();
Juice var2 = new Juice();
Milk var3 = new Egg();
Milk var4 = new Juice();
Milk var5 = new Milk();
Object var6 = new Fruit();
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.method1(); ____________________________
var2.method1(); ____________________________
var3.method1(); ____________________________
var4.method1(); ____________________________
var5.method1(); ____________________________
var6.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
((Juice)var6).method1(); ____________________________
((Fruit)var1).method1(); ____________________________
((Fruit)var3).method2(); ____________________________
((Fruit)var4).method1(); ____________________________
((Juice)var3).method2(); ____________________________
((Egg)var3).method2(); ____________________________
((Fruit)var4).method3(); ____________________________
((Milk)var6).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method shift that takes a stack of
integers and an integer n as parameters and that shifts n values from the
bottom of the stack to the top of the stack. For example, if a variable
called s stores the following sequence of values:
bottom [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] top
and we make the following call:
shift(s, 6);
the method shifts the six values at the bottom of the stack to the top of
the stack and leaves the other values in the same order producing:
bottom [7, 8, 9, 10, 6, 5, 4, 3, 2, 1] top
Notice that the value that was at the bottom of the stack is now at the top,
the value that was second from the bottom is now second from the top, the
value that was third from the bottom is now third from the top, and so on,
and that the four values not involved in the shift are now at the bottom of
the stack in their original order.
If s had stored these values instead:
bottom [7, 23, -7, 0, 22, -8, 4, 5] top
and we make the following call:
shift(s, 3);
then s should store these values after the call:
bottom [0, 22, -8, 4, 5, -7, 23, 7] top
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. Your solution must run in O(n) time.
Your method should throw an IllegalArgumentException if the parameter n is
less than 0 or greater than the number of elements in the stack. 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 shift below.
6. Array Programming, 10 points. Write a method removeFront that takes an
integer n as a parameter and that removes the first n values from a list of
integers. For example, if a variable called list stores this sequence of
values:
[8, 17, 9, 24, 42, 3, 8]
and the following call is made:
list.removeFront(4);
then it should store the following values after the call:
[42, 3, 8]
Notice that the first four values in the list have been removed and the
other values appear in the same order as in the original list.
You are writing a method for the ArrayIntList class discussed in lecture
(handout 3):
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 method should throw an IllegalArgumentException if the parameter n is
less than 0 or greater than the number of elements in the list. Your
solution must run in O(n) time.
Write your solution to removeFront below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011