<![CDATA[
CSE143 Final
Fall 2012
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
The exam is divided into ten questions with the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Binary Tree Traversal 6 _____
2 Binary Search Tree 4 _____
3 Collections Mystery 5 _____
4 Collections Programming 5 _____
5 Binary Trees 10 _____
6 Collections Programming 10 _____
7 Comparable class 20 _____
8 Binary Trees 20 _____
9 Linked Lists 20 _____
10 Fiction (bonus) 1 _____
----------------------------------
Total 100 _____
This is a closed-book/closed-note exam. Space is provided for your answers.
There is a 2-page "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 you are required to declare all data fields and helper
methods as private, to use generics properly, and to declare variables and
parameters using interfaces when possible. 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).
You are not allowed to use a calculator or other electronic device while
working on this exam. 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. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 0 | | 3 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 5 | | 7 | | 4 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 1 | | 6 | | 9 | | 8 |
+---+ +---+ +---+ +---+
Fill in each of the traversals below:
Preorder traversal __________________________________________________
Inorder traversal __________________________________________________
Postorder traversal __________________________________________________
2. Binary Search Tree, 4 points. Draw a picture below of the binary search
tree that would result from inserting the following names into an empty
binary search tree in the following order: Pride, Envy, Greed, Lust,
Anger, Sloth, Gluttony.
3. Collections Mystery, 5 points. Consider the following method:
public Map<String, String> mystery(List<String> list1,
List<String> list2) {
Map<String, String> result = new TreeMap<String, String>();
for (int i = 0; i < list1.size(); i++) {
result.put(list1.get(i), list2.get(i));
result.put(list2.get(i), list1.get(i));
}
return result;
}
The three entries below have specific values for the first and second
parameters to method mystery (when you see text like the letter b, that
indicates that the list stores the String "b" in that position). For each
entry, indicate what values would be stored in the map returned by method
mystery3 if the given lists are passed as parameters. Map elements should
be listed with "key=value" elements, as in {b=z, d=e}. You should list the
map entries in their proper order.
list1: [b, l, u, e] list2: [s, p, o, t]
map returned:__________________________________________________________
list1: [k, e, e, p] list2: [s, a, f, e]
map returned:__________________________________________________________
list1: [s, o, b, e, r] list2: [b, o, o, k, s]
map returned:__________________________________________________________
4. Collections Programming, 5 points. Write a method called retainAll that
takes two sets of integers as parameters and that removes any values in the
first set that are not found in the second set. For example, given sets:
s1: [0, 19, 8, 9, 12, 13, 14, 15]
s2: [0, 19, 2, 4, 5, 9, 10, 11]
If the following call is made:
retainAll(s1, s2);
after the call, the sets would store the following values:
s1: [0, 19, 9]
s2: [0, 19, 2, 4, 5, 9, 10, 11]
You are implementing a two-argument alternative to the standard Set method
called retainAll, so you are not allowed to call that method to solve this
problem. You are also not allowed to construct any structured objects to
solve the problem (no set, list, stack, queue, string, etc) although you can
construct iterators. Your method should not change the second set passed
as a parameter.
5. Binary Trees, 10 points. Write a method called evenBranches that returns
the number of branch nodes in a binary tree that contain even numbers. A
branch node is one that has one or two children (i.e., not a leaf). For
example, if a variable t stores a reference to the following tree:
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ \
/ \
+---+ +---+
| 4 | | 9 |
+---+ +---+
then the call t.evenBranches() should return 3 because there are three
branch nodes with even values (2, 8 and 6). Notice that the leaf nodes with
even values are not included (the nodes storing 0 and 4).
You are writing a public method for a binary tree class defined as follows:
public class IntTreeNode {
public int data; // data stored in this node
public IntTreeNode left; // reference to left subtree
public IntTreeNode right; // reference to right subtree
<constructors>
}
public class IntTree {
private IntTreeNode overallRoot;
<methods>
}
You may define private helper methods to solve this problem, but otherwise
you may not call any other methods of the class. You may not define any
auxiliary data structures to solve this problem.
6. Collections Programming, 10 points. Write a method called recordMoves that
records a series of moves made by players in a game. The idea is that there
is a grid of possible (x, y) locations and each Move object indicates a
player moving onto a specific location. The Move class has the following
public methods:
getX() returns the x-coordinate of this move
getY() returns the y-coordinate of this move
getName() returns the name of the player making this move
Initially the grid is empty, but as moves are recorded, the grid will fill
up with various players at different locations in the world. For example,
suppose that the following sequence of moves is made:
Simone moves to (0, 0), Sam moves to (0, 3), Jia Le moves to (3, 3),
Sara moves to (4, 4), Adam moves to (2, 1), Dane moves to (3, 2),
Ally moves to (0, 4)
Your method should produce a map whose keys are Point objects and whose
values are the names of players. For example, given the sequence above,
you'd end up with the following associations (in no particular order):
{[x=0,y=3]=Sam, [x=0,y=0]=Simone, [x=3,y=3]=Jia Le, [x=2,y=1]=Adam,
[x=4,y=4]=Sara, [x=0,y=4]=Ally, [x=3,y=2]=Dane}
It is possible that a player will move onto an occupied location. If that
happens, the new player replaces the old player and the old player is put
into a special graveyard list. For example, given this sequence of moves:
Alex moves to (1, 3), Victoria moves to (0, 1), Gabe moves to (1, 3),
Janette moves to (4, 0), Matt moves to (0, 1), Riley moves to (1, 2),
Charlie moves to (1, 3)
We would end up with the following associations (in no particular order):
{[x=1,y=2]=Riley, [x=1,y=3]=Charlie, [x=0,y=1]=Matt, [x=4,y=0]=Janette}
For the location (1, 3), we first get Alex at that location, then Gabe moves
there and replaces him, sending Alex to the graveyard. Then Charlie
replaces Gabe, sending Gabe to the graveyard. The following players end up
in the graveyard:
graveyard = [Alex, Victoria, Gabe]
Players should be added to the graveyard in the order in which they are
killed. In the first example, the graveyard would have been empty.
Your method should take two parameters: the list of Move objects followed by
the graveyard (a list of strings that will initially be empty). You are to
construct and return an appropriate map and add names to the graveyard if
any players die. You may assume that no player appears in more than one
move.
Your method should construct the new map and can construct iterators and one
Point object per move, but should otherwise not construct any new data
structures. It should not modify the list of moves passed as a parameter,
but it should change the graveyard list if appropriate.
<continued on next page>
Write your solution to recordMoves below.
7. Comparable class, 20 points. Define a class called USCurrency that can be
used to store a currency amount in dollars and cents (both integers) where
one dollar is 100 cents. Your class should include the following methods:
USCurrency(dollars, cents) constructs a currency object with given
dollars and cents
dollars() returns the dollars
cents() returns the cents
toString() returns a String in standard $d.cc notation
(-$d.cc for negative amounts)
add(other) returns the result of adding another
currency amount to this one
subtract(other) returns the result of subtracting another
currency amount from this one
A currency amount can be negative. The constructor should allow you to pass
any values for dollars and cents, including negative values, and mixtures of
negatives and positives. The cents method should return values in the range
of 0 to 99 for nonnegative currency amounts and should return values in the
range of 0 to -99 for negative currency amounts. For example, the
constructor might be asked to work with 38 dollars and -413 cents, but that
would be reported as 33 dollars and 87 cents.
The add and subtract methods should return new USCurrency objects that
represent the result of adding or subtracting the other currency amount.
They should not change the two currency objects being added or subtracted.
Note that the toString method should return the amount in a standard format
($d.cc) with two digits for cents and with negative values indicated with a
single minus sign in front of the dollar sign (-$d.cc). For example, 4
dollars and 5 cents would be expressed as "$4.05" while -19 dollars and -43
cents would be expressed as "-$19.43".
In addition, your class should implement the Comparable<E> interface.
USCurrency objects should be compared in the obvious way, with smaller
currency amounts considered "less" than larger currency amounts (e.g.,
-$13.45 < -$2.03 < $5.13 < $98.06).
8. Binary Trees, 20 points. Write a method called stretch that stretches
each node that has only one child in a binary tree of integers. More
specifically, each node that has a single child should be replaced by a new
node storing the data 1 and with the old node as a child in the same
direction as the original node's child. For example, suppose a variable t
stores a reference to the following tree:
+----+
| 13 |
+----+
/ \
+----+ +----+
| 48 | | 17 |
+----+ +----+
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/ \
+----+ +----+
| 65 | | 10 |
+----+ +----+
There are two nodes in this tree that have a single child: the nodes storing
48 and 17. Each of those nodes is replaced in the tree with a new node
storing the value 1 and with the original node as a child in the same
direction as its only child. The node storing 48 has a left child, so it
appears to the left of a new node storing 1. The node 17 has a right child,
so it appears to the right of a new node storing 1. So after the call:
t.stretch();
The tree should look like this:
+----+
| 13 |
+----+
/ \
+----+ +----+
| 1 | | 1 |
+----+ +----+
/ \
+----+ +----+
| 48 | | 17 |
+----+ +----+
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/ \
+----+ +----+
| 65 | | 10 |
+----+ +----+
This stretching process should be performed on every node in the original
tree that has a single child.
<continued on next page>
You are writing a public method for a binary tree class defined as follows:
public class IntTreeNode {
public int data; // data stored in this node
public IntTreeNode left; // reference to left subtree
public IntTreeNode right; // reference to right subtree
// post: constructs an IntTreeNode with the given data and links
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public class IntTree {
private IntTreeNode overallRoot;
<methods>
}
You are writing a method that will become part of the IntTree class. You
may define private helper methods to solve this problem, but otherwise you
may not assume that any particular methods are available. You are NOT to
change the data field of the existing nodes in the tree. You will, however,
construct new nodes containing the value 1 to be inserted into the tree and
you will change the links of the tree to include these new nodes.
9. Linked Lists, 20 points. Write a method called weave that takes a list of
integers as a parameter and that combines the values from the second list
into the first list in an alternating fashion, leaving the second list
empty. The new list should start with the first value of the first list
followed by the first value of the second list followed by the second value
of the first list followed by the second value of the second list, and so
on. For example, if the variables list1 and list2 store the following:
list1 = [0, 2, 4, 6], list2 = [1, 3, 5, 7]
If you make the following call:
list1.weave(list2);
then the lists should store the following values after the call:
list1 = [0, 1, 2, 3, 4, 5, 6, 7], list2 = []
Notice that the second list is empty after the call and that the values that
were in the second list have been moved into the first list in an
alternating fashion. If the call had instead been:
list2.weave(list1);
then the lists would have stored the following values after the call:
list1 = [], list2 = [1, 0, 3, 2, 5, 4, 7, 6]
These examples use sequential integers to make it easier to see the intended
order, but the values can be any numbers at all. It is also possible that
one list will have more values than the other, in which case its values
should simply be appended to the end of the list. For example, if the lists
store these values:
list1 = [3, 18, 9], list2 = [-5, 4, 13, 42, 0, 23]
then the call list1.weave(list2) should produce this result:
list1 = [3, -5, 18, 4, 9, 13, 42, 0, 23], list2 = []
while the call list2.weave(list1) should produce this result:
list1 = [], list2 = [-5, 3, 4, 18, 13, 9, 42, 0, 23]
You are writing a public method for a linked list class defined as follows:
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>
}
<continued on next page>
You are writing a method that will become part of the LinkedIntList class.
Both lists are of type LinkedIntList. You may define private helper methods
to solve this problem, but otherwise you may not assume that any particular
methods are available. You are allowed to define your own variables of type
ListNode, but you may not construct any new nodes, and you may not use any
auxiliary data structure to solve this problem (no array, ArrayList, stack,
queue, String, etc). You also may not change any data fields of the nodes.
You MUST solve this problem by rearranging the links of the lists. Your
solution must run in O(n) time where n is the length of the list.
10. Fiction, 1 point (bonus). Your TA has woken up in jail. Explain why. You
may express your answer in any way you choose by writing a story, drawing a
picture, writing a poem, etc. 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