<![CDATA[
CSE143 Final
Winter 2014
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
The exam is divided into eleven 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 15 _____
9 Linked Lists 15 _____
10 Programming 10 _____
11 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.
+---+
| 4 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 1 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 7 | | 3 | | 8 | | 5 |
+---+ +---+ +---+ +---+
\ \ /
\ \ /
+---+ +---+ +---+
| 9 | | 6 | | 0 |
+---+ +---+ +---+
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: Moon, Sun, Mercury, Saturn,
Venus, Jupiter, Mars. 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 retainEqual that
takes a set of Point objects as a parameter and that retains only the points
where the x and y values are equal to each other. For example, if a set
called points contains the following values:
[[x=42,y=3], [x=4,y=2], [x=18,y=1], [x=7,y=8], [x=-2,y=-2], [x=3,y=3],
[x=7,y=7], [x=0,y=82], [x=14,y=14], [x=3,y=13], [x=-3,y=4], [x=1,y=3]]
and the following call is made:
retainEqual(points);
then points should store the following after the call (in no particular
order):
[[x=-2,y=-2], [x=3,y=3], [x=7,y=7], [x=14,y=14]]
Your method is expected to have reasonable efficiency in that it shouldn't
lead to more set operations than it needs to. You may construct iterator
objects, but you are not allowed to construct any structured objects to
solve the problem (no set, list, stack, queue, string, 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 convert that
takes as a parameter a set of strings representing phone numbers and that
returns a map of strings to sets of strings that represent the same phone
numbers split into exchange/suffix. In particular, the phone numbers in the
set passed to the method will each include a 3-digit exchange followed by a
dash followed by a four-digit suffix, as in:
[493-3923, 723-9278, 384-1917, 555-1795, 384-4923, 555-4923, 555-1212,
723-9823]
The method should split each string into the 3-digit exchanges that come
before the dash and the suffixes that come after. The method should
construct a map in which the keys are the 3-digit exchanges. Each such
exchange will be mapped to a set of 4-digit suffixes. For the set of phone
numbers above, the following map would be constructed:
{384=[1917, 4923], 493=[3923], 555=[1212, 1795, 4923], 723=[9278, 9823]}
Notice, for example, that three of the phone numbers in the original set
began with "555". In the map, the key "555" maps to a set of three elements
(the three suffixes that came after "555-").
Your method should construct the new map and each of the sets contained in
the map. Recall that the String class has a substring method that takes a
starting index (inclusive) and a stopping index (exclusive). For example:
"Australia".substring(1, 5) returns "ustr"
The keys of the new map should be ordered by the 3-digit exchanges and each
set should be ordered by the 4-digit suffixes in that set.
7. Comparable class, 20 points. Define a class FoodData that stores
information about a food item. Each FoodData object keeps track of the name
of the food along with its number of grams of fat, carbohydrate, and
protein. For example:
FoodData item1 = new FoodData("sausage biscuit", 31.0, 39.0, 11.0);
FoodData item2 = new FoodData("strawberry sundae", 6.0, 49.0, 6.0);
FoodData item3 = new FoodData("banana", 0.4, 31.1, 1.5);
In calling the constructor, the name is followed by fat grams, followed by
carbohydrate grams, followed by protein grams. For example, the sausage
biscuit above has 31 grams of fat, 39 grams of carbohydrate, and 11 grams
of protein. As in the third example, these values can be real numbers.
Your constructor should throw an IllegalArgumentException if any of the
numeric values passed to it is negative.
This class is being designed for programs that will help people who want to
use a low-fat diet. For example, it is a bit surprising that the McDonalds
sausage biscuit (item1) gets over 58% of its calories from fat while the
McDonalds strawberry sundae (item2) gets only 19.7% of its calories from
fat. The banana (item3) gets less than 2.7% of its calories from fat.
Your class should have the following public methods:
getName() returns the name of this food item
getCalories() returns total calories for this food item
percentFat() returns the percent of calories from fat for this item
toString() returns a String representation of this item
To compute total calories and percent fat, assume that each gram of fat is 9
calories and that each gram of carbohydrate and protein is 4 calories. For
example, the calories for the strawberry sundae (item2 above) are 274:
9 * (fat grams) + 4 * (carb grams) + 4 * (protein grams) =
9 * 6.0 + 4 * 49.0 + 4 * 6.0 = 274.0
Its percent fat is a little over 19.7 because the calories from fat are 54
and the total calories are 274. As usual, percentages should be expressed
as real numbers in the range of 0.0 to 100.0. You may assume that the
number of calories will be greater than 0.
The toString method should include the name of the item followed by a colon
followed by the fat, carbohydrate and protein grams, separated by commas,
and labeled, as in the following examples for item1, item2, and item3 above:
sausage biscuit: 31.0g fat, 39.0g carbohydrates, 11.0g protein
strawberry sundae: 6.0g fat, 49.0g carbohydrates, 6.0g protein
banana: 0.4g fat, 31.1g carbohydrates, 1.5g protein
Your class should also implement the Comparable interface. Items should be
ordered first by percent of calories coming from fat (lowest to highest) and
then by name (sorted alphabetically).
Write your solution to FoodData on the next page.
Write your solution to FoodData below.
8. Binary Trees, 15 points. Write a method called limitPathSum that removes
nodes from a binary tree of integers to guarantee that the sum of the values
on any path from the root to a node does not exceed some maximum value. For
example, suppose that a variable t stores a reference to the following tree:
+----+
| 29 |
+----+
/ \
+----+ +----+
| 17 | | 15 |
+----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| -7 | | 37 | | 4 | | 14 |
+----+ +----+ +----+ +----+
/ \ \ / \
+----+ +----+ +----+ +----+ +----+
| 11 | | 12 | | 16 | | -9 | | 19 |
+----+ +----+ +----+ +----+ +----+
Then the call:
t.limitPathSum(50);
will remove nodes so as to guarantee that no path from the root to a node
has a sum that is greater than 50. This will require removing the node with
12 in it because the sum of the values from the root to that node is greater
than 50 (29 + 17 + -7 + 12, which is 51). Similarly, we have to remove the
node with 37 in it because its sum is too high (29 + 17 + 37, which is 83).
Whenever you remove a node, you remove anything under it as well, so
removing the node with 37 also removes the node with 16 in it. We also
remove the node with 14 and everything under it because its sum is too high
(29 + 15 + 14, which is 58). Thus, we end up with:
+----+
| 29 |
+----+
/ \
+----+ +----+
| 17 | | 15 |
+----+ +----+
/ /
+----+ +----+
| -7 | | 4 |
+----+ +----+
/
+----+
| 11 |
+----+
The method would be forced to remove all nodes if the data stored at the
overall root is greater than the given maximum.
Assume that 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. 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).
9. Linked Lists, 15 points. Write a method of the LinkedIntList class called
mergeFrom that takes a list of integers as a parameter and that moves the
values from the second list into the first list so as to preserve sorted
order assuming that the two lists are in sorted (nondecreasing) order
initially. The resulting list should contain the values from both lists in
sorted order and the list passed as a parameter should be empty after the
call. For example, if the variables list1 and list2 store the following:
list1 = [-3, 0, 9, 12, 43, 54], list2 = [9, 9, 15, 98]
and you make the following call:
list1.mergeFrom(list2);
then the lists should store the following values after the call:
list1 = [-3, 0, 9, 9, 9, 12, 15, 43, 54, 98], list2 = []
Notice that list2 is empty after the call and that the values that were in
list2 have been moved into list1 so as to preserve sorted order. If the
call instead had been list2.mergeFrom(list1) then the result would be:
list1 = [], list2 = [-3, 0, 9, 9, 9, 12, 15, 43, 54, 98]
Either list might be empty, as in:
list1 = [5, 7, 7, 12, 15], list2 = []
in which case the call list1.mergeFrom(list2) would leave the lists
unchanged while list2.mergeFrom(list1) would leave you in this state:
list1 = [], list2 = [5, 7, 7, 12, 15]
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 merged list. As
in the examples above, assume that both lists are in sorted order.
10. Programming, 10 points. Write a constructor for the IntTree class that
takes an integer n as a parameter and that constructs a balanced binary
tree of n nodes such that a postorder traversal of the tree will produce
the sequence of numbers 1 through n inclusive. The tree that is
constructed should have the property that for every node in the tree,
either the left and right subtrees have the same number of nodes or the
left subtree has one more node than the right subtree. For example:
IntTree t = new IntTree(6);
would set t to the following tree:
+---+
| 6 |
+---+
/ \
+---+ +---+
| 3 | | 5 |
+---+ +---+
/ \ /
+---+ +---+ +---+
| 1 | | 2 | | 4 |
+---+ +---+ +---+
You are writing a public constructor for a binary tree class defined as in
problem 8. Assume the IntTreeNode class has the following constructor:
// 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;
}
You are writing a constructor 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. You will construct new
nodes, but you may not construct any auxiliary data structure to solve this
problem (no array, ArrayList, stack, queue, String, etc). Your constructor
should produce an empty tree if passed the value 0 and should throw an
IllegalArgumentException if passed a negative number.
11. 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