<![CDATA[
CSE143 Sample Final (Part 2) handout #31
1. Binary Trees, 10 points. Write a method purebredOdds that returns the
number of purebred odd values in a binary tree of integers. A purebred odd
is an odd number all of whose ancestors in the tree are also odd numbers.
For example, suppose that a variable t refers to the following tree:
+----+
| 15 |
+----+
/ \
/ \
+----+ +----+
| 27 | | 34 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 29 | | 75 | | 83 |
+----+ +----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 18 | | 33 | | 46 | | 51 |
+----+ +----+ +----+ +----+
Then the call t.purebredOdds() should return 5 because this tree has a total
of 5 purebred odd values: 15, 27, 29, 75, and 33. The values 83 and 51 are
odd numbers, but not purebred odd numbers because they have an even number
as an ancestor in the tree (the value 34). Notice that if the overall root
is an even number, then the tree will have no purebred odd numbers at all
because every other node has the overall root as an ancestor.
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.
2. 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).
3. Binary Trees, 20 points. Write a method mirror that converts a binary
tree of integers to its mirror image. For example, if a variable called t
stores a reference to a binary tree and you make the following call:
t.mirror();
then the links of the tree should be rearranged so that after the call, t
stores the mirror image of what it stored before the call. Below is a
specific example of how a tree would change:
before | after
+---+ | +---+
| 9 | | | 9 |
+---+ | +---+
/ \ | / \
/ \ | / \
+---+ +---+ | +---+ +---+
| 6 | | 14| | | 14| | 6 |
+---+ +---+ | +---+ +---+
/ \ \ | / / \
/ \ \ | / / \
+---+ +---+ +---+ | +---+ +---+ +---+
| 9 | | 2 | | 11| | | 11| | 2 | | 9 |
+---+ +---+ +---+ | +---+ +---+ +---+
/ \ | / \
/ \ | / \
+---+ +---+ | +---+ +---+
| 4 | | 1 | | | 1 | | 4 |
+---+ +---+ | +---+ +---+
After the call is made, the tree stores the structure that you would see if
you were to hold the original tree's diagram up to a mirror. More
precisely, the overall root (if it exists) remains in the same place in the
mirror image and every other node is moved so that it's new path from the
overall root is composed of the old path from the overall root with left and
right links exchanged. For example, the node that stores 4 in the example
above has the path (left, right, left) in the original tree. In the mirror
image, it has path (right, left, right). The node that stores 1 has the
path (left, right, right) in the original tree. In the mirror image it has
path (right, left, left).
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). You also may not
change any data fields of the nodes. You MUST solve this problem by
rearranging the links of the tree.
]]>