<![CDATA[
CSE143 Final
Autumn 2008
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
This is an open-book/open-note exam. Space is provided for your answers. Use
the backs of pages if necessary. The exam is divided into eight questions with
the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Binary Tree Traversal 6 _____
2 Binary Search Tree 4 _____
3 Binary Trees 10 _____
4 Programming with Inheritance 20 _____
5 Comparable class 20 _____
6 Binary Trees 20 _____
7 Linked Lists 20 _____
8 Art (bonus) 1 _____
----------------------------------
Total 100 _____
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.
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.
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 6 | | 7 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 0 | | 1 | | 9 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 5 | | 8 | | 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: Kirk, Spock, Scotty, McCoy,
Uhuru, Chekov, Sulu. Assume the search tree uses alphabetical ordering to
compare words.
3. 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.
4. Programming with inheritance, 20 points. You have been asked to extend a
Java class called DocumentList that is used to store a list of Document
objects. The DocumentList class has a set of methods that is similar to
those we have seen for the built-in ArrayList and LinkedList classes:
public DocumentList(int capacity) constructs an empty document list
of given capacity
public void add(Document d) appends d to end of list
public void add(int index, Document d) inserts d at given index
public void remove(int index) removes document at given index
public int indexOf(Document d) returns index of first occurrence
of d; -1 if not found
public int size() returns # of elements in the list
The class works correctly, but we are interested in analyzing how the list
changes over time. In particular, we are going to collect statistics about
the sequence of states the list goes through as it is modified. The list is
constructed as an empty list and this will be the first state we want to
keep track of. Then, each time that the list is modified, we want to keep
track of that new state. The list is modified each time a client calls
either of the add methods or the remove method. Each modification leads to
a new state even if the list ends up returning to a value it had previously.
For example, the list starts out as an empty list and it might go through a
series of modifications that lead it to be empty a second time, but we would
consider each to be a different state.
You are to define a new class called AnalyzingDocumentList that extends
through inheritance the DocumentList class so that it has the same
functionality described above while also keeping track of information about
the various states that the list goes through. In particular, it should
provide the following additional public methods:
public int totalStates() a count of the total number of states
this list has gone through
public int sizeCount(int size) a count of the number of states this
list has gone through in which its
size was the given size
For example, suppose that an AnalyzingDocumentList called lst is manipulated
in the following ways:
the list is constructed (size is 0)
a document is appended to the end of the list (size now 1)
a document is appended to the end of the list (size now 2)
a document is appended to the end of the list (size now 3)
a document is added at index 1 (size now 4)
the document at index 1 is removed (size now 3)
the document at index 0 is removed (size now 2)
a document is added at index 0 (size now 3)
a document is appended to the end of the list (size now 4)
Then the analyzing methods would return the following values:
lst.totalStates() returns 9 (initial state plus 8 modifications)
lst.sizeCount(0) returns 1 (1 state had size 0)
lst.sizeCount(1) returns 1 (1 state had size 1)
lst.sizeCount(2) returns 2 (2 states had size 2)
lst.sizeCount(3) returns 3 (3 states had size 3)
lst.sizeCount(4) returns 2 (2 states had size 4)
lst.sizeCount(5) returns 0 (no states had size 5)
...
Write your solution to AnalyzingDocumentList on the next page.
Write your solution to AnalyzingDocumentList below.
5. 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.
6. 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>
}
<continued on next page>
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.
7. Linked Lists, 20 points. Write a method reverse3 that reverses each
successive sequence of 3 values in a list of integers. 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.reverse3();
Afterwards the list should store the following sequence of values:
[3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13]
The first sequence of 3 values (1, 2, 3) has been reversed to be (3, 2, 1).
The second sequence of 3 values (4, 5, 6) has been reverse to be (6, 5, 4).
And so on. If the list has extra values that are not part of a sequence of
3, those values are unchanged. 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:
[3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13, 16, 17]
Notice that the values (16, 17) are unchanged in position because they were
not part of a sequence of three values.
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:
[19, 8, 3, 26, 7, 42, 193, -8, 19, -4, 6, 204, 99]
Your method should not change the list if it has fewer than three 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>
}
You are writing a method that will become part of the LinkedIntList class.
You may not call any methods of the class to solve this problem, 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 reverse3 on the next page.
Write your solution to reverse3 below.
8. 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