<![CDATA[
CSE143 Final
Fall 2010
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 Art (bonus) 1 _____
----------------------------------
Total 100 _____
This is a closed-book/closed-note exam. You are allowed to have one
hand-written index card up to 5" x 8". Space is provided for your answers.
Use the backs of the pages of this test if necessary. The last two pages
include the "cheat sheet" and can be used as scratch paper. You are not
allowed to access any other paper during the exam (not even scratch paper).
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.
+---+
| 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: Ginger, Professor, Skipper,
Lovey, Gilligan, Thurston, Maryann.
3. Collections Mystery, 5 points. Consider the following method:
public List<Integer> mystery(int[][] data) {
List<Integer> result = new LinkedList<Integer>();
for (int i = 1; i < data.length; i++) {
for (int j = 0; j < data[i].length - 1; j++) {
result.add(data[i][j] - 1);
}
}
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 list
returned by method mystery if the array in the left-hand column is passed as
a parameter to mystery. List elements should be listed in proper order as a
comma-separated bracketed list, as in [3, 18, 25].
Two-Dimensional Array Contents of List Returned
------------------------------------------------------------------
[[0, 1], [2, 3]] ______________________________
[[0, 1, 2], [3, 4, 5], [6, 7, 8]] ______________________________
[[3, 4], [1, 2, 3], [], [5, 6]] ______________________________
4. Collections Programming, 5 points. Write a method called equals that takes
two sets of integers as parameters and that returns true if the sets are
equal. Two sets are considered equal if they store the same values. For
example, given sets:
s1: [5, 3, 1, 0]
s2: [0, 1, 5, 3]
s3: [1, 0, 5, 3, 4]
The call equals(s1, s2) would return true while the calls equals(s1, s3) and
equals(s2, s3) would return false. As in the examples above, you can not
assume that the set values are ordered.
You are implementing a two-argument alternative to the standard Set method
called equals, so you are not allowed to call that method or the containsAll
method to solve this problem. You may construct iterator objects, but you
are also not allowed to construct any structured objects to solve the
problem (no set, list, stack, queue, string, etc). Your method should not
change either of the sets passed as parameters.
5. Binary Trees, 10 points. Write a method countMultiples that returns a count
of the number of multiples of a particular value in a binary tree of
integers. Given a number n, a value m is considered a multiple of n if it
can be expressed as (k * n) for some integer k. For example, suppose that a
variable t stores a reference to the following tree:
+---+
| 6 |
+---+
/ \
+---+ +---+
| 2 | | 9 |
+---+ +---+
/ \ \
+---+ +---+ +---+
| 5 | | 3 | | 4 |
+---+ +---+ +---+
/ \ / \
+---+ +---+ +---+ +---+
| 8 | | 6 | | 7 | | 0 |
+---+ +---+ +---+ +---+
The table below shows various calls and the values returned.
method call returns explanation
-------------------------------------------------------------------
t.countMultiples(2) 6 six multiples of 2: 6, 2, 4, 8, 6, 0
t.countMultiples(4) 3 three multiples of 4: 4, 8, 0
t.countMultiples(3) 5 five multiples of 3: 6, 9, 3, 6, 0
t.countMultiples(1) 10 all ten numbers are multiples of 1
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. Your method should throw an
IllegalArgumentException if passed the value 0.
6. Collections Programming, 10 points. Write a method pointCount that takes as
a parameter a list of Point objects and that returns a map that stores for
each Point from the list how many occurrences there are of that Point in the
list. For example, given a variable list storing the following:
list: [[x=1,y=3], [x=7,y=8], [x=4,y=2], [x=7,y=8], [x=4,y=3],
[x=1,y=3], [x=4,y=2], [x=4,y=2], [x=18,y=4], [x=7,y=8],
[x=4,y=3], [x=2,y=2], [x=0,y=7], [x=7,y=0]]
the method call pointCount(list) should return the following map:
{[x=2,y=2]=1, [x=4,y=2]=3, [x=0,y=7]=1, [x=7,y=0]=1, [x=18,y=4]=1,
[x=1,y=3]=2, [x=4,y=3]=2, [x=7,y=8]=3}
This map indicates that the point [x=2,y=2] occurred once in the list, the
point [x=4,y=2] occurred 3 times, and so on. The map entries can be stored
in any order.
You may construct iterator objects, but you may not construct any structured
objects other than the map you are returning. Traversing the list should
take O(n) time even if the list is a linked list. Your method should not
change the list passed as a parameter.
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.
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, 20 points. Write a method 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. Homeworks 7 and 8 involved full
binary trees (20 questions, Huffman). Your method should produce a full
binary tree by eliminating all nodes that have only one child. For example,
if a variable called t stores a reference to the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 28 | | 19 |
+----+ +----+
/ /
/ /
+----+ +----+
| 94 | | 32 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 65 | | -8 | | 72 |
+----+ +----+ +----+
\ / \
\ / \
+----+ +----+ +----+
| 10 | | 42 | | 50 |
+----+ +----+ +----+
then the call:
t.makeFull();
should leave t storing the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 94 | | 72 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 65 | | 10 | | 42 | | 50 |
+----+ +----+ +----+ +----+
Notice that the nodes that stored the values 28, 19, 32, and -8 have all
been eliminated from the tree because each had one child. When a node is
removed, it is replaced by its child. Notice that this can lead to multiple
replacements because the child might itself be replaced (as in the case of
19 which is replaced by its child 32 which is replaced by its child 72).
<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
<constructors>
}
public class IntTree {
private IntTreeNode overallRoot;
<methods>
}
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
allowed to change the data fields of the existing nodes in the tree, and you
are not allowed to construct new nodes or additional data structures.
9. Linked Lists, 20 points. Write a method reorder3 that reorders each
successive sequence of 3 values in a list of integers by switching the order
of the first two values. For example, suppose that a variable called list
stores the following sequence of values:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
and we make the following call:
list.reorder3();
Afterwards the list should store the following sequence of values:
[2, 1, 3, 5, 4, 6, 8, 7, 9, 11, 10, 12, 14, 13, 15]
In the first sequence of 3 values (1, 2, 3), the first two have been
switched to produce (2, 1, 3). In the second sequence of 3 values (4, 5,
6), the first two have been switched to produce (5, 4, 6). And so on. If
the final sequence has just two values, they should still be switched. For
example, if the list had instead stored:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
The result would have been:
[2, 1, 3, 5, 4, 6, 8, 7, 9, 11, 10, 12, 14, 13, 15, 17, 16]
Notice that the values (16, 17) have been switched even though there is no
third value. If the final sequence has just one value, then it is not
changed.
These examples purposely used sequential integers to make the rearrangement
clear, but you should not expect that the list will store sequential
integers. For example, the following list:
[3, 8, 19, 42, 7, 26, 19, -8, 193, 204, 6, -4, 99]
would be rearranged as follows:
[8, 3, 19, 7, 42, 26, -8, 19, 193, 6, 204, -4, 99]
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.
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 reorder3 on the next page.
Write your solution to reorder3 below.
10. Art, 1 point (bonus). Give an artistic rendering of your TA. 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