Key to CSE143 Sample Midterm, Summer 2008 handout #17
1. Method Call Output Produced
-----------------------------------------------
mystery(3, 3); =3=
mystery(5, 1); *
mystery(1, 5); 5 4 =3= 2 1
mystery(2, 7); 7 6 5 * 4 3 2
mystery(1, 8); 8 7 6 5 * 4 3 2 1
2. One possible solution appears below.
public String repeat(String s, int n) {
if (n < 0)
throw new IllegalArgumentException();
else if (n == 0)
return "";
else if (n == 1)
return s;
else if (n % 2 == 0) {
String temp = repeat(s, n / 2);
return temp + temp;
// alternative without temp: return repeat(s + s, n / 2);
} else
return s + repeat(s, n - 1);
}
3. One possible solution appears below.
public void transferFrom(LinkedIntList other) {
if (front == null)
front = other.front;
else {
ListNode current = front;
while (current.next != null)
current = current.next;
current.next = other.front;
}
other.front = null;
}
4. One possible solution appears below.
public void removeLast(int n) {
if (front != null) {
ListNode current = front;
ListNode spot = null;
while (current.next != null) {
if (current.next.data == n)
spot = current;
current = current.next;
}
if (spot != null)
spot.next = spot.next.next;
else if (front.data == n)
front = front.next;
}
}
5. One possible solution appears below.
public void interleave(Queue<Integer> q) {
if (q.size() % 2 != 0)
throw new IllegalArgumentException();
Stack<Integer> s = new ArrayStack<Integer>();
int halfSize = q.size() / 2;
for (int i = 0; i < halfSize; i++)
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
for (int i = 0; i < halfSize; i++)
q.enqueue(q.dequeue());
for (int i = 0; i < halfSize; i++)
s.push(q.dequeue());
while (!s.isEmpty()) {
q.enqueue(s.pop());
q.enqueue(q.dequeue());
}
}
6. One possible solution appears below.
public void removeOddPositions() {
size = (size + 1) / 2;
for (int i = 0; i < size; i++)
elementData[i] = elementData[2 * i];
}
Stuart Reges
Last modified: Wed May 14 17:14:19 PDT 2008