<![CDATA[
CSE142 Final
Autumn 2014
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 can also request scratch paper from a TA. You are not
allowed to access any of your own papers during the exam.
In general the exam is not graded on style and you do not need to include
comments, although the Critter class has special requirements you must follow.
You are limited to the constructs described in chapters 1 through 10 of the
textbook, which means that you are not allowed to use break statements or to
have a return from a void method. You are not allowed to use methods from the
Arrays class or other methods that aren't included on the cheat sheet. 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. 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
2 + 3 * (2 + 3) + 17 / 4 __________
67 % 10 % 5 * 6 - 3 % 6 __________
7.5 * 2 + 19 / 2 / 2.0 - 0.5 - 1 / 2 __________
4 + 2 * 2 + "2 * 2" + 2 * 2 + 4 __________
43 / 4 / 3 * 5.0 / 2 + 5 / 2 __________
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 - 1; i++) {
if (i % 2 == 0) {
list[i] = list[i] - list[i - 1];
} else {
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
------------------------------------------------------------
{1} ____________________________
{2, 5, 9} ____________________________
{2, 3, 7, 2} ____________________________
{2, 4, 5, 4, 3} ____________________________
{5, 1, 8, 4, 8, 4} ____________________________
3. Inheritance, 6 points. Assume the following classes have been defined:
public class A extends D {
public String toString() {
return "a";
}
public void method1() {
System.out.println("a 1");
}
}
public class B extends C {
public String toString() {
return "b";
}
}
public class C extends D {
public void method1() {
System.out.println("c 1");
}
}
public class D {
public String toString() {
return "d";
}
public void method1() {
System.out.println("d 1");
}
public void method2() {
System.out.println("d 2");
}
}
Consider the following code fragment:
D[] elements = {new C(), new A(), new D(), new B()};
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 (do not label columns or rows).
4. Token-Based File Processing, 10 points. Write a static method called
evaluate that takes as a parameter a Scanner containing a series of tokens
that represent a numeric expression involving addition and subtraction and
that returns the value of the expression. For example, if a Scanner called
data contains the following tokens:
4.2 + 3.4 - 4.1
and we make the following call:
evaluate(data)
the method should return 3.5 because 4.2 + 3.4 - 4.1 evaluates to 3.5.
Every expression will begin with a real number and then will have a series
of operator/number pairs that follow. The operators will be either "+"
(addition) or "-" (subtraction). As in the example above, there will be
spaces separating numbers and operators. Assume the expression is legal.
Your program should evaluate operators sequentially from left to right. For
example, for this expression:
7.3 - 4.1 - 2.0
your method should evaluate the operators as follows:
7.3 - 4.1 - 2.0 = (7.3 - 4.1) - 2.0 = 3.2 - 2.0 = 1.2
The Scanner might contain just a number, in which case your method should
return that number as its result. You may not construct any extra data
structures to solve this problem.
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>". You may not construct any extra
data structures to solve this problem.
6. Arrays, 10 points. Write a static method called hasAlternatingParity that
returns whether or not an array 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 these values are stored in an array called data and we make this call:
hasAlternatingParity(data)
the method would return true. If the array instead stored these values:
[2, 13, 4, 1, 0, 9, 2, 7, 4, 12, 3, 2]
it would return false because there are two even numbers in a row (4, 12).
By definition, an empty list or a list of one element has alternating
parity. You may assume the values in the array are not negative.
You may not construct any extra data structures to solve this problem.
7. ArrayList, 10 points. Write a static method called collapse that takes an
ArrayList of integer values as a parameter and that replaces each successive
pair of integers in the list 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]
Then the following call:
collapse(list);
should leave the list with the following values:
[9, 17, 17, 8, 19]
The first pair from the original list is collapsed into 9 (7 + 2), the
second pair is collapsed into 17 (8 + 9), the third pair is collapsed into
17 (4 + 13) and so on.
If the list stores an odd number of elements, the final element is not
collapsed. For example, if the list had been:
[1, 2, 3, 4, 5]
Then the call on collapse would produce the following list:
[3, 7, 5]
with the 5 at the end of the list unchanged. 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. See the cheat
sheet for a list of available ArrayList methods.
8. Critters, 15 points. Write a class called Counter that extends the Critter
class. The constructor for the Counter class takes an integer indicating a
maximum value to count up to. For example, you would pass the value 5 to
the Counter constructor to indicate that the corresponding Counter object
should count up to 5. Different Counter objects will have different maximum
values. On each successive move, the Counter object should display with an
increasing count relative to its maximum until it reaches the maximum and
then it should start back at 1. If the maximum is 5, it will go through
this cycle of values when toString is called:
1/5, 2/5, 3/5, 4/5, 5/5, 1/5, 2/5, 3/5, 4/5, 5/5, 1/5, ...
It initially displays as "1/5", then after one move it becomes "2/5", etc.,
starting back at "1/5" after 5 moves. For a maximum of 3, the pattern is:
1/3, 2/3, 3/3, 1/3, 2/3, 3/3, 1/3, 2/3, 3/3
Counter objects should be blue. They should always infect if an enemy is in
front. If there isn't an enemy to infect, they should hop if possible. If
there is no enemy in front and they can't hop, they should turn left.
As in assignment 9, all fields must be declared private and fields that need
to be initialized to a non-default value must be set in a constructor.
9. Arrays, 15 points. Write a static method called combineSublists that takes
as parameters two arrays of integers, a "from index" (inclusive), and a "to
index" (exclusive), and that returns a new array containing the specified
sublist from the first list followed by the specified sublist from the
second list. For example, if arrays list1 and list2 store the following:
list1 = [7, 15, 4, 3, 8, 2] list2 = [42, -3, 5, 12, 17, 6, 0]
then the call combineSublists(list1, list2, 1, 5) should return this array:
[15, 4, 3, 8, -3, 5, 12, 17]
| | | |
+--list1--+ +--list2--+
Notice that the new array has values from list1 from indexes 1 through 4
followed by values form list2 from indexes 1 through 4. The call
combine(list1, list2, 5, 6) would return this array:
[2, 6]
It includes the value from index 5 of list1 followed by the value at index 5
from list2. If the start and stop indexes are equal, your method should
return an empty array. You may assume that the method is not passed indexes
that would be illegal for the two arrays passed as parameters. The method
should not construct any extra data structures other than the array to be
returned and it should not alter its two array parameters.
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.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011