<![CDATA[
CSE142 Final
Winter 2012
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
This exam is divided into eleven questions with the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Expressions 5 _____
2 Array Simulation 10 _____
3 Inheritance 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 _____
11 Art (bonus) 1 _____
----------------------------------
Total 100 _____
This is a closed-book/closed-note exam. Space is provided for your answers.
There is a "cheat sheet" at the end that you can use as scratch paper or to
write answers. You are not allowed to access any other paper during the exam
(not even scratch paper). Use the backs of the pages of this test if
necessary. Anyone caught with extra paper will lose at least 10 points.
In general the exam is not graded on style and you do not need to include
comments, although all fields of a class should be declared private. 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 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. 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
8.0 / 4 / 4 + 3 / 4 + 0.5 * 3 __________
88 % 10 % 5/2 + 7 % 8 __________
2 * 3 + 4 + " = " + 5 * 6 + 7 __________
54 / 5 / 2.0 / 4 * 3 __________
2 * (0.75 + 1.25)/5 * 10 - 7/4 __________
2. Array 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. Inheritance, 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? (write the output as a series of
3-line columns in order from left to right)
4. Token-Based File Processing, 10 points. Write a static method called
reportRunningSum that takes as a parameter a Scanner holding a sequence of
real numbers and that prints to System.out the running sum of the numbers
followed by the maximum running sum. In other words, the n-th number that
you report should be the sum of the first n numbers in the Scanner and the
maximum that you report should be the largest such value that you report.
For example if the Scanner contains the following data:
3.25 4.5 -8.25 7.25 3.5 4.25 -6.5 5.25
your method should produce the following output:
running sum = 3.25 7.75 -0.5 6.75 10.25 14.5 8.0 13.25
max sum = 14.5
The first number reported is the same as the first number in the Scanner
(3.25). The second number reported is the sum of the first two numbers in
the Scanner (3.25 + 4.5). The third number reported is the sum of the first
three numbers in the Scanner (3.25 + 4.5 + -8.25). And so on. The maximum
of these values is 14.5, which is reported on the second line of output.
You are to exactly reproduce the format of this output. You may assume that
there is at least one number to read.
5. Line-Based File Processing, 9 points. Write a static method called
analyzeParagraphs that takes as a parameter a Scanner containing a text file
and that produces output that describes the paragraph structure of the file,
returning the maximum number of lines in any given paragraph. Each
paragraph in the input file will be terminated by the text "<p>" on a line
by itself. For example, consider the following input file:
This is an example of an input file
with four different paragraphs.
<p>
The second paragraph is the longest
with three lines, so your method should
return 3 when processing this file.
<p>
<p>
The third paragraph was empty. This one is just short.
<p>
The method should count the number of lines in each paragraph and report
that information to System.out. For example, if the input above is stored
in a Scanner called input and we make the following call:
int max = analyzeParagraphs(input);
It should produce the following output:
2-line paragraph
3-line paragraph
0-line paragraph
1-line paragraph
It would assign max the value 3 because the method returns the maximum
number of lines in any given paragraph. You must exactly reproduce the
format of this output. You may assume that the input file has no blank
lines, that it contains at least one paragraph, and that each paragraph is
terminated by a line containing just "<p>".
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.
You are not allowed to use an auxiliary data structure such as a temporary
array or ArrayList to solve this problem and you are not allowed to call any
methods of the Arrays class or the Collections class.
7. ArrayList, 10 points. Write a static method called removeAdjacentMatches
that removes extra copies of a value that are adjacent to it in an ArrayList
of integers. For example, if a variable called list contains the following:
[1, 3, 3, 15, 2, 2, 2, 2, 1, 19, 3, 42, 42, 42, 7, 42, 1]
and we make the following call:
removeAdjacentMatches(list);
Then list should store the following values after the call:
[1, 3, 15, 2, 1, 19, 3, 42, 7, 42, 1]
Notice that the two occurrences of 3 that appear next to each other have
been replaced with a single occurrence of 3, the four occurrences of 2 that
appear next to each other have been replaced with a single 2, and the three
occurrences of 42 that appear next to each other have been replaced with a
single 42. Notice, however, that the list still contains three occurrences
of 1, two occurrences of 3, and two occurrences of 42. That is because
those duplicate values do not appear right next to each other in the list.
You may not construct any extra data structures to solve this problem. You
must solve it by manipulating the ArrayList you are passed as a parameter.
8. Critters, 15 points. Write a class called Eagle that extends the Critter
class. The instances of the Eagle class switch back and forth between red
and blue in an increasing pattern. They should be red for their first move
and then blue for one move. Then they should be red for two moves and then
blue for two moves. Then they should be red for three moves and then blue
for three moves. Then they should be red for four moves and then blue for
four moves. And so on, each time increasing the number of moves at a
particular color by one. They should be displayed using a less-than
character followed by a greater-than character (<>). They should always hop
whenever possible. If they can't hop, they should turn right if there is a
wall in front of them and otherwise they should infect.
9. Arrays, 15 points. Write a static method called reverseSublist that takes
as parameters an array of integers and a "from index" (inclusive) and "to
index" (exclusive) and that returns a new array containing the specified
sublist in reverse order. For example, suppose that an array called list
stores the following values:
[0, 1, 2, 3, 4, 5, 6, 7]
and we make the following call:
int[] result = reverseSublist(list, 2, 5);
The sublist specified goes from index 2 (inclusive) to index 5 (exclusive).
In other words, it includes the values [2, 3, 4] from the list. The method
should construct and return a new array that contains this sequence of
values in reverse order:
[4, 3, 2]
This first example used an array of sequential integers, but the array might
contain any values. If the list instead stores these values:
[34, 9, -8, 17, 4, 32, 9]
and we make the following call:
int[] result = reverseSublist(list, 1, 5);
the method should instead return an array containing this sequence:
[4, 17, -8, 9]
You may assume that the two index values are legal:
0 <= (from index) <= (to index) <= (array length)
If the from-index and to-index are equal, your method should return an array
of length 0.
Your method should not change the array passed as a parameter. You are not
allowed to solve this problem using an ArrayList and you are not allowed to
call any methods of the Arrays class or the Collections class.
10. Programming, 10 points. Write a static method called removeZeros that
takes an array of integers as a parameter and that moves any zeros in the
array to the end of the array, otherwise preserving the order of the list.
For example, if a variable called "list" stores the following values:
[7, 2, 3, 0, 4, 6, 0, 0, 13, 0, 78, 0, 0, 19, 14]
then the call:
removeZeros(list);
should rearrange the values in the array so that it stores the following:
[7, 2, 3, 4, 6, 13, 78, 19, 14, 0, 0, 0, 0, 0, 0]
Notice that the six zeros have been moved to the end of the array and the
other values are in the same order as in the original list.
You are not allowed to use an auxiliary data structure such as a temporary
array or ArrayList to solve this problem and you are not allowed to call any
methods of the Arrays class or the Collections class.
11. Art, 1 point (bonus). You've programmed lions, bears, giants, and huskies,
but what kind of critter would your TA be? Give an artistic rendering of
how you see your TA fitting into the unforgiving world of the critter
simulation. You may either write a poem or draw a picture. If your answer
below indicates at least 1 minute of effort, you will receive full credit,
although your TA would probably appreciate it if you put in a little more
effort.
CSE142 Final Cheat Sheet
Math Method Description ArrayList Types
-------------------------------------- -----------------
Math.abs(n) absolute value of n ArrayList<String>
Math.max(x, y) maximum of x and y ArrayList<Integer>
Math.min(x, y) minimum of x and y
String Method Description
-----------------------------------------------------------------------------
charAt(index) character at a specific index
endsWith(text) whether or not string ends with text
equals(text) whether or not string equals text
equalsIgnoreCase(text) whether or not string equals text ignoring case
indexOf(text) index of a particular string (-1 if not found)
length() number of characters in string
startsWith(text) whether or not string starts with text
substring(start, stop) characters from start (inclusive) to stop (exclusive)
substring(start) characters from start to end of string
toLowerCase() a new String with lowercase version of original
toUpperCase() a new String with uppercase version of original
ArrayList method Description
-------------------------------------------------------------------------------
add(value) appends value at end of list
add(index, value) inserts value at index, shifting subsequent values right
clear() removes all elements of the list
contains(value) whether the list contains the value
get(index) returns the value at given index
isEmpty() whether list is empty
remove(index) removes value at index, shifting subsequent values left
set(index, value) replaces value at given index with given value
size() returns the number of elements in list
Critter Details
---------------
getMove returns one of Action.HOP, Action.LEFT, Action.RIGHT, Action.INFECT.
There are methods for finding out what kind of critters are around a critter
(one of Neighbor.WALL, Neighbor.EMPTY, Neighbor.SAME, Neighbor.OTHER):
getFront(), getBack(), getLeft(), getRight()
There is a method getDirection() to find out what direction a critter is facing
(one of Direction.NORTH, Direction.SOUTH, Direction.EAST, Direction.WEST)
public class FlyTrap extends Critter {
public String toString() {
return "T";
}
public Action getMove(CritterInfo info) {
if (info.getFront() == Neighbor.OTHER) {
return Action.INFECT;
} else {
return Action.LEFT;
}
}
public Color getColor() {
return Color.RED;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011