<![CDATA[
CSE143 Midterm
Winter 2018
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
Student #____________________________
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 ArrayIntList 10 _____
6 Stacks/Queues 25 _____
----------------------------
Total 100 _____
This is a closed-book/closed-note exam. Space is provided for your 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 at the end of the exam 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 and smart watches. 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 a TA and exit quietly.
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 value is returned.
Method Call Value Returned
mystery(42, 0) _____________________________________
mystery(5, 25) _____________________________________
mystery(752, 792) _____________________________________
mystery(3092, 5028) _____________________________________
mystery(61903, 1930) _____________________________________
2. Recursive Programming, 15 points. Write a recursive method called
groupChars that takes a string as a parameter and that returns a new string
obtained by inserting parentheses and brackets so as to group the
characters. For strings with only one or two characters, the characters
should be surrounded by square brackets. For example, groupChars("in")
should return "[in]" and groupChars("a") should return "[a]". For strings
with more than 2 characters, parentheses should be inserted that surround
and separate individual characters with the center-most characters
surrounded by square brackets. The table below includes more examples.
Method Call Value Returned
-------------------------- --------------------------
groupChars("the") "(t[h]e)"
groupChars("rain") "(r[ai]n)"
groupChars("in") "[in]"
groupChars("Spain") "(S(p[a]i)n)"
groupChars("falls") "(f(a[l]l)s)"
groupChars("mainly") "(m(a[in]l)y)"
groupChars("recursively!") "(r(e(c(u(r[si]v)e)l)y)!)"
groupChars("") "*"
Notice that the method might be passed an empty string, in which case it
returns a string composed of a single asterisk. You are not allowed to
construct any structured objects to solve this problem 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. You may use only the string methods included on the cheat sheet.
3. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Block extends Truck {
public void method1() {
System.out.println("Block 1");
}
public void method3() {
System.out.println("Block 3");
}
}
public class Doll extends Ball {
public void method1() {
System.out.println("Doll 1");
}
public void method2() {
System.out.println("Doll 2");
}
}
public class Truck extends Ball {
public void method2() {
System.out.println("Truck 2");
super.method2();
method3();
}
public void method3() {
System.out.println("Truck 3");
}
}
public class Ball {
public void method2() {
System.out.println("Ball 2");
}
public void method3() {
System.out.println("Ball 3");
}
}
And assuming the following variables have been defined:
Ball var1 = new Truck();
Doll var2 = new Doll();
Ball var3 = new Block();
Object var4 = new Ball();
Truck var5 = new Block();
Ball var6 = new Doll();
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(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
var5.method3(); ____________________________
((Doll)var3).method1(); ____________________________
((Block)var5).method1(); ____________________________
((Truck)var3).method1(); ____________________________
((Truck)var3).method3(); ____________________________
((Block)var6).method3(); ____________________________
((Ball)var4).method2(); ____________________________
((Truck)var4).method3(); ____________________________
((Doll)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] | p->[1] |
| |
| |
q->[3] | q->[3]->[2] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p | p->[1] |
| |
| |
q->[1]->[2]->[3] | q->[2]->[3] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2]->[3] | p->[3]->[1] |
| |
| |
q->[4] | q->[2]->[4] |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1] | p->[5]->[1]->[3] |
| |
| |
q->[2]->[3]->[4]->[5] | q->[4]->[2] |
| |
| |
| |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
5. ArrayIntList, 10 points. Write a method called fromCounts that constructs
and returns a new ArrayIntList of values given an existing ArrayIntList of
counts. 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 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, storing the value returned in a variable called list2:
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
zero-argument constructor for ArrayIntList will construct an array of
sufficient capacity to store the result. 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 other than the new
ArrayIntList you are constructing (no array, String, ArrayList, etc), and
you may not change the original list.
6. Stacks/Queues, 25 points. Write a method called mirrorCollapse that
takes a stack of integers as a parameter and that collapses the stack by
combining pairs of values whose positions are a mirror image of each other.
For example, suppose a variable s stores these values:
bottom [1, 2, 3, 40, 50, 60] top
^ ^ ^ ^ ^ ^
| | +--+ | |
| +---------+ |
+----------------+
mirror positions
The pairs of values in mirror image positions are the first and last (1 and
60), the second and fifth (2 and 50), and the third and fourth (3 and 40).
The method should add the first value to its mirror image, add the second
value to its mirror image, add the third value to its mirror image, and so
on. Thus, if we make the following call:
mirrorCollapse(s);
the stack should store the following values after the call:
bottom [43, 52, 61] top
If there is a value in the middle that has no mirror image, then it should
not be altered. For example, if the stack had instead stored these values:
bottom [1, 2, 3, 4, 50, 60, 70] top
then it should store the following values after the method is called:
bottom [4, 53, 62, 71] top
Notice that the value 4 that was in the middle is unchanged. This example
uses values with a regular pattern to make it easier to understand what is
going on, but you should not assume anything about the sequence. For
example, if s instead stored this sequence:
bottom [7, 1, 4, 18, 9, 23, 0, -5, 12] top
then after the method is called, it would store this sequence:
bottom [9, 41, 4, -4, 19] top
Your method should not change the stack if it has fewer than two values.
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 stack. 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).
Space is provided on the next page for your answer.
Please write your answer to mirrorCollapse below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011