<![CDATA[
CSE143 Midterm
Winter 2017
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 void mystery(int x) {
if (x == 0) {
System.out.print("=");
} else {
int y = x % 10;
if (y < 5) {
System.out.print(y);
mystery(x / 10);
} else {
mystery(x / 10);
System.out.print(y);
}
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(9); _____________________________________
mystery(42); ______________________________________
mystery(703); ______________________________________
mystery(5821); ______________________________________
mystery(83105); ______________________________________
2. Recursive Programming, 15 points. Write a recursive method called weave
that takes two integers as parameters and that returns the result of weaving
their digits together to form a single integer. Two numbers x and y that
have the same number of digits are weaved together as follows. The first
digit of x and the first digit of y become the first two digits of the
result in that order. The next pair of digits in the result comes from the
second digit of x followed by the second digit of y. And so on.
For example, consider weaving 128 with 394. The first two digits of the
result are 13 because those are the first digits of the two numbers. The
next two digits in the result are 29 and the third pair of digits is 84. So
the overall result is 132984. Thus, the call weave(128, 394) should return
132984. Notice that the order of the arguments is important. The call
weave(394, 128) would return 319248.
If one of the numbers has more digits than the other, you should imagine
that leading zeros are used to make the numbers have equal length. For
example, weave(2384, 12) should return 20308142 (as if it were a call on
weave(2384, 0012)). Similarly, weave(9, 318) should return 30198 (as if it
were a call on weave(009, 318)). The table below includes several examples.
Method Call Result Method Call Result
---------------------------- ----------------------------
weave(8, 5) 85 weave(7, 0) 70
weave(5, 8) 58 weave(0, 7) 7
weave(42, 95) 4925 weave(4723, 9815) 49782135
weave(42, 7596) 7054926 weave(0, 0) 0
weave(7596, 42) 70509462 weave(444, 318) 434148
The method should throw an IllegalArgumentException if either parameter is
negative. You are not allowed to construct any structured objects to solve
this problem (no string, 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 Bell extends Candle {
public void method1() {
System.out.println("Bell 1");
super.method1();
}
}
public class Candle {
public void method1() {
System.out.println("Candle 1");
}
public void method2() {
System.out.println("Candle 2");
method1();
}
}
public class Cat extends Bell {
public void method1() {
System.out.println("Cat 1");
}
public void method3() {
System.out.println("Cat 3");
}
}
public class Book extends Bell {
public void method2() {
System.out.println("Book 2");
}
public void method3() {
System.out.println("Book 3");
}
}
And assuming the following variables have been defined:
Candle var1 = new Cat();
Book var2 = new Book();
Candle var3 = new Bell();
Object var4 = new Candle();
Bell var5 = new Cat();
Candle var6 = new Book();
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(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
((Cat)var5).method3(); ____________________________
((Bell)var1).method3(); ____________________________
((Bell)var4).method1(); ____________________________
((Cat)var1).method3(); ____________________________
((Candle)var4).method1(); ____________________________
((Book)var5).method3(); ____________________________
((Bell)var6).method3(); ____________________________
((Candle)var4).method2(); ____________________________
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] | p->[1]->[3] |
| |
| |
q->[2]->[3] | q->[2] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1] | p->[2]->[1] |
| |
| |
q->[2]->[3] | q->[3] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1] | p->[1]->[3] |
| |
| |
q->[2]->[3]->[4] | q->[4]->[2] |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2] | p->[2]->[4] |
| |
| |
q->[3]->[4]->[5] | q->[5]->[3]->[1] |
| |
| |
| |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
5. ArrayIntList, 10 points. Write a method called removeAll that takes an
integer n as a parameter and that removes all occurrences of n from a list
of integers. For example, if a variable called list stores this sequence of
values:
[12, 7, 8, 3, 9, 3, 2, 3, 3, 14]
and you make the following call:
list.removeAll(3);
then it should store the following values after the call:
[12, 7, 8, 9, 2, 14]
Notice that all occurrences of the value 3 have been removed from the list
and other values appear in their original order. If the list has no
occurrences of the target value, then it is unchanged.
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,
and you are not allowed to define any auxiliary data structures (no array,
ArrayList, string, etc).
6. Stacks/Queues, 25 points. Write a method called makeSortedSequence that
takes a queue of integers as a parameter and that rearranges the values so
that the queue begins with a sorted sequence. In particular, after the
method is done executing, the queue should begin with the first value from
the original sequence, followed by the next value from the original sequence
that is greater than or equal to the first value, followed by the next value
from the original sequence that is greater than or equal to that second
value, and so on. Values that are not included in the sorted sequence
should appear after the sorted sequence in the same relative order as in the
original sequence. For example, suppose a variable q stores these values:
front [3, 1, 2, 6, 5, 7, 9, 8, 12, 4, 3, 4, 12, 11, 14] back
and we make the following call:
makeSortedSequence(q);
A sorted sequence is formed starting with the first value in the queue (3)
and finding subsequent values that are greater than or equal to the previous
value, as indicated by the arrows below.
front [3, 1, 2, 6, 5, 7, 9, 8, 12, 4, 3, 4, 12, 11, 14] back
^ ^ ^ ^ ^ ^ ^
Moving these values to the front of the queue while otherwise preserving the
order of values produces the following result:
front [3, 6, 7, 9, 12, 12, 14, 1, 2, 5, 8, 4, 3, 4, 11] back
^ ^ ^ ^
| | | |
+--sorted sequence--+ +----other values----+
Notice that the sorted sequence appears at the beginning of the queue
followed by the other values from the sequence in their original order.
It is possible that the sorted sequence will not be very long. For example,
if the first value in the queue is larger than all the others, then the
resulting sorted sequence will have just that one value in it, which means
the queue ends up in the same order as the original sequence. The queue
might also be empty in which case the method should not change it.
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 also may
not solve the problem recursively. Your solution must run in O(n) time
where n is the size of the queue. 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 makeSortedSequence below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011