<![CDATA[
CSE143 Midterm
Winter 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.
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 int mystery(int x, int y) {
if (x % 2 == 1 || y % 2 == 1) {
return 1;
} else {
return 2 * mystery(x / 2, y / 2);
}
}
For each call below, indicate what value is returned:
Method Call Value Returned
mystery(4, 19) ______________
mystery(32, 56) ______________
mystery(12, 20) ______________
mystery(4, 18) ______________
mystery(48, 128) ______________
2. Recursive Programming, 15 points. Write a method writeSquares that takes an
integer n as a parameter and that writes the first n squares to System.out
separated by commas with the odd squares in descending order followed by the
even squares in ascending order. For example, the call:
writeSquares(5);
should produce the following output:
25, 9, 1, 4, 16
The odd squares (25, 9, and 1) appear first in descending order followed by
the even squares (4 and 16) in ascending order. Notice that commas are used
to separate consecutive values in the list. Your method should send its
output to System.out and should not call println. For example, the
following calls:
writeSquares(5);
System.out.println(); // to complete the line of output
writeSquares(1);
System.out.println(); // to complete the line of output
writeSquares(8);
System.out.println(); // to complete the line of output
should produce exactly three lines of output:
25, 9, 1, 4, 16
1
49, 25, 9, 1, 4, 16, 36, 64
You must exactly reproduce the format of these examples. 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 writeSquares below.
3. Linked Lists, 15 points. Write a method printEvenOddSum that prints the sum
of the values in even positions and the sum of values in odd positions in a
list of integers. For example, if a variable called list stores the
following sequence of values:
[1, 18, 2, 7, 33, 39, 12]
then the call:
list.printEvenOddSum();
should print the sum of the values in even positions (1, 2, 33, 12) and the
sum of the values in odd positions (18, 7, 39). Notice that it doesn't
matter whether the number itself is odd or even. What matters is whether
the value is in an odd or even position. Also notice that we are using the
standard zero-based indexing convention that the first value is considered
to be at position 0.
Thus, the method should produce this output for the sample list:
even sum = 48
odd sum = 64
You must exactly reproduce the format of this output. You may not make
any assumptions about the number of elements in the list.
Assume that we are using a linked list that stores integers, as discussed in
lecture (handouts 6 and 7).
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 printEvenOddSum below.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Fog extends Sleet {
public void method1() {
System.out.println("Fog 1");
}
public void method3() {
System.out.println("Fog 3");
}
}
public class Rain extends Snow {
public void method1() {
System.out.println("Rain 1");
}
public void method2() {
System.out.println("Rain 2");
}
}
public class Sleet extends Snow {
public void method2() {
System.out.println("Sleet 2");
super.method2();
method3();
}
public void method3() {
System.out.println("Sleet 3");
}
}
public class Snow {
public void method2() {
System.out.println("Snow 2");
}
public void method3() {
System.out.println("Snow 3");
}
}
And assuming the following variables have been defined:
Snow var1 = new Sleet();
Rain var2 = new Rain();
Snow var3 = new Fog();
Object var4 = new Snow();
Sleet var5 = new Fog();
Snow var6 = new Rain();
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(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
var5.method3(); ____________________________
((Rain)var3).method1(); ____________________________
((Fog)var5).method1(); ____________________________
((Sleet)var3).method1(); ____________________________
((Sleet)var3).method3(); ____________________________
((Fog)var6).method3(); ____________________________
((Snow)var4).method2(); ____________________________
((Sleet)var4).method3(); ____________________________
((Rain)var6).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method isConsecutive that takes a stack
of integers as a parameter and that returns whether or not the stack
contains a sequence of consecutive integers starting from the bottom of the
stack (returning true if it does, returning false if it does not).
Consecutive integers are integers that come one after the other, as in 5, 6,
7, 8, 9, etc. So if a stack s stores the following values:
bottom [3, 4, 5, 6, 7, 8, 9, 10] top
then the call:
isConsecutive(s)
should return true. If the stack had instead contained this set of values:
bottom [3, 4, 5, 6, 7, 8, 9, 10, 12] top
then the call should return false because the numbers 10 and 12 are not
consecutive. Notice that we look at the numbers starting at the bottom of
the stack. The following sequence of values would be consecutive except for
the fact that it appears in reverse order, so the method would return false:
bottom [3, 2, 1] top
Your method must restore the stack so that it stores the same sequence of
values after the call as it did before. Any stack with fewer than two
values should be considered to be a list of consecutive integers.
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.
Write your solution to isConsecutive below.
6. Array Programming, 10 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)
The inversions can appear in any order, so this is just one possible correct
output. 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. 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.
Write your solution to printInversions below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011