<![CDATA[
CSE143 Final
Autumn 2017
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
Student #____________________________
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 "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 you are required to declare all data fields and helper
methods as private, to use generics properly, to declare variables and
parameters using interfaces when possible, and to avoid the use of break
statements, the diamond operator, and return from a void method. 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).
For standard Java classes such as Math and String, you are limited to the
methods listed on the cheat sheet. You are not allowed to use the Arrays or
Collections classes or other standard classes and methods that aren't included
on the cheat sheet.
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.
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 9 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 4 | | 6 | | 0 |
+---+ +---+ +---+ +---+
\ \ /
\ \ /
+---+ +---+ +---+
| 8 | | 1 | | 5 |
+---+ +---+ +---+
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 words into an empty
binary search tree in the following order: Mike, Will, Nancy, Eleven, Lucas,
Dustin, Steve. Assume the search tree uses alphabetical ordering to compare
words.
3. Collections Mystery, 5 points. Consider the following method:
public Set<Integer> mystery(int[][] data, int n) {
Set<Integer> result = new TreeSet<Integer>();
for (int j = 0; j < data[n].length; j++) {
result.add(data[n][j]);
}
for (int i = 0; i < data.length; i++) {
result.remove(data[i][n]);
}
return result;
}
Suppose that a variable called grid has been declared as follows:
int[][] grid = {{5, 2, 2, 2, 4, 2}, {6, 2, 4, 3, 5, 9},
{5, 2, 1, 2, 9, 8}, {5, 3, 4, 2, 6, 4}};
which means it will store the following 4-by-6 grid of values:
5 2 2 2 4 2
6 2 4 3 5 9
5 2 1 2 9 8
5 3 4 2 6 4
For each call below, indicate what value is returned. If the method call
results in an exception being thrown, write "exception" instead.
Method Call Contents of Set Returned
mystery(grid, 0) _________________________________
mystery(grid, 1) _________________________________
mystery(grid, 3) _________________________________
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 toString method for a binary tree of
integers. The method should return "empty" for an empty tree. For a leaf
node, it should return the data in the node as a String. For a branch node,
it should return a parenthesized String that has three elements separated by
commas: the data at the root followed by a String representation of the left
subtree followed by a String representation of the right subtree. 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.toString() should return the following String:
"(2, (8, 0, empty), (1, (7, 4, empty), (6, empty, 9)))"
The quotes above are used to indicate that this is a String but should not
be included in the String that you return.
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 pointMap that
takes a list of points as a parameter and that returns a map that
associates each point from the list with a list of indexes at which that
point occurs. For example, if a variable called list stores the following:
[[x=1,y=3], [x=7,y=7], [x=1,y=3], [x=7,y=8], [x=1,y=3], [x=1,y=3],
[x=7,y=7], [x=7,y=8], [x=4,y=2], [x=7,y=8], [x=7,y=8], [x=4,y=2],
[x=1,y=3], [x=4,y=2]]
then the call pointMap(list) should return the following map:
{[x=4,y=2]=[8, 11, 13], [x=1,y=3]=[0, 2, 4, 5, 12], [x=7,y=7]=[1, 6],
[x=7,y=8]=[3, 7, 9, 10]}
Notice that each point from the original list maps to a list of indexes.
For example, the point [x=1,y=3] appeared at indexes 0, 2, 4, 5, and 12,
so it maps to a list with those values. The lists that each point maps
to should have indexes in increasing order, as in the example.
Your method should construct the new map and each of the lists contained in
the map and can construct iterators but should otherwise not construct any
other structured objects (no string, set, list, etc.). It should also not
modify the list of points passed as a parameter and it should be reasonably
efficient.
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).
You may begin your solution to USCurrency below, but an extra page is
provided for your answer after this page.
Continue your solution to USCurrency below.
8. Binary Trees, 20 points. Write a method called add that takes as a
parameter a reference to a second binary tree and that adds the values in
the second tree to this tree. If the method is called as follows:
tree1.add(tree2);
it should add all values in tree2 to the corresponding nodes in tree1. In
other words, the value stored at the root of tree2 should be added to the
value stored at the root of tree1 and the values in tree2's left and right
subtrees should be added to the corresponding positions in tree1's left and
right subtrees. The values in tree2 should not be changed by your method.
initial tree1 initial tree2 final tree1
+---+ +---+ +---+
| 1 | | 2 | | 3 |
+---+ +---+ +---+
/ \ / \ / \
+---+ +---+ +---+ +---+ +---+ +---+
| 4 | | 7 | | 3 | | 1 | | 7 | | 8 |
+---+ +---+ +---+ +---+ +---+ +---+
If tree1 has a node that has no corresponding node in tree2, then that node
is unchanged. For example, if tree2 is empty, tree1 is not changed at all.
It is also possible that tree2 will have one or more nodes that have no
corresponding node in tree1. For each such node, create a new node in tree1
in the corresponding position with the value stored in tree2's node. For
example:
initial tree1 initial tree2 final tree1
+---+ +---+ +---+
| 6 | | 1 | | 7 |
+---+ +---+ +---+
/ / \ / \
+---+ +---+ +---+ +---+ +---+
| 2 | | 4 | | 5 | | 6 | | 5 |
+---+ +---+ +---+ +---+ +---+
/ \ / \
+---+ +---+ +---+ +---+
| 8 | | 2 | | 8 | | 2 |
+---+ +---+ +---+ +---+
<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 (what we called
"morphing" in assignments 7 and 8). You will, however, construct new nodes
to be inserted into the tree as described above (notice the 3-argument
TreeNode constructor that can be used to do so) and you will change the
links of the tree to restructure the tree as described. Your solution must
run in O(n) time where n is the number of nodes in the tree.
9. Linked Lists, 20 points. Write a method of the LinkedIntList class called
switchPairsOfPairs that rearranges each successive sequence of 4 values by
switching the order of the two pairs that make up the sequence. Suppose,
for example, that a variable called list stores the following values:
[1, 2, 3, 4, 5, 6, 7, 8]
| | | | | | | |
+--+ +--+ +--+ +--+
pair pair pair pair
As indicated, this list has four pairs. If the following call is made:
list.switchPairsOfPairs();
the following sequence would be produced:
[3, 4, 1, 2, 7, 8, 5, 6]
| | | | | | | |
+--+ +--+ +--+ +--+
pair pair pair pair
Notice that the pair (1, 2) has been switched with the pair (3, 4) and that
the pair (5, 6) has been switched with the pair (7, 8).
This example purposely used sequential integers to make the rearrangement
clear, but you should not expect that the list will store sequential
integers. It also might have extra values at the end that are not part of a
group of four. Such values should not be moved. For example, if the list
had stored this sequence of values:
[3, 8, 19, 42, 7, 26, 19, -8, 193, 204, 6, -4, 99, 2]
then a call on the method would have produced this sequence:
[19, 42, 3, 8, 19, -8, 7, 26, 6, -4, 193, 204, 99, 2]
Notice that the values 99 and 2 that appear at the end have not been moved
because they are not part of a complete group of four values.
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>
Your method will become part of the LinkedIntList 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 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 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