<![CDATA[
CSE143 Midterm
Fall 2010
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 blank page 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.
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();
}
1. Recursive Tracing, 15 points. Consider the following method:
public int mystery(int n, int m) {
if (n == 0 || m == 0) {
return 0;
} else if (n % 10 == m % 10) {
return 1 + mystery(n / 10, m / 10);
} else {
return mystery(n / 10, m / 10);
}
}
For each call below, indicate what output is produced:
Method Call Value Returned
mystery(18, 0) _____________________________________
mystery(8, 18) ______________________________________
mystery(25, 21) ______________________________________
mystery(305, 315) ______________________________________
mystery(20734, 1724) ______________________________________
2. Recursive Programming, 15 points. Write a recursive method called
isPalindrome that takes a string as a parameter and that returns true if the
string is a palindrome and false if it is not. A palindrome is a string
like "racecar" that has the same sequence of characters when written
forwards and backwards. Notice that in a palindrome, the first and last
characters match, as do the second and second-to-last, the third and
third-to-last, and so on. The table below includes various method calls and
the value returned:
Method Call Result Method Call Result
----------------------------------------------------------------------
isPalindrome("radar") true isPalindrome("123321") true
isPalindrome("hah") true isPalindrome("peer") false
isPalindrome("peep") true isPalindrome("ab") false
isPalindrome("x") true isPalindrome("a ba") false
isPalindrome("") true isPalindrome("ABba") false
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)
For example, if a String s stores the text "hello", then:
s.charAt(0) returns 'h'
s.length() returns 5
s.substring(1, 3) returns "el"
You are not allowed to construct any structured objects (no array,
ArrayList, String, 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 numUnique that returns the
number of unique values in a sorted (nondecreasing) list of integers.
Because the list is in sorted order, the duplicates will be grouped
together. For example, if a variable called "list" stores these values:
[5, 7, 7, 7, 8, 22, 22, 23, 31, 35, 35, 40, 40, 40, 41]
then the call list.numUnique() should return 9 because this list has 9
unique values (5, 7, 8, 22, 23, 31, 35, 40, and 41). The table below
indicates various possible values for a variable list and the value that
would be returned by the call list.numUnique():
List Value List Value
Contents Returned Contents Returned
------------------------------- -------------------------------
[] 0 [0, 10, 15, 23, 45] 5
[42] 1 [1, 2, 2, 3, 3, 3] 3
[3, 3, 3] 1 [-8, -5, -5, 0, 17] 4
[4, 5] 2 [42, 42, 42, 42, 42] 1
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 Page extends Folder {
public void method3() {
System.out.println("Page 3");
}
}
public class Bit extends Bunch {
public void method1() {
System.out.println("Bit 1");
}
public void method3() {
System.out.println("Bit 3");
}
}
public class Folder extends Bunch {
public void method1() {
System.out.println("Folder 1");
}
public void method3() {
System.out.println("Folder 3");
super.method3();
}
}
public class Bunch {
public void method2() {
System.out.println("Bunch 2");
method3();
}
public void method3() {
System.out.println("Bunch 3");
}
}
And assuming the following variables have been defined:
Object var1 = new Folder();
Bunch var2 = new Bunch();
Bunch var3 = new Bit();
Folder var4 = new Page();
Object var5 = new Bunch();
Bunch var6 = new Page();
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(); ____________________________
((Bit)var6).method1(); ____________________________
((Bunch)var1).method1(); ____________________________
((Bunch)var1).method2(); ____________________________
((Folder)var1).method3(); ____________________________
((Folder)var6).method1(); ____________________________
((Page)var1).method1(); ____________________________
((Page)var4).method2(); ____________________________
((Folder)var3).method1(); ____________________________
5. Stacks/Queues, 25 points. Write a method removeMax that takes a stack of
integers as a parameter and that removes and returns the largest value from
the stack. For example, if a variable called s stores the following:
bottom [19, 8, 3, 19, 7, 3, 2, 42, 19, 3, 2, 7, 12, -8, 4] top
and we make the following call:
int n = removeMax(s);
the method removes and returns the value 42 from the stack, so that the
variable n will be 42 after the call and s will store the following values:
bottom [19, 8, 3, 19, 7, 3, 2, 19, 3, 2, 7, 12, -8, 4] top
If the maximum value appears more than once, all occurrences of the maximum
should be removed from the stack. For example, given the ending value of
the stack above, if we again call removeMax(s), the method would return 19
and would leave the stack in the following state:
bottom [8, 3, 7, 3, 2, 3, 2, 7, 12, -8, 4] 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 may not use
recursion to solve this problem and your solution must run in O(n) time
where n is the size of the stack. Use the Stack and Queue interfaces and
LinkedQueue and ArrayStack implementations described in the cheat sheet.
Your method should throw an IllegalArgumentException if the stack is empty.
6. Array Programming, 10 points. Write a method collapse that collapses a list
of integers by replacing each successive pair of integers with the sum of
the pair. For example, if a variable called list stores this sequence:
[7, 2, 8, 9, 4, 13, 7, 1, 9, 10]
and the following call is made:
list.collapse();
The first pair should be collapsed into 9 (7 + 2), the second pair should be
collapsed into 17 (8 + 9), the third pair should be collapsed into 17 (4 +
13) and so on to yield:
[9, 17, 17, 8, 19]
If the list stores an odd number of elements, the final element is not
collapsed. For example, the sequence:
[1, 2, 3, 4, 5]
would collapse into:
[3, 7, 5]
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 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 to be collapsed.
This page can be used for scratch work or for answers
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011