<![CDATA[
CSE143 Midterm
Fall 2012
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. 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.
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 {
mystery(n / 2);
System.out.print(", " + n);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(1); ___________________________________________
mystery(4); ____________________________________________
mystery(16); ____________________________________________
mystery(30); ____________________________________________
mystery(100); ____________________________________________
2. Recursive Programming, 15 points. Write a recursive method called
digitMatch that takes two nonnegative integers as parameters and that
returns the number of digits that match between them. Two digits match if
they are equal and have the same relative position starting from the end of
the number (i.e., starting with the ones digit). In other words, the method
should compare the last digits of each number, the second-to-last digits of
each number, the third-to-last digits of each number, and so forth, counting
how many pairs match. For example, digitMatch(1072503891, 62530841) would
compare as follows:
1 0 7 2 5 0 3 8 9 1
| | | | | | | |
6 2 5 3 0 8 4 1
The method should return 4 in this case because 4 of these pairs match (2-2,
5-5, 8-8, and 1-1). Below are more examples:
Method call Result Method call Result
-------------------------------- --------------------------------
digitMatch(38, 34) 1 digitMatch(5, 5552) 0
digitMatch(892, 892) 3 digitMatch(1234567, 67) 2
digitMatch(298892, 7892) 3 digitMatch(380, 0) 1
digitMatch(123456, 654321) 0 digitMatch(0, 4) 0
digitMatch(42, 24) 0 digitMatch(0, 0) 1
Your method should throw an IllegalArgumentException if either of the two
parameters is negative. You are not allowed to construct any structured
objects to solve this problem (no array, String, StringBuilder, ArrayList,
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. 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 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 | q->[2] |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2] | p->[2] |
| |
| |
q | q->[1] |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2]->[3] | p->[1]->[4]->[2]->[5] |
| |
| |
q->[4]->[5] | q->[3] |
| |
| |
| |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
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 called compressDuplicates that
takes a stack of integers as a parameter and that replaces each sequence of
duplicates with a pair of values representing a count of the number of
duplicates followed by the number. For example, suppose a variable called s
stores the following sequence of values:
bottom [2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17] top
and we make the following call:
compressDuplicates(s);
Then s should store the following values after the call:
bottom [5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17] top
This new stack indicates that the original had 5 occurrences of 2 at the
bottom of the stack followed by 2 occurrences of -5 followed by 4
occurrences of 3, and so on. This process works best when there are many
duplicates in a row. For example, if the stack instead had stored:
bottom [10, 20, 10, 20, 10, 20] top
Then the resulting stack ends up being longer than the original:
bottom [1, 10, 1, 20, 1, 10, 1, 20, 1, 10, 1, 20] top
If the stack is empty, your method should not change it. 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.
6. Array Programming, 10 points. Write a method called isConsecutive that
returns true if a list of integers contains a sequence of consecutive
integers and that returns false otherwise. Consecutive integers are
integers that come one after the other, as in 5, 6, 7, 8, 9, etc. For
example, if a variable called list stores these values:
[3, 4, 5, 6, 7, 8, 9, 10]
then the call:
list.isConsecutive()
should return true. If the list had instead contained this sequence:
[3, 4, 5, 6, 7, 8, 9, 10, 12]
then the call should return false because the numbers 10 and 12 are not
consecutive. The following sequence of values would be consecutive except
for the fact that it appears in reverse order, so the method would return
false in this case:
[3, 2, 1]
Any list with fewer than two values should be considered to be consecutive.
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 methods 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.
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