<![CDATA[
CSE143 Midterm
Spring 2009
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 >= 10) {
mystery(n / 10);
}
if (n % 2 == 0) {
System.out.print("-");
} else {
System.out.print("*");
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(5); _____________________________________
mystery(15); ______________________________________
mystery(304); ______________________________________
mystery(9247); ______________________________________
mystery(43269); ______________________________________
2. Recursive Programming, 15 points. Write a recursive method called substring
that takes as parameters a string, a start index, and an ending index, and
that returns a specified substring of the string. You are implementing a
recursive alternative to the standard substring method. As with the
standard substring method, your method should return the substring that
begins at the start index and that extends to the character just before the
ending index. For example:
substring("hello", 0, 2) should return "he"
substring("hamburger", 4, 8) should return "urge"
substring("smiles", 1, 5) should return "mile"
substring("howdy", 3, 3) should return ""
The method should throw an IllegalArgumentException if the start index is
negative or if the ending index is greater than the length of the string or
if the start index is greater than the ending index. The method should
return an empty string if the two indexes are equal. In implementing this
method, you are restricted to the following string methods:
charAt(index) returns the character at the given index
equals(other) returns whether this String is equal to the other
length() returns the length of the String
You are not allowed to construct any structured objects other than Strings
(no array, StringBuilder, Scanner, 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 isConsecutive that returns
true if a list of integers contains a sequence of consecutive integers and
that returns false otherwise. Consecutive integers are integers that come
one after the other, as in 5, 6, 7, 8, 9, etc. For example, if a variable
called list stores these values:
[3, 4, 5, 6, 7, 8, 9, 10]
then the call:
list.isConsecutive()
should return true. If the list had instead contained this sequence:
[3, 4, 5, 6, 7, 8, 9, 10, 12]
then the call should return false because the numbers 10 and 12 are not
consecutive. The following sequence of values would be consecutive except
for the fact that it appears in reverse order, so the method would return
false in this case:
[3, 2, 1]
Any list with fewer than two values should be considered to be consecutive.
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 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 Water extends Earth {
public void method1() {
System.out.println("Water 1");
}
public void method3() {
System.out.println("Water 3");
}
}
public class Fire {
public void method1() {
System.out.println("Fire 1");
}
public void method2() {
System.out.println("Fire 2");
method1();
}
}
public class Earth extends Fire {
public void method1() {
System.out.println("Earth 1");
super.method1();
}
}
public class Air extends Fire {
public void method3() {
System.out.println("Air 3");
}
}
And assuming the following variables have been defined:
Fire var1 = new Water();
Fire var2 = new Earth();
Fire var3 = new Fire();
Object var4 = new Earth();
Earth var5 = new Water();
Fire var6 = new Air();
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(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
((Water)var4).method2(); ____________________________
((Fire)var4).method2(); ____________________________
((Air)var6).method3(); ____________________________
((Earth)var1).method3(); ____________________________
((Water)var1).method3(); ____________________________
((Water)var2).method3(); ____________________________
((Earth)var1).method2(); ____________________________
((Water)var6).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method called reverseByN that takes a
queue of integers and an integer n as parameters and that reverses each
successive sequence of length n in the queue. For example, suppose that a
variable called q stores the following sequence of values:
front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] back
and we make the following call:
reverseByN(q, 3);
Then q should store the following values after the call:
front [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13] back
Notice that the first three values (1, 2, 3) have been reversed, as have the
next three values (4, 5, 6), the next three values (7, 8, 9), and so on. If
the size of the queue is not an even multiple of n, then there will be a
sequence of fewer than n values at the end. This sequence should be
reversed as well. For example, if q stores this sequence:
front [8, 9, 15, 27, -3, 14, 42, 8, 73, 19] back
and we make the call:
reverseByN(q, 4);
Then q should store the following values after the call:
front [27, 15, 9, 8, 8, 42, 14, -3, 19, 73] back
Notice that the two sequences of length 4 have been reversed along with the
sequence of two values at the end (73, 19). If n is greater than the size
of the queue, then the method should reverse the entire sequence.
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 may not use
recursion to solve this problem and 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 called fromCounts that
converts an ArrayIntList of counts into a new ArrayIntList of values.
Assume that the ArrayIntList that is called stores a sequence of integer
pairs that each indicate a count and a number. For example, suppose that an
ArrayIntList called list stores the following sequence of values:
[5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17]
This sequence of pairs indicates that you have 5 occurrences of 2, followed
by two occurrences of -5, followed by 4 occurrences of 3, and so on. If we
make the following call:
ArrayIntList list2 = list.fromCounts();
Then the variable list2 should store the following sequence of values:
[2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17]
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 assume that the ArrayIntList that is called stores a legal sequence
of pairs (which means it will always have an even size) and that the default
constructor for ArrayIntList will construct an array of sufficient capacity
to store the result. Your method should not change the original list. If
the sequence of pairs is empty, the result should be an empty list.
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 define any auxiliary data structures (no array, String,
ArrayList, etc), and you may not change the original list.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011