<![CDATA[
CSE143 Midterm
Winter 2006
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 may use a calculator to do simple arithmetic, although you are not allowed
to program the calculator or to run a stored program.
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 int mystery(int x, int y) {
if (x > y) {
return 0;
} else {
return mystery(x + 1, y) + 2 * x - 1;
}
}
For each call below, indicate what value is returned:
Method Call Value Returned
mystery(1, 3) ______________
mystery(4, 4) ______________
mystery(3, 5) ______________
mystery(1, 5) ______________
mystery(4, 7) ______________
2. Recursive Programming, 15 points. Write a method countToBy that takes
integer parameters n and m and that produces output indicating how to count
to n in increments of m. For example, to count to 10 by 1 you'd say:
countToBy(10, 1);
which should produce the following output:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
The increment does not have to be 1. For example, the following call
indicates that we want to count to 25 in increments of 4:
countToBy(25, 4);
which produces this output:
1, 5, 9, 13, 17, 21, 25
It will not always be possible to start counting at 1. The first number
should always be in the range of 1 to m inclusive. So if you instead count
to 30 by 4, you have to start with 2. So this call:
countToBy(30, 4);
produces this output:
2, 6, 10, 14, 18, 22, 26, 30
It is possible that only one number will be printed. All output should
appear on the same line. For example, the following calls:
countToBy(34, 5);
System.out.println(); // to complete the line of output
countToBy(3, 6);
System.out.println(); // to complete the line of output
countToBy(17, 3);
System.out.println(); // to complete the line of output
should produce the following output:
4, 9, 14, 19, 24, 29, 34
3
2, 5, 8, 11, 14, 17
You must exactly reproduce the format of the examples above. Your method
should throw an IllegalArgumentException if either m or n is 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 countToBy below.
3. Linked Lists, 15 points. Write a method lastIndexOf that takes an integer n
as a parameter and that returns the index of the last occurrence of n in a
list of integers and that returns -1 if n does not appear in the list. We
are using the normal 0-based indexing scheme. For example, if a variable
called list stores the following sequence of values:
(1, 18, 2, 7, 18, 39, 18, 40)
then the call:
list.lastIndexOf(18)
should return 6 because that is the index of the last occurrence of 18 in
the list. If the call had instead been:
list.lastIndexOf(3)
The method would return -1 because 3 does not appear in the list.
You may not make any assumptions about how many elements are in the list.
Assume that we are using a linked list that stores integers, as discussed in
lecture (handouts 7 and 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.
Write your solution to lastIndexOf below.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Bay extends Lake {
public void method1() {
System.out.println("Bay 1");
super.method2();
}
public void method2() {
System.out.println("Bay 2");
}
}
public class Pond {
public void method2() {
System.out.println("Pond 2");
}
}
public class Ocean extends Bay {
public void method2() {
System.out.println("Ocean 2");
}
}
public class Lake extends Pond {
public void method3() {
System.out.println("Lake 3");
method2();
}
}
And assuming the following variables have been defined:
Lake var1 = new Ocean();
Pond var2 = new Pond();
Pond var3 = new Lake();
Object var4 = new Bay();
Lake var5 = new Bay();
Bay var6 = new Ocean();
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(); ____________________________
((Ocean)var5).method1(); ____________________________
((Lake)var3).method3(); ____________________________
((Lake)var4).method1(); ____________________________
((Ocean)var1).method1(); ____________________________
((Bay)var4).method1(); ____________________________
((Lake)var2).method3(); ____________________________
((Ocean)var5).method1(); ____________________________
((Pond)var4).method2(); ____________________________
5. Stacks/Queues, 25 points. Write a method isPalindrome that takes a Queue of
integers as a parameter and that returns whether or not the numbers in the
queue represent a palindrome (true if they do, false otherwise). A sequence
of numbers is considered a palindrome if it is the same in reverse order.
For example, suppose a Queue called q stores this sequence of values:
front [3, 8, 17, 9, 17, 8, 3] back
Then the following call:
isPalindrome(q)
should return true because this sequence is the same in reverse order. If
the list had instead stored these values:
front [3, 8, 17, 9, 4, 17, 8, 3] back
the call on isPalindrome would instead return false because this sequence is
not the same in reverse order (the 9 and 4 in the middle don't match).
The empty queue should be considered a palindrome. You may not make any
assumptions about how many elements are in the queue and your method must
restore the queue so that it stores the same sequence of values after the
call as it did before.
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. 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 isPalindrome below.
6. Array Programming, 10 points. Write a method isPairwiseSorted that returns
whether or not a list of integers is pairwise sorted (true if it is, false
otherwise). A list is considered pairwise sorted if each successive pair of
numbers is in sorted (non-decreasing) order. For example, if a variable
called list stores the following sequence of values:
[3, 8, 2, 5, 19, 24, -3, 0, 4, 4, 8, 205, 42]
then the following call:
list.isPairwiseSorted()
should return the value true because the successive pairs of this list are
all sorted: (3, 8), (2, 5), (19, 24), (-3, 0), (4, 4), (8, 205). Notice
that the extra value 42 at the end had no effect on the result because it is
not part of a pair.
If the list had instead stored the following values:
[1, 9, 3, 17, 4, 28, -5, -3, 0, 42, 308, 409, 19, 17, 2, 4]
then the method should return the value false because the pair [19, 17] is
not in sorted order. If a list is so short that it has no pairs, then it is
considered to be pairwise sorted.
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>
}
You are not to call any other IntList methods to solve this problem.
Write your solution to isPairwiseSorted below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011