CSE143 Sample Midterm
Summer 2008
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 six questions with
the following points:
# Problem Area Points Score
---------------------------------------------
1 Recursive Tracing 15 _____
2 Recursive Programming 15 _____
3 Linked Lists 15 _____
4 More Linked Lists 15 _____
5 Stacks/Queues 25 _____
6 Array Programming 15 _____
----------------------------
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 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, int y) {
if (x > y)
System.out.print("*");
else if (x == y)
System.out.print("=" + y + "=");
else {
System.out.print(y + " ");
mystery(x + 1, y - 1);
System.out.print(" " + x);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(3, 3); _____________________________________
mystery(5, 1); ______________________________________
mystery(1, 5); ______________________________________
mystery(2, 7); ______________________________________
mystery(1, 8); ______________________________________
2. Recursive Programming, 15 points. Write a method repeat that takes a String
s and an integer n as parameters and that returns a String composed of n
copies of s. For example:
repeat("hello", 3) returns "hellohellohello"
repeat("this is fun", 1) returns "this is fun"
repeat("wow", 0) returns ""
repeat("hi ho!", 5) returns "hi ho!hi ho!hi ho!hi ho!hi ho!"
Your method should throw an IllegalArgumentException if passed a negative
value for n.
You should solve this problem by concatenating Strings using the "+"
operator. String concatenation is an expensive operation, so it is best to
minimize the number of concatenation operations you perform. For example,
for the call repeat("foo", 500), it would be inefficient to perform 500
different concatenation operations to obtain the result. Most of the credit
(9 points) will be awarded on the correctness of your solution independent
of efficiency. The remaining credit (6 points) will be awarded based on
your ability to minimize the number of concatenation operations performed.
You are not allowed to construct any structured objects other than Strings
(no array, 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. Write a method transferFrom for
LinkedIntList that takes a second LinkedIntList list as a parameter
and that moves values from the second list to this list. First you
are to join them together, attaching the second list to the end of
this list. Then you are to empty the second list. For example, if
two lists store these sequences of values:
list1: (8, 17, 2, 4)
list2: (1, 2, 3)
Then the following call:
list1.transferFrom(list2);
should leave the lists as follows:
list1: (8, 17, 2, 4, 1, 2, 3)
list2: ()
The order of the arguments in the call matters. For example:
list2.transferFrom(list1);
would have left the lists as follows:
list1: ()
list2: (1, 2, 3, 8, 17, 2, 4)
Either of the two lists could be empty, but you can assume that neither
list is null. You are not to create any new nodes. Your method should
simply change links of the lists to join them together.
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
}
public class LinkedIntList {
private ListNode front;
}
You may not call any other methods of the LinkedIntList class to solve this
problem and your solution must run in O(n) time.
4. More Linked Lists, 15 points. Write a method removeLast that
removes the last occurrence of an integer (if any) from a list of
integers. For example, suppose that a variable called "list"
stores this sequence of values:
[3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0, 3]
If we repeatedly make the following call:
list.removeLast(3);
Then the list will take on the following sequence of values:
[3, 2, 3, 3, 19, 8, 3, 43, 64, 1, 0]
[3, 2, 3, 3, 19, 8, 43, 64, 1, 0]
[3, 2, 3, 19, 8, 43, 64, 1, 0]
[3, 2, 19, 8, 43, 64, 1, 0]
[2, 19, 8, 43, 64, 1, 0]
[2, 19, 8, 43, 64, 1, 0]
Notice that once we reach a point where no more 3's occur in the list, then
calling the method has no effect.
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
}
public class LinkedIntList {
private ListNode front;
}
You may not call any other methods of the LinkedIntList class to solve this
problem and your solution must run in O(n) time.
5. Stacks/Queues, 25 points. Write a method interleave that takes a queue of
integers as a parameter and that rearranges the elements by interleaving
the first half of the list with the second half of the list. For example,
suppose a variable called q stores the following sequence of values:
front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] back
and we make the following call:
interleave(q);
Consider the two halves of this list:
first half: [1, 2, 3, 4, 5] second half: [6, 7, 8, 9, 10]
These are combined in an alternating fashion to form a sequence of
interleave pairs: the first values from each half (1 and 6), then the second
values from each half (2 and 7), then the third values from each half (3 and
8), and so on. In each pair, the value from the first half appears before
the value from the second half. Thus, after the call, the queue stores the
following values:
front [1, 6, 2, 7, 3, 8, 4, 9, 5, 10] back
This example uses sequential integers to make the interleaving more obvious,
but the same process can be applied to any sequence of even length. For
example, if q had instead stored these values:
front [2, 8, -5, 19, 7, 3, 24, 42] back
then the method would have rearranged the list to become:
front [2, 7, 8, 3, -5, 24, 19, 42] back
Your method should throw an IllegalArgumentException if the queue does not
have even length. 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.
Your solution must run in O(n) time. Use the Stack and Queue interfaces and
the ArrayStack and LinkedQueue implementations discussed in lecture.
6. Array Programming, 15 points. Write a method removeOddPositions that removes
the values in odd-numbered positions (if any) from a list of integers. For
example if a variable called list stores these values:
[8, 13, 17, 4, 9, 12, 98]
and the following call is made:
list.removeOddPositions();
The list should store this sequence after the call:
[8, 17, 9, 98]
The method removed the values at odd positions (positions 1, 3, and 5),
otherwise preserving the order of the remaining elements. Notice that it
doesn't matter whether the value itself is odd or even but instead whether
it appears in an odd position or even position.
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
}
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, ArrayList, etc), and your solution must run in O(n) time.