<![CDATA[
CSE142 Final
Spring 2006
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
Exam time (10:30, 12:30)_____________
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 ten questions with
the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Expressions 5 _____
2 Simulation 10 _____
3 Polymorphism 6 _____
4 Token-Based File processing 10 _____
5 Line-Based File Processing 9 _____
6 Arrays 10 _____
7 ArrayList 10 _____
8 Critters 15 _____
9 Arrays 15 _____
10 Programming 10 _____
----------------------------------
Total 100 _____
In general the exam is not graded on style and you do not need to include
comments. You do not have to include any import statements. Do not abbreviate
any code that you write (e.g., S.o.p versus System.out.print) and do not
abbreviate any answer asking for sample output (show the complete output).
You may use a calculator to do simple arithmetic, although you are not allowed
to program the calculator or to run a stored program.
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. Expressions, 5 points. For each expression in the left-hand column,
indicate its value in the right-hand column. Be sure to list a constant of
appropriate type (e.g., 7.0 rather than 7 for a double, Strings in quotes).
Expression Value
17/3 + 55 % 20/2 __________
19.0/2 + 2 * 2.25 __________
2 + 2 + "." + 2 + 2 + 4 * 5 __________
73/10 * 4/3/2.0 * 3 __________
15/2 * (1.5 + 2.5) + 98 % 5/2 __________
2. Simulation, 10 points. You are to simulate the execution of a method that
manipulates an array of integers. Consider the following method:
public static void mystery(int[] list) {
for (int i = 1; i < list.length; i++)
list[i] = list[i] + list[i - 1];
}
In the left-hand column below are specific lists of integers. You are to
indicate in the right-hand column what values would be stored in the list
after method mystery executes if the integer list in the left-hand column
is passed as a parameter to mystery.
Original List Final List
------------------------------------------------------------
(8) ____________________________
(6, 3) ____________________________
(2, 4, 6) ____________________________
(1, 2, 3, 4) ____________________________
(7, 3, 2, 0, 5) ____________________________
3. Polymorphism, 6 points. Assume the following classes have been defined:
public class D extends A {
public String toString() {
return "d";
}
public void method1() {
System.out.println("d 1");
}
}
public class B extends D {
public void method2() {
System.out.println("b 2");
}
}
public class A extends C {
public void method2() {
System.out.println("a 2");
}
}
public class C {
public String toString() {
return "c";
}
public void method1() {
System.out.println("c 1");
}
public void method2() {
System.out.println("c 2");
}
}
Consider the following code fragment:
C[] elements = {new B(), new C(), new A(), new D()};
for (int i = 0; i < elements.length; i++) {
System.out.println(elements[i]);
elements[i].method1();
elements[i].method2();
System.out.println();
}
What output is produced by this code?
4. Token-Based File Processing, 10 points. Write a static method called
processSets that takes a Scanner as a parameter and that prints information
about a series of data sets stored in the Scanner. The Scanner will contain
a sequence of data entries where an entry is either:
- a positive integer followed by a real number, which indicates that
the given real number occurs the given number of times in the data
set, as in "3 4.2" which would indicate 3 occurrences of 4.2
- a 0, which indicates the end of the data set
For example, suppose the Scanner contains the following data:
3 4.5 2 9.8 7 4.5 0 4 2.7 5 3.9 0 2 3.2 4 7.1 0
This input includes three data sets because it has three zeros. The first
data set has 3 occurrences of 4.5, 2 occurrences of 9.8 and 7 occurrences of
4.5 (terminated by a 0). The second data set has 4 occurrences of 2.7 and 5
occurrences of 3.9, again terminated by a 0. The third data set has 2
occurrences of 3.2 and 4 occurrences of 7.1 terminated by a 0.
Your method should report for each data set the total number of entries in
the data set and the average of the numbers. For the input above, the
following output should be produced:
total values = 12
average value = 5.383333333333333
total values = 9
average value = 3.3666666666666667
total values = 6
average value = 5.8
You must exactly reproduce this format. The value 0 that is used to
terminate each data set should not be included in the computations. Notice
that you have to account for the multiple occurrences of each number in
reporting the total number of values and the overall average for the data
set. For example, the first data set is specified by three pairs of
numbers, but because of the duplicates, it contains a total of 12 numbers
and the overall average of those 12 numbers is reported.
If the Scanner is initially empty, your method should produce no output.
Otherwise you may assume that no data set is empty and that each data set is
terminated by a 0 (including the last data set).
Write your solution to processSets below.
5. Line-Based File Processing, 9 points. Write a static method called
countOddLength that takes a Scanner containing an input file as a parameter
and that reports to System.out the total number of lines in the file, the
total number of odd-length lines and the percentage of odd-length lines.
For example, given the following input file:
This line has odd length because it is 57 characters long
This line is even because it is 40 long.
another even (68 characters) along with the blank line above with 0.
another odd line here
and one final even
Two of these input lines have odd length and there are six lines total, so
your method should print the following output:
Total lines = 6
odd length = 2
percent = 33.333333333333336
You are to exactly reproduce the format of this output. You may assume that
the Scanner contains at least one line.
Write your solution to countOddLength below.
6. Arrays, 10 points. Write a static method called numUnique that takes a
sorted array of integers as a parameter and that returns the number of
unique values in the array. The array is guaranteed to be in sorted order,
which means that duplicates will be grouped together. For example, if a
variable called "list" stores the following values:
(5, 7, 7, 7, 8, 22, 22, 23, 31, 35, 35, 40, 40, 40, 41)
then the following call:
numUnique(list)
should return 9 because this list has 9 unique values (5, 7, 8, 22, 23, 31,
35, 40 and 41). It is possible that the list might not have any
duplicates. For example if list instead stored this sequence of values:
(1, 2, 11, 17, 19, 20, 23, 24, 25, 26, 31, 34, 37, 40, 41)
then a call on the method would return 15 because this list contains 15
different values.
If passed an empty list, your method should return 0. Remember that you can
assume that the values in the array appear in sorted (nondecreasing) order.
Write your solution to numUnique below.
7. ArrayList, 10 points. Write a static method called collapse that takes an
ArrayList of Strings as a parameter and that collapses successive pairs into
a single String. Each pair should be collapsed into a new String that has
the two values inside parentheses and separated by a comma. For example, if
a variable called "list" initially stores these values:
["four", "score", "and", "seven", "years", "ago"]
and we make the following call:
collapse(list);
Your method should collapse the first pair into "(four, score)", the second
pair into "(and, seven)" and the third pair into "(years, ago)" so that list
stores the following values:
["(four, score)", "(and, seven)", "(years, ago)"]
Notice that the list goes from having 6 elements to having 3 elements
because each successive pair is collapsed into a single value. If there are
an odd number of values in the list, the final element is not collapsed.
For example, if the original list had been:
["to", "be", "or", "not", "to", "be", "hamlet"]
It would again collapse pairs of values, but the final value ("hamlet")
would not be collapsed, yielding this list:
["(to, be)", "(or, not)", "(to, be)", "hamlet"]
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 collapse below.
8. Critters, 15 points. Write a class called Orca that implements the Critter
interface. The instances of the Orca class go through cycles of staying in
the same place (like a Stone), then traveling West, then traveling East. In
the first cycle each Orca first stands still for one move, then moves West
for one move, then moves East for one move. In the second cycle the Orca
stands still for two moves, then moves West for two moves, then moves East
for two moves. In the third cycle the Orca stands still for three moves,
then moves West for three moves, then moves East for three moves. The
cycles continue in this pattern, each time increasing by one the number of
times each of the three choices is made. The Orca should display itself as
a plus ("+") if it most recently stood still, as a less-than ("<") if it
most recently moved West and as a greater-than (">") if it most recently
moved East. It should initially display itself as a plus ("+").
Remember that the Critter interface is defined as follows:
public interface Critter {
public char getChar();
public int getMove(CritterInfo info);
<definitions for constants NORTH, SOUTH, EAST, WEST and CENTER>
}
Write your solution to the Orca class below.
9. Arrays, 15 points. Write a static method called insert that takes as
parameters a short array of integers, a long array of integers and an index
and that inserts the values from the short array into the long array
starting at the given index, shifting existing values in the long array to
the right to make room for the new values.
For example, suppose that the following two arrays have been declared:
int[] bigList = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int[] shortList = {2, 4, 6, 8};
Then the following call:
insert(shortList, bigList, 2);
indicates that the values from the short list should be inserted into the
big list starting at index 2. After the call, bigList should store the
following sequence of values:
(1, 3, 2, 4, 6, 8, 5, 7, 9, 11)
Notice that the values in the short list (2, 4, 6, 8) now appear in the big
list starting at index 2. Also notice that the values that used to be in
those positions have been shifted right (5, 7, 9, 11). As a result of this
shifting, some values are no longer in the big list (13, 15, 17, 19).
You may assume that there is room in the longer array to insert the values
from the shorter array starting at the given index.
You are not allowed to use an auxiliary data structure such as a temporary
array or ArrayList to solve this problem.
Write your solution to insert below.
10. Programming, 10 points. Write a static method called printReversed that
takes a String as a parameter and that prints a line of output to
System.out with all words in the String reversed. For this problem, we
will define words as nonempty sequences of characters separated by one or
more spaces. For example, if we make the following calls:
printReversed("four score and seven years ago");
printReversed("our fathers brought forth on this continent");
We should get the following output:
ruof erocs dna neves sraey oga
ruo srehtaf thguorb htrof no siht tnenitnoc
Notice that the words appear in the same order as in the Strings that were
passed as parameters, but each individual word is reversed ("four" has
become "ruof", "score" has become "erocs" and so on).
The String you are passed might have leading or trailing spaces which
should be printed exactly as they appear in the String. For example, if we
make the following call:
printReversed(" merry-go-round is one word ");
the following output should be produced:
dnuor-og-yrrem si eno drow
This output has 3 spaces at the beginning of the line and 2 spaces at the
end of the line, just as in the String.
You are allowed to call the toCharArray method on the String to convert the
entire String into a char[] if you prefer to use array notation rather than
String notation in solving the problem.
Write your solution to printReversed below.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:06:12 PDT 2011