<![CDATA[
CSE143 Midterm
Fall 2011
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 x) {
if (x < 10)
System.out.print(x);
else {
int y = x % 10;
System.out.print(y);
mystery(x / 10);
System.out.print(y);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(3); ___________________________________________
mystery(42); ____________________________________________
mystery(293); ____________________________________________
mystery(402); ____________________________________________
mystery(2468); ____________________________________________
2. Recursive Programming, 15 points. Write a recursive method called
writeNumbers that takes an integer n as a parameter and that writes the
first n numbers separated by commas with the odd numbers in descending order
followed by the even numbers in ascending order. For example, the call:
writeNumbers(5);
should produce the following output:
5, 3, 1, 2, 4
The odd numbers (5, 3, and 1) appear first in descending order followed by
the even numbers (2 and 4) in ascending order. Notice that commas are used
to separate consecutive values in the list. Your method should send its
output to System.out and should not call println. For example, the
following calls:
writeNumbers(5);
System.out.println(); // to complete the line of output
writeNumbers(1);
System.out.println(); // to complete the line of output
writeNumbers(8);
System.out.println(); // to complete the line of output
should produce exactly three lines of output:
5, 3, 1, 2, 4
1
7, 5, 3, 1, 2, 4, 6, 8
You must exactly reproduce the format of these examples. Your method should
throw an IllegalArgumentException if passed a value less than 1. 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 increasingTriples that
returns whether or not a list of integers is composed of a series of
increasing triples. An increasing triple is a sequence of three integers
that increase in value. Below are examples of increasing triples:
1, 2, 3 0, 42, 309 -8, 47, 2094
Below are examples of triples that are not increasing:
1, 2, 2 3, 18, 12 45, 30, 10
Your method should examine the first three values to see if they are an
increasing triple, then the next three values, then the next three, and so
on. If there is an extra value at the end, you can ignore it. If there is
an extra pair at the end, your method should check that the pair is
increasing. For example, if a variable list stored any of the following:
[1, 2, 3, 0, 42, 309, -8, 47, 2094]
[1, 2, 3, 0, 42, 309, -8, 47, 2094, 14]
[1, 2, 3, 0, 42, 309, -8, 47, 2094, 14, 20]
then the call list.increasingTriples() would return true. Your method
should return true for a list with fewer than two elements.
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 Scoop extends Spoon {
public void method1() {
System.out.println("Scoop 1");
}
public void method3() {
System.out.println("Scoop 3");
}
}
public class Cone {
public void method1() {
System.out.println("Cone 1");
}
public void method2() {
System.out.println("Cone 2");
method1();
}
}
public class Spoon extends Cone {
public void method1() {
System.out.println("Spoon 1");
super.method1();
}
}
public class Cup extends Cone {
public void method3() {
System.out.println("Cup 3");
}
}
And assuming the following variables have been defined:
Cone var1 = new Scoop();
Cone var2 = new Spoon();
Cone var3 = new Cone();
Object var4 = new Spoon();
Spoon var5 = new Scoop();
Object var6 = new Cup();
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(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
((Spoon)var1).method3(); ____________________________
((Cup)var6).method3(); ____________________________
((Scoop)var4).method1(); ____________________________
((Cone)var6).method2(); ____________________________
((Cone)var4).method1(); ____________________________
((Scoop)var6).method3(); ____________________________
((Scoop)var3).method3(); ____________________________
((Scoop)var5).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method called isConsecutive that takes a
stack of integers as a parameter and that returns whether or not the stack
contains a sequence of consecutive integers starting from the bottom of the
stack (returning true if it does, returning false if it does not).
Consecutive integers are integers that come one after the other, as in 5, 6,
7, 8, 9, etc. So if a stack s stores the following values:
bottom [3, 4, 5, 6, 7, 8, 9, 10] top
then the call:
isConsecutive(s)
should return true. If the stack had instead contained this sequence:
bottom [3, 4, 5, 6, 7, 8, 9, 10, 12] top
then the call should return false because the numbers 10 and 12 are not
consecutive. Notice that we look at the numbers starting at the bottom of
the stack. The following sequence of values would be consecutive except for
the fact that it appears in reverse order, so the method would return false:
bottom [3, 2, 1] top
Your method must restore the stack so that it stores the same sequence of
values after the call as it did before. Any stack with fewer than two
values should be considered to be a list of consecutive integers.
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 insertAt that takes an
index, an integer n, and a value as parameters, and that inserts n copies of
the given value at the given index in a list of integers. For example, if a
variable called list stores this sequence:
[12, 42, 8, 934]
and the following call is made:
list.insertAt(2, 4, 98);
then it should store the following values after the call:
[12, 42, 98, 98, 98, 98, 8, 934]
Notice that there are now four occurrences of the value 98 starting at index
2 and that later values are in the same order as in the original.
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>
}
Your method should throw an IllegalArgumentException if the index is less
than 0 or greater than the number of elements in the list or if the value of
n is less than 0. 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. You may assume that the array has
sufficient capacity to store the new values.
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.
-------------------------------------------------------------------------------
Below is an example of a method that could be added to the LinkedIntList class
to compute the sum of the list:
public int sum() {
int sum = 0;
ListNode current = front;
while (current != null) {
sum += current.data;
current = current.next;
}
return sum;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011