<![CDATA[
CSE143 Final
Winter 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.
+---+
| 3 |
+---+
\
\
+---+
| 5 |
+---+
/ \
/ \
+---+ +---+
| 9 | | 7 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 6 | | 8 | | 1 |
+---+ +---+ +---+
/ \ /
/ \ /
+---+ +---+ +---+
| 0 | | 2 | | 4 |
+---+ +---+ +---+
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: Luke, Kylo, Poe, Rey, BB8, Maz,
Finn. 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) {
Set<Integer> result = new TreeSet<Integer>();
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
result.add(i * 10 + data[i][j]);
}
}
return result;
}
In the left-hand column below are specific two-dimensional arrays. You are
to indicate in the right-hand column what values would be stored in the set
returned by method mystery if the array in the left-hand column is passed as
a parameter to mystery. Set elements should be listed in proper order as a
comma-separated bracketed list, as in [3, 18, 25].
Two-Dimensional Array Contents of Set Returned
------------------------------------------------------------------
[[1, 2], [3, 4]] ______________________________
[[7], [], [8, 8, 9, 10]] ______________________________
[[3, 14], [5, 13, 4], [4, 3, 1]] ______________________________
4. Collections Programming, 5 points. Write a method called recordTrip that
records information about trips taken by people. Trip information will be
stored in a map in which the keys are names of people and the values are
sets of place names. The method will take as parameters the map followed by
a person's name followed by a place name. For example, if we start with an
empty map stored in a variable called trips and we make the following calls:
recordTrip(trips, "John", "London");
recordTrip(trips, "Sally", "Seattle");
recordTrip(trips, "John", "Paris");
recordTrip(trips, "Sally", "San Francisco");
recordTrip(trips, "John", "NYC");
recordTrip(trips, "John", "Paris");
the map would store the following values after these calls:
{John=[London, NYC, Paris], Sally=[San Francisco, Seattle]}
Notice that the map needs to construct a set for each person to store the
names of the places they have visited. The sets it constructs should store
the place names in alphabetical order. You may construct iterators and the
sets that store place names, but you are not allowed to construct other
structured objects (no string, set, list, etc.).
5. Binary Trees, 10 points. Write a method called printLeaves that prints
the leaves of a binary tree from right to left. More specifically, the
leaves should be printed in the reverse order that they would be printed
using any of the standard traversals. For example, if t stores this tree:
+---+
| 2 |
+---+
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ / \
+---+ +---+ +---+
| 4 | | 5 | | 9 |
+---+ +---+ +---+
then the call:
t.printLeaves();
should produce the following output:
leaves: 9 5 4 0
You must exactly reproduce the format above for a nonempty tree. If the
tree is empty, your method should produce the output "no leaves". Your
method should always produce exactly one line of output. In other words,
if it is called n times, it should produce n lines of output.
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 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 call any other methods of the class and you may not use any
auxiliary data structure to solve this problem (no array, ArrayList, stack,
queue, String, etc).
6. Collections Programming, 10 points. Write a method called removePoints that
takes a map and an index as parameters and that removes particular points
from the map returning them in a set. The map this method will manipulate
uses integer indexes as keys and store as values a list of points. For
example, a variable called data might store the following:
{17=[[x=3,y=4], [x=12,y=6], [x=8,y=12], [x=3,y=6]],
42=[[x=2,y=5], [x=3,y=3], [x=1,y=5], [x=4,y=2], [x=8,y=9]],
308=[[x=1,y=2], [x=5,y=8], [x=4,y=4], [x=2,y=7], [x=3,y=9]]}
This map has three entries. The first entry associates the key 17 with a
list of four points. The second associates the key 42 with a list of five
points. The third associates 308 with a list that also has five points.
When the method is called, it will be passed the map and a key and it will
return a set of points, as in:
Set<Point> result = removePoints(data, 42);
The method should manipulate the list of points for the given index,
removing any points for which the x-value is less than the y-value and
returning these points in a set. After the call above, result should be:
[[x=2,y=5], [x=1,y=5], [x=8,y=9]]
and data should store the following:
{17=[[x=3,y=4], [x=12,y=6], [x=8,y=12], [x=3,y=6]],
42=[[x=3,y=3], [x=4,y=2]],
308=[[x=1,y=2], [x=5,y=8], [x=4,y=4], [x=2,y=7], [x=3,y=9]]}
Notice that the index 42 is now associated with a list of just two points
(the two that weren't removed). The method should return an empty set if
there are no points to remove or if the index value has no corresponding
entry in the map.
Your method should construct a set to return and may construct iterators,
but you are not allowed to construct other structured objects (no string,
set, list, etc.).
7. Comparable class, 20 points. Write a class called ItemOrder that stores
information about an item being ordered. Each ItemOrder object keeps track
of its item number (a string), an integer quantity, and a price per item
expressed as an integer number of pennies. For example:
ItemOrder item1 = new ItemOrder("007", 3, 36);
Notice that the quantity is passed as a parameter before the price in the
constructor, so this indicates an order for item number 007 with a quantity
of 3 at 36 cents each. The total price for this order would be 108 cents.
An ItemOrder can also store an optional note (a string) that appears in the
constructor after the item number, as in:
ItemOrder item2 = new ItemOrder("182", "red", 2, 1895);
This indicates an order for item number 182 with the note "red" and with a
quantity of 2 at 1895 cents per item. In addition to these two
constructors, the class should include the following public methods:
getItem() returns the item number for this item (without optional note)
getPrice() returns the total price for this order in pennies
toString() returns a String representation of the order
Listed below are patterns for formatting the toString result--the first
for items with no optional text, the second for orders with optional text.
item #<item>: <quantity>@$<price per> = $<total price>
item #<item> (<note>): <quantity>@$<price per> = $<total price>
For example, given the two variables defined above, item1.toString() should
return "item #007: 3@$0.36 = $1.08" and item2.toString() should return
"item #182 (red): 2@$18.95 = $37.90". Notice that prices are expressed as
dollars and cents in the usual format with 2 digits for pennies.
The ItemOrder class should implement the Comparable<E> interface. Item
orders should be ordered first by item number (sorted alphabetically) and
then by total price (sorted in reverse order with highest price first,
lowest price last). Recall that values considered "less" appear earlier in
a sorted list.
You may begin your solution to ItemOrder below, but an extra page is
provided for your answer after this page.
Continue your solution to ItemOrder below.
8. Binary Trees, 20 points. Write a method called makeFull that turns a binary
tree of integers into a full binary tree. A full binary tree is one in
which every node has either 0 or 2 children. Your method should produce a
full binary tree by replacing each node that has one child with a new node
that has the old node as a leaf where there used to be an empty tree. The
new node should store a value that indicates the level of the tree (-1 for
the first level of the tree, -2 for the second level of the tree, and so
on). For example, if a tree called t stores the following:
+----+
| 12 |
+----+
/
+----+
| 29 |
+----+
and we make the call:
t.makeFull();
then the tree should store the following after the call:
+----+
| -1 |
+----+
/ \
+----+ +----+
| 29 | | 12 |
+----+ +----+
Notice that the node storing 12 that used to be at the top of the tree is
now a leaf where there used to be an empty tree. In its place at the top of
the tree is a new node that stores the value -1 to indicate that it was
added at level 1 of the tree. Your method should perform this operation
at every level of the tree. For example, if t had instead stored:
+----+
| 12 |
+----+
/ \
+----+ +----+
| 28 | | 19 |
+----+ +----+
/ /
+----+ +----+
| 94 | | 32 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| 65 | | 18 | | 72 |
+----+ +----+ +----+
then after the call it would store:
+----+
| 12 |
+----+
/ \
+----+ +----+
| -2 | | -2 |
+----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 94 | | 28 | | -3 | | 19 |
+----+ +----+ +----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 65 | | 18 | | 32 | | 72 |
+----+ +----+ +----+ +----+
<continued on next page>
Notice that two nodes were added at level 2, and one at level 3.
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
containing negative values to be inserted into the tree and you will change
the links of the tree to restructure the tree as described, and 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
switchEvens that takes a second list of integers as a parameter and that
switches values in even numbered positions between the first and second
lists. For example, if the variables list1 and list2 store the following:
list1 = [3, 9, 5, 4, 2]
list2 = [7, 1, 0, 6, 18, 12, 8]
and you make the following call:
list1.switchEvens(list2);
The method switches the values at index 0 (3 and 7), the values at index 2
(5 and 0), and the values at index 4 (2 and 18), as indicated below:
list1 = [3, 9, 5, 4, 2]
| | |
list2 = [7, 1, 0, 6, 18, 12, 8]
After the method is called, the lists should store the following values:
list1 = [7, 9, 0, 4, 18]
list2 = [3, 1, 5, 6, 2, 12, 8]
Notice that it doesn't matter whether the numbers themselves are even but
whether they appear in even positions. Also notice that if one list is
longer than the other, then the values that don't have corresponding entries
in the shorter list are left unchanged.
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>
}
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 list.
Write your solution to switchEvens on the next page.
Write your solution to switchEvens below.
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