CSE143 Sample Midterm handout #18
Spring 2008
1. Recursive Tracing, 15 points. Consider the following method:
public void mystery(int n) {
if (n % 2 == 1)
System.out.print(n);
else {
System.out.print(n + ", ");
mystery(n / 2);
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(13); _____________________________________
mystery(42); ______________________________________
mystery(40); ______________________________________
mystery(60); ______________________________________
mystery(48); ______________________________________
2. Recursive Programming, 15 points. Write a method indexOf that takes two
Strings as parameters and that returns the starting index of the first
occurrence of the second String inside the first String (-1 if not found).
For example:
indexOf("Barack Obama", "Bar") returns 0
indexOf("Barack Obama", "ck") returns 4
indexOf("Barack Obama", "a") returns 1
indexOf("Barack Obama", "BAR") returns -1
Notice that case matters, as in the last example that returns -1 because the
second String does not occur inside the first String.
The String class includes an indexOf method and you are not allowed to
simply call it to solve this problem. You are limited to the following
String methods:
equals(other) Returns whether this String is equal to
the other object
length() Returns the length of the String
substring(fromIndex, toIndex) Returns a new string that is a substring
of this string from startIndex
(inclusive) to stopIndex (exclusive)
substring(fromIndex) Returns a new string that is a substring
of this string from startIndex
(inclusive) to the end of the String
For example, if a String s stores the text "hello", then:
s.equals("hello") returns true
s.length() returns 5
s.substring(1, 3) returns "el"
s.substring(2) returns "llo"
You are not allowed to construct any structured objects other than Strings
(no array, StringBuilder, Scanner, 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 hasAlternatingParity that returns
whether or not a list of integers has alternating parity (true if it does,
false otherwise). The parity of an integer is 0 for even numbers and 1 for
odd numbers. To have alternating parity, a list would have to alternate
between even and odd numbers, as in the following list:
[3, 2, 19, 8, 43, 64, 1, 0, 3]
If a variable called list stores the values above, then the call:
list.hasAlternatingParity()
would return true. If instead the list stored the following values:
[2, 13, 4, 1, 0, 9, 2, 7, 4, 12, 3, 2]
then the call would return false because the list has two even numbers in a
row (4 and 12). By definition, an empty list or a list of one element has
alternating parity. You may assume that the values in the list are greater
than or equal to 0.
Assume that we are using a linked list that stores integers, as discussed in
lecture (handout 8).
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 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 and
your method cannot change the contents of the list.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Clip extends Paper {
public void method2() {
System.out.println("Clip 2");
super.method2();
}
}
public class Paper {
public void method2() {
System.out.println("Paper 2");
}
public void method3() {
System.out.println("Paper 3");
method2();
}
}
public class Stapler extends Clip {
public void method1() {
System.out.println("Stapler 1");
}
public void method2() {
System.out.println("Stapler 2");
}
}
public class Pen extends Paper {
public void method1() {
System.out.println("Pen 1");
}
public void method2() {
System.out.println("Pen 2");
}
}
And assuming the following variables have been defined:
Paper var1 = new Pen();
Stapler var2 = new Stapler();
Paper var3 = new Stapler();
Paper var4 = new Paper();
Object var5 = new Stapler();
Paper var6 = new Clip();
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.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
var1.method1(); ____________________________
var2.method1(); ____________________________
var3.method1(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
((Pen)var1).method1(); ____________________________
((Stapler)var3).method1(); ____________________________
((Clip)var3).method3(); ____________________________
((Clip)var5).method1(); ____________________________
((Pen)var5).method1(); ____________________________
((Clip)var6).method2(); ____________________________
((Stapler)var6).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method removeMin that takes a stack of
integers as a parameter and that removes and returns the smallest value from
the Stack. For example, if a variable called s stores the following
sequence of values:
bottom [2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, -8, 4] top
and we make the following call:
int n = removeMin(s);
the method removes and returns the value -8 from the stack, so that the
variable n will be -8 after the call and s will store the following values:
bottom [2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, 4] top
If the minimum value appears more than once, all occurrences of the minimum
should be removed from the stack. For example, given the ending value of
the stack above, if we again call removeMin(s), the method would return 2
and would leave the stack in the following state:
bottom [8, 3, 19, 7, 3, 42, 9, 3, 7, 12, 4] top
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.
Your method should throw an IllegalArgumentException if the stack is empty.
In writing your method, assume that you are using the Stack and Queue
interfaces and the ArrayStack and LinkedQueue implementations discussed in
lecture.
6. Array Programming, 10 points. Write a method collapse that collapses a list
of integers by replacing each successive pair of integers with the sum of
the pair. For example, if a variable called list stores this sequence of
values:
[7, 2, 8, 9, 4, 13, 7, 1, 9, 10]
and the following call is made:
list.collapse();
The first pair should be collapsed into 9 (7 + 2), the second pair should be
collapsed into 17 (8 + 9), the third pair should be collapsed into 17 (4 +
13) and so on to yield:
[9, 17, 17, 8, 19]
If the list stores an odd number of elements, the final element is not
collapsed. For example, the sequence:
[1, 2, 3, 4, 5]
would collapse into:
[3, 7, 5]
with the 5 at the end of the list unchanged.
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
}
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.