<![CDATA[
CSE143 Midterm
Spring 2011
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
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 _____
This is a closed-book/closed-note exam. You are allowed to have one
hand-written index card up to 5" x 8". Space is provided for your answers.
There is a "cheat sheet" at the end that you can use as scratch paper or to
write answers. You are not allowed to access any other paper during the exam
(not even scratch paper). Use the backs of the pages of this test if
necessary. Anyone caught with extra paper will lose at least 10 points.
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 + ", ");
mystery(n / 2);
System.out.print(", " + n);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(1); ___________________________________________
mystery(3); ____________________________________________
mystery(4); ____________________________________________
mystery(6); ____________________________________________
mystery(12); ____________________________________________
2. Recursive Programming, 15 points. Write a recursive method called replace
that takes a string and two characters as parameters and that returns a new
string with all occurrences of the first character replaced by the second
character. The table below indicates the result of various method calls:
Method Call Result
----------------------------------------------------------------------
replace("to be or not to be", 'e', 'o'); "to bo or not to bo"
replace("to be or not to be", 'o', '-'); "t- be -r n-t t- be"
replace("to be or not to be", 'm', '!'); "to be or not to be"
replace("Mississippi", 'i', 'e'); "Messesseppe"
replace("hah!", 'h', '*'); "*a*!"
replace("Hah!", 'h', '*'); "Ha*!"
replace("", 'g', 'h'); ""
You are restricted to the following String methods:
charAt(index) returns the character at the given index
length() returns the length of the string
substring(fromIndex, toIndex) returns a new string that is a substring
of this string from startIndex
(inclusive) to stopIndex (exclusive)
substring(fromIndex) Returns a new string that is a substring
of this string from startIndex
(inclusive) to the end of the String
For example, if a String s stores the text "hello", then:
s.charAt(0) returns 'h' s.substring(1, 3) returns "el"
s.length() returns 5 s.substring(2) returns "llo"
You will be constructing new strings, but you are not allowed to construct
any other structured objects (no array, ArrayList, StringBuilder, 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 minGap that returns the
minimum gap between adjacent values in a list of integers. The gap between
two adjacent values in a list is defined as the second value minus the first
value. For example, suppose a variable called list stores these values:
[1, 3, 6, 7, 12]
The first gap is 2 (3 - 1), the second gap is 3 (6 - 3), the third gap is 1
(7 - 6), and the fourth gap is 5 (12 - 7). Thus, the call:
list.minGap()
should return 1 because that is the smallest gap. Notice that the minimum
gap could be a negative number. For example, if list stores the following:
[3, 5, 11, 4, 8]
The gaps are 2 (5 - 3), 6 (11 - 5), -7 (4 - 11), and 4 (8 - 4). Of these
values, -7 is the smallest, so it would be returned.
Your method should return 0 if the list has fewer than 2 elements. 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>
}
Your method should not modify the list contents and is required to run in
O(n) time where n is the length of the list. 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 Horse extends Cat {
public void method1() {
System.out.println("Horse 1");
super.method2();
}
public void method2() {
System.out.println("Horse 2");
}
}
public class Dog {
public void method2() {
System.out.println("Dog 2");
}
}
public class Pig extends Horse {
public void method2() {
System.out.println("Pig 2");
}
}
public class Cat extends Dog {
public void method3() {
System.out.println("Cat 3");
method2();
}
}
And assuming the following variables have been defined:
Cat var1 = new Pig();
Dog var2 = new Dog();
Dog var3 = new Cat();
Object var4 = new Horse();
Cat var5 = new Horse();
Horse var6 = new Pig();
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(); ____________________________
((Pig)var5).method1(); ____________________________
((Cat)var3).method3(); ____________________________
((Cat)var4).method1(); ____________________________
((Pig)var1).method1(); ____________________________
((Horse)var4).method1(); ____________________________
((Cat)var2).method3(); ____________________________
((Horse)var3).method1(); ____________________________
((Dog)var4).method2(); ____________________________
5. Stacks/Queues, 25 points. Write a method called equals that takes as
parameters two stacks containing lists of integers and that returns true if
the two stacks are equal and that returns false otherwise. Two stacks are
considered equal if they store the same number of values and those values
appear in the same order. Your method is to examine the two stacks but must
return them to their original state before terminating.
For example, if the following stack variables are defined:
s1 bottom [3, 18, 9, 42] top
s2 bottom [3, 18, 9, 42] top
s3 bottom [3, 18, 9, 42, 17] top
s4 bottom [42, 9, 18, 3] top
then the call equals(s1, s2) would return true and the calls equals(s1, s3),
equals(s1, s4), equals(s2, s3), and equals(s3, s4) would return false. Two
empty stacks would be considered equal to each other.
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. Your method should be efficient by
returning false immediately if the two stacks are not of the same size and
by not examining more values from the two stacks once it has found a
difference. Use the Stack interface and ArrayStack implementation described
in the cheat sheet.
6. Array Programming, 10 points. Write a method called 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:
[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:
public class ArrayIntList {
private int[] elementData; // list of integers
private int size; // current # of elements in the list
<methods>
}
Your method should throw an IllegalArgumentException if the parameter n is
less than 0 or greater than the number of elements in the list. You are not
to call any other 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 where n is the length of the list.
CSE143 Midterm Cheat Sheet
Queues should be constructed using the Queue<E> interface and the
LinkedQueue<E> implementation. For example, to construct a queue of String
values, you would say:
Queue<String> q = new LinkedQueue<String>();
Stacks should be constructed using the Stack<E> interface and the
ArrayStack<E> implementation. For example, to construct a stack of String
values, we would say:
Stack<String> s = new ArrayStack<String>();
To transfer from a queue to a stack:
while (!q.isEmpty())
s.push(q.dequeue());
To transfer from a stack to a queue:
while (!s.isEmpty())
q.enqueue(s.pop());
-------------------------------------------------------------------------------
// Interface Queue defines a set of operations for manipulating a FIFO
// (First In First Out) structure that can be used to store objects.
public interface Queue<E> {
// post: given value inserted at the end of the queue
public void enqueue(E value);
// pre : !isEmpty()
// post: removes and returns the value at the front of the queue
public E dequeue();
// post: returns true if the queue is empty, false otherwise
public boolean isEmpty();
// post: returns the current number of elements in the queue
public int size();
}
-------------------------------------------------------------------------------
// Interface Stack defines a set of operations for manipulating a LIFO
// (Last In First Out) structure that can be used to store elements of
// type E.
public interface Stack<E> {
// post: given value is pushed onto the top of the stack
public void push(E value);
// pre : !isEmpty()
// post: removes and returns the value at the top of the stack
public E pop();
// post: returns true if the stack is empty, false otherwise
public boolean isEmpty();
// post: returns the current number of elements in the stack
public int size();
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011