<![CDATA[
CSE143 Midterm
Fall 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 Details of Inheritance 20 _____
5 Stacks/Queues 25 _____
6 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. Recursive Tracing, 15 points. Consider the following method:
public int mystery(int n) {
if (n < 0)
return -mystery(-n);
else if (n < 10)
return (n + 1) % 10;
else
return 10 * mystery(n / 10) + (n + 1) % 10;
}
For each call below, indicate what value is returned:
Method Call Value Returned
mystery(7) _____________________________________
mystery(42) ______________________________________
mystery(385) ______________________________________
mystery(-790) ______________________________________
mystery(89294) ______________________________________
2. Recursive Programming, 15 points. Write a recursive method digitMatch that
takes two nonnegative integers as parameters and that returns the number of
digits that match between them. Two digits match if they are equal and have
the same relative position starting from the end of the number (i.e.,
starting with the ones digit). In other words, the method should compare
the last digits of each number, the second-to-last digits of each number,
the third-to-last digits of each number, and so forth, counting how many
pairs match. For example, for the call digitMatch(1072503891, 62530841),
the method would compare as follows:
1 0 7 2 5 0 3 8 9 1
| | | | | | | |
6 2 5 3 0 8 4 1
The method should return 4 in this case because 4 of these pairs match (2-2,
5-5, 8-8, and 1-1). Below are more examples:
Method Call Value Returned
------------------------------------------------
digitMatch(38, 34) 1
digitMatch(5, 5552) 0
digitMatch(892, 892) 3
digitMatch(298892, 7892) 3
digitMatch(380, 0) 1
digitMatch(123456, 654321) 0
digitMatch(1234567, 67) 2
Your method should throw an IllegalArgumentException if either of the two
parameters is negative. You are not allowed to construct any structured
objects to solve this problem (no array, String, 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 isSortedByN that takes an integer n
as a parameter and that returns true if a list of integers is sorted in
nondecreasing order when examined "by n" and that returns false otherwise.
When examining a list by n, you pick any element of the list and consider
the sublist formed by that element followed by the element that comes n
later, followed by the element that comes 2n later, followed by the element
that comes 3n later, and so on. For example, suppose that a variable list
stores the following sequence of numbers:
[1, 3, 2, 5, 8, 7, 12, 7, 20]
This list would normally not be considered to be sorted, which means that
list.isSortedByN(1) should return false. But when examining elements by 2,
we get two sorted sublists:
[1, 2, 8, 12, 20] and [3, 5, 7, 7]
Thus, list.isSortedByN(2) should return true. Notice that duplicates are
allowed in the sublists. The call list.isSortedByN(3) returns false because
one of the resulting sublists is not sorted:
[1, 5, 12] (sorted), [3, 8, 7] (NOT sorted), and [2, 7, 20] (sorted)
By definition, an empty list and a list of one element are considered to be
sorted. The method should return true whenever n is greater than or equal
to the length of the list because in that case all of the resulting sublists
would be of length 1. Your method should throw an IllegalArgumentException
if passed an n that is less than or equal to 0.
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>
}
You may not call any other methods of the LinkedIntList class to solve this
problem.
4. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Couch extends Table {
public void method1() {
System.out.println("Couch 1");
}
}
public class Table extends Chair {
public void method1() {
System.out.println("Table 1");
}
public void method2() {
System.out.println("Table 2");
super.method2();
}
public void method3() {
System.out.println("Table 3");
method1();
}
}
public class Chair {
public void method2() {
System.out.println("Chair 2");
}
}
public class Lamp extends Chair {
public void method1() {
System.out.println("Lamp 1");
}
public void method2() {
System.out.println("Lamp 2");
}
}
And assuming the following variables have been defined:
Table var1 = new Table();
Chair var2 = new Table();
Table var3 = new Couch();
Chair var4 = new Lamp();
Chair var5 = new Couch();
Object var6 = new Chair();
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(); ____________________________
var4.method1(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
((Lamp)var4).method1(); ____________________________
((Lamp)var2).method1(); ____________________________
((Table)var5).method1(); ____________________________
((Couch)var1).method1(); ____________________________
((Chair)var6).method2(); ____________________________
((Couch)var5).method3(); ____________________________
((Table)var5).method3(); ____________________________
5. Stacks/Queues, 25 points. Write a method compressDuplicates that takes a
stack of integers as a parameter and that replaces each sequence of
duplicates with a pair of values representing a count of the number of
duplicates followed by the number. For example, suppose a variable called s
stores the following sequence of values:
bottom [2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17] top
and we make the following call:
compressDuplicates(s);
Then s should store the following values after the call:
bottom [5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17] top
This new stack indicates that the original had 5 occurrences of 2 at the
bottom of the stack followed by 2 occurrences of -5 followed by 4
occurrences of 3, and so on. This process works best when there are many
duplicates in a row. For example, if the stack instead had stored:
bottom [10, 20, 10, 20, 10, 20] top
Then the resulting stack ends up being longer than the original:
bottom [1, 10, 1, 20, 1, 10, 1, 20, 1, 10, 1, 20] top
If the stack is empty, your method should not change it. 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 may not use recursion to solve this
problem and 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, 10 points. Write a method isConsecutive that returns
true if a list of integers contains a sequence of consecutive integers and
that returns false otherwise. Consecutive integers are integers that come
one after the other, as in 5, 6, 7, 8, 9, etc. For example, if a variable
called list stores these values:
[3, 4, 5, 6, 7, 8, 9, 10]
then the call:
list.isConsecutive()
should return true. If the list had instead contained this sequence:
[3, 4, 5, 6, 7, 8, 9, 10, 12]
then the call should return false because the numbers 10 and 12 are not
consecutive. The following sequence of values would be consecutive except
for the fact that it appears in reverse order, so the method would return
false in this case:
[3, 2, 1]
Any list with fewer than two values should be considered to be consecutive.
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>
}
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, String, ArrayList, etc), and your solution must run in O(n) time.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011