<![CDATA[
CSE143 Midterm
Spring 2007
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
This is an open-book/open-note exam. Space is provided for your answers. Use
the backs of pages if necessary. The exam is divided into seven questions with
the following points:
# Problem Area Points Score
---------------------------------------------
1 Iterators 10 _____
2 ArrayLists 10 _____
3 Recursive Programming 10 _____
4 Linked Lists 15 _____
5 Details of Inheritance 20 _____
6 Stacks/Queues 25 _____
7 Array Programming 10 _____
----------------------------
Total 100 _____
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.
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. Iterators, 10 points. Recall that the ArrayIntList class includes a method
for generating an iterator:
// post: returns an iterator for this list
public ArrayIntListIterator iterator()
And recall that the ArrayIntListIterator class includes three methods:
// post: returns true if there are more elements left, false otherwise
public boolean hasNext()
// pre : hasNext()
// post: returns the next element in the iteration
public int next()
// pre : next() has been called without a call on remove (i.e., at most
// one call per call on next)
// post: removes the last element returned by the iterator
public void remove()
Write a method printSum that takes an ArrayIntList as a parameter and that
prints the values from the list in order with plus signs separating
successive values. For example, if a variable called list stores the
following values:
[9, 3, 14, 7, 23, 408, 42, 19]
then the following call:
printSum(list);
should produce the following output:
9 + 3 + 14 + 7 + 23 + 408 + 42 + 19
Your method should produce a complete line of output so that if it is called
n times it will produce n lines of output. It should produce a blank line
of output if the list is empty.
You are not allowed to call any other methods of the ArrayIntList class to
solve this problem. You must solve it using iterators.
Write your solution to printSum below.
2. ArrayLists, 10 points. Write a method stretch that doubles the size of an
ArrayList of integers by replacing every integer in the list with a pair of
integers, each half the original. If a number in the original list is odd,
then the first number in the replacement pair should be one higher than the
second so that the sum equals the original number. For example, if a
variable called list stores this sequence of values:
[18, 7, 4, 24, 11]
and you make the following call:
stretch(list);
Then the number 18 is stretched into the pair (9, 9), the number 7 is
stretched into (4, 3), the number 4 is stretched into (2, 2), the number 24
is stretched into (12, 12) and the number 11 is stretched into (6, 5)
yielding the following overall list which is twice the length of the
original list:
[9, 9, 4, 3, 2, 2, 12, 12, 6, 5]
Recall that the primary methods for manipulating an ArrayList<E> are:
add(E value) appends value at end of list
add(int index, E value) inserts given value at given index, shifting
subsequent values right
clear() removes all elements of the list
get(int index) returns the value at given index
remove(int index) removes and returns value at given index,
shifting subsequent values left
set(int index, E value) replaces value at given index with given value
size() returns the number of elements in list
Write your solution to stretch below.
3. Recursive Tracing, 10 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(7); ______________
mystery(38); ______________
mystery(194); ______________
mystery(782); ______________
mystery(3842); ______________
4. Linked Lists, 15 points. Write a method rotate that moves the value at the
front of a list of integers to the end of the list. For example, if a
variable called list stores the following sequence of values:
[8, 23, 19, 7, 45, 98, 102, 4]
then the call:
list.rotate();
should move the value 8 from the front of the list to the back of the list,
yielding this sequence of values:
[23, 19, 7, 45, 98, 102, 4, 8]
The other values in the list should retain the same order as in the original
list. If the method is called for a list of 0 or 1 elements, it should have
no effect on the list.
Assume that we are using a linked list that stores integers, as discussed in
lecture (handout 9).
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>
}
You are writing a method that will become part of the LinkedIntList class.
You may not call any other methods of the class to solve this problem. You
are not allowed to construct any new nodes to solve this problem and you
are not allowed to change any of the integer values stored in nodes. You
must solve the problem by rearranging the links of the list.
Write your solution to rotate below.
5. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Eye extends Mouth {
public void method1() {
System.out.println("Eye 1");
super.method1();
}
}
public class Mouth {
public void method1() {
System.out.println("Mouth 1");
}
public void method2() {
System.out.println("Mouth 2");
method1();
}
}
public class Nose extends Eye {
public void method1() {
System.out.println("Nose 1");
}
public void method3() {
System.out.println("Nose 3");
}
}
public class Ear extends Eye {
public void method2() {
System.out.println("Ear 2");
}
public void method3() {
System.out.println("Ear 3");
}
}
And assuming the following variables have been defined:
Mouth var1 = new Nose();
Ear var2 = new Ear();
Mouth var3 = new Eye();
Object var4 = new Mouth();
Eye var5 = new Nose();
Mouth var6 = new Ear();
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 (you may abbreviate these as "ce" and "re" or "c.e." and "r.e.").
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(); ____________________________
((Nose)var5).method3(); ____________________________
((Eye)var1).method1(); ____________________________
((Eye)var4).method1(); ____________________________
((Nose)var1).method3(); ____________________________
((Mouth)var4).method1(); ____________________________
((Ear)var5).method3(); ____________________________
((Eye)var6).method3(); ____________________________
((Mouth)var4).method2(); ____________________________
6. Stacks/Queues, 25 points. Write a method reorder that takes a queue of
integers as a parameter and that puts the integers into sorted
(nondecreasing) order assuming that the queue is already sorted by absolute
value. For example, suppose that a variable called q stores the following
sequence of values:
front [1, 2, -2, 4, -5, 8, -8, 12, -15, 23] back
Notice that the values appear in sorted order if you ignore the sign of the
numbers. The following call:
reorder(q);
should reorder the values so that the queue stores this sequence of values:
front [-15, -8, -5, -2, 1, 2, 4, 8, 12, 23] back
Notice that the values now appear in sorted order taking into account the
sign of the numbers.
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.
In writing your method, assume that you are using the Stack and Queue
interfaces and the ArrayStack and LinkedQueue implementations discussed in
lecture.
Write your solution to reorder below.
7. Array Programming, 10 points. Write a method mirror that doubles the size
of a list of integers by appending the mirror image of the original
sequence to the end of the list. The mirror image is the same sequence of
values in reverse order. For example, if a variable called list stores
this sequence of values:
[1, 3, 2, 7]
and we make the following call:
list.mirror();
then it should store the following values after the call:
[1, 3, 2, 7, 7, 2, 3, 1]
Notice that it has been doubled in size by having the original sequence
appearing in reverse order at the end of the list. You may not make
assumptions about how many elements are in the list.
You are writing a method for the ArrayIntList class discussed in lecture
(handout 3):
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.
You may assume that the array has sufficient capacity to store the new
sequence of values.
Write your solution to mirror below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011