<![CDATA[
CSE143 Midterm
Autumn 2014
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 Details of Inheritance 20 _____
4 Linked Lists 15 _____
5 Stacks/Queues 25 _____
6 Array Programming 10 _____
----------------------------
Total 100 _____
This is a closed-book/closed-note exam. 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 can also request scratch paper from a TA. You are not
allowed to access any of your own papers during the exam.
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.
The cheat sheet mentions important restrictions on Stacks and Queues that you
must follow.
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 + ", ");
if (n % 2 == 0) {
mystery(n / 2);
} else {
mystery(3 * n + 1);
}
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(1); _____________________________________
mystery(3); ______________________________________
mystery(4); ______________________________________
mystery(5); ______________________________________
mystery(20); ______________________________________
2. Recursive Programming, 15 points. Write a recursive method called
collapseSequences that takes a string and a character as parameters and that
returns a new string that has all sequences of the given character
collapsed to one of that character. A sequence is a group of consecutive
characters that are all the same. Consider the following call:
collapseSequence("-this----has maaany--dashes---", '-')
The string has 5 sequences of dashes of varying lengths. Each is reduced to
a single occurrence of the dash producing "-this-has maaany-dashes-".
Notice that other characters are unchanged. If you make the call:
collapseSequence("eecckk!!, he's meeeping meep", 'e')
the method should return "ecckk!!, he's meping mep". In implementing this
method, 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(start, stop) returns a new string composed of characters
from start index (inclusive) to stop index
(exclusive)
substring(start) returns a new string composed of characters
from start index (inclusive) to the string end
You are not allowed to construct any structured objects other than Strings
(no array, ArrayList, 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. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Fork extends Dish {
public void method2() {
System.out.println("Fork 2");
}
public void method3() {
System.out.println("Fork 3");
}
}
public class Bowl extends Soap {
public void method2() {
System.out.println("Bowl 2");
}
public void method3() {
System.out.println("Bowl 3");
}
}
public class Soap {
public void method1() {
System.out.println("Soap 1");
method3();
}
public void method3() {
System.out.println("Soap 3");
}
}
public class Dish extends Soap {
public void method3() {
System.out.println("Dish 3");
super.method3();
}
}
And assuming the following variables have been defined:
Soap var1 = new Dish();
Fork var2 = new Fork();
Soap var3 = new Bowl();
Soap var4 = new Fork();
Soap var5 = new Soap();
Object var6 = new Dish();
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.method1(); ____________________________
var2.method1(); ____________________________
var3.method1(); ____________________________
var4.method1(); ____________________________
var5.method1(); ____________________________
var6.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
((Fork)var6).method1(); ____________________________
((Dish)var3).method2(); ____________________________
((Fork)var4).method2(); ____________________________
((Fork)var3).method2(); ____________________________
((Bowl)var3).method2(); ____________________________
((Fork)var1).method1(); ____________________________
((Dish)var4).method3(); ____________________________
((Soap)var6).method3(); ____________________________
4. Linked Lists, 15 points. Fill in the "code" column in the following table
providing a solution that will turn the "before" picture into the "after"
picture by modifying links between the nodes shown. You are not allowed to
change any existing node's data field value and you are not allowed to
construct any new nodes, but you are allowed to declare and use variables of
type ListNode (often called "temp" variables). You are limited to at most
two variables of type ListNode for each of the four subproblems below.
You are writing code for the ListNode 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>
}
As in the lecture examples, all lists are terminated by null and the
variables p and q have the value null when they do not point to anything.
before after code
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2]->[3] | p->[1]->[2] |
| |
| |
q | q->[3] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[3] | p->[1]->[2]->[3] |
| |
| |
q->[2] | q |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2] | p->[2]->[4] |
| |
| |
q->[3]->[4] | q->[3]->[1] |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2]->[3] | p->[2]->[1]->[4] |
| |
| |
q->[4]->[5] | q->[3]->[5] |
| |
| |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
5. Stacks/Queues, 25 points. Write a method called parityMatches that takes
two stacks of integers as parameters and that returns a count of the number
of elements in corresponding positions that have the same parity. Two
numbers are considered to have the same parity if they are either both even
or both odd. Suppose, for example, that two stacks store these values:
s1: bottom [3, 4, 5] top s2: bottom [37, 14, 24] top
The method compares values in corresponding positions in the two stacks (3
and 37, 4 and 14, 5 and 24). Of these pairs, two have the same parity. The
third pair (5 and 24) do not have the same parity. Therefore the method
call parityMatches(s1, s2) would return 2.
You may assume that the two stacks store the same number of values (your
method should throw an IllegalArgumentException if they have different
numbers of elements). You may also assume that all of the numbers stored in
the list are greater than or equal to 0. Your method is to examine the two
stacks but must return them to their original state before terminating.
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. Your solution must run in O(n) time
where n is the size of the stacks. Use the Stack and Queue structures
described in the cheat sheet and obey the restrictions described there
(recall that you can't use the peek method or a foreach loop or iterator).
6. Array Programming, 10 points. Write a method called stutter that doubles
the size of a list of integers by replacing every integer in the list with
two of that integer. For example, if a variable called list stores the
following:
[1, 8, 19, 4, 17]
and we make the following call:
list.stutter();
then it should store the following sequence of integers after the call:
[1, 1, 8, 8, 19, 19, 4, 4, 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 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 your solution must run in O(n) time.
You may assume that elementData is large enough to fit the longer list.
CSE143 Midterm Cheat Sheet
Queues should be constructed using the Queue<E> interface and the
LinkedList<E> implementation. For example, to construct a queue of String
values, you would say:
Queue<String> q = new LinkedList<String>();
Stacks should be constructed using the Stack<E> class (there is no interface).
For example, to construct a stack of String values, you would say:
Stack<String> s = new Stack<String>();
To transfer from a queue to a stack:
while (!q.isEmpty()) {
s.push(q.remove());
}
To transfer from a stack to a queue:
while (!s.isEmpty()) {
q.add(s.pop());
}
-------------------------------------------------------------------------------
For Stack<E>, you are limited to the following operations:
public void push(E value); // push given value onto top of the stack
public E pop(); // removes and returns the top of the stack
public boolean isEmpty(); // returns whether or not stack is empty
public int size(); // returns number of elements in the stack
For Queue<E> you are allowed the following operations:
public void add(E value); // inserts given value at the end of the queue
public E remove(); // removes and returns the front of the queue
public boolean isEmpty(); // returns whether or not queue is empty
public int size(); // returns number of elements in the queue
YOU ARE NOT ALLOWED TO USE FOREACH LOOPS OR ITERATORS FOR EITHER STRUCTURE.
-------------------------------------------------------------------------------
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011