<![CDATA[
CSE143 Final
Spring 2007
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 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.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 9 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 1 | | 2 | | 4 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 5 | | 8 | | 7 | | 6 |
+---+ +---+ +---+ +---+
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: Ephraim, Ben, Dan, Frank, Caleb,
Gideon, Adam. Assume the search tree uses alphabetical ordering to compare
words.
3. Binary Trees, 10 points. Write a toString method for a binary tree of
integers. The method should return "empty" for an empty tree. For a leaf
node, it should return the data in the node as a String. For a branch node,
it should return a parenthesized String that has three elements separated by
commas: the data at the root followed by a String representation of the left
subtree followed by a String representation of the right subtree. For
example, if a variable t stores a reference to the following tree:
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ \
/ \
+---+ +---+
| 4 | | 9 |
+---+ +---+
then the call t.toString() should return the following String:
"(2, (8, 0, empty), (1, (7, 4, empty), (6, empty, 9)))"
The quotes above are used to indicate that this is a String but should not
be included in the String that you return.
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.
Write your solution to toString below.
4. Programming with inheritance, 20 points. You have been asked to extend a
Java class called GroceryBill that is used to keep track of a list of items
being purchased at a grocery store. The GroceryBill class has the following
public methods:
public GroceryBill(ClerkInfo info) constructs a GroceryBill object for
the given clerk
public void add(Item i) adds the given item to this bill
public double getTotal() returns the total cost of these items
public void printReceipt() prints a list of items
This class works correctly, but doesn't allow for customer discounts. You
are to define a new class called DiscountBill that extends this class
through inheritance so that it can be used to track discounts on various
items for preferred customers. The Item class includes the following public
methods:
public double getPrice() returns the price for this item
public double getDiscount() returns the discount for this item
The discount indicates how much is subtracted from the price for this item.
For example, a candy bar might cost 1.35 with a discount of 0.25 for
preferred customers, meaning that preferred customers get it for 1.10.
The DiscountBill class has a slightly different constructor that includes
information about whether or not a customer is a preferred customer who
should get the discount (true if yes, false otherwise):
public DiscountBill(ClerkInfo info, boolean preferred)
Your class is to keep track of information about discounted items for
preferred customers and it should adjust the amount reported by getTotal for
preferred customers. For example, if the total would have been $80 but a
preferred customer is getting $20 in discounts, then getTotal should report
the total as $60 for that customer. Some items will have no discount (a
discount of 0.0). Your class should keep track of how many items a customer
is getting a non-zero discount for and what this discount adds up to, both
as a total amount and as a percentage of what the bill would have been
otherwise. Your class should include several extra methods that allow a
client to ask about the discount (if any):
public int getDiscountCount() returns the number of items that were
discounted (if any)
public double getDiscountAmount() returns the total discount for this
list of items (if any)
public double getDiscountPercent() returns the percent of the total
discount as a percent of what the
total would have been otherwise
These methods should return 0 if the customer is not a preferred customer or
if none of the items was discounted. Notice that the percent is reported as
a percent of what the bill would have been otherwise. For example, if a
bill would have been $80.00 but has a $20.00 discount, then the discount
percent should be reported as 25% because $20 is 25% of $80.
Space is provided on the next page for your answer.
Write your solution to DiscountBill below.
5. Comparable class, 20 points. Define a class Rectangle that stores
information about a rectangle. Each Rectangle object keeps track of its
location and size and has the following public methods:
Rectangle(x, y, width, height) constructs a rectangle with upper-left
coordinates (x, y) and given width/height
getX() returns x-coordinate of upper left
getY() returns y-coordinate of upper left
getWidth() returns width of rectangle
getHeight() returns height of rectangle
getArea() returns the area of the rectangle
toString() returns a String representation of the
rectangle
Assume that we are using integer coordinates, which means that all values
passed to these methods and returned by these methods should be of type int.
The Rectangle constructor should throw an IllegalArgumentException if passed
negative values for width or height, although x and y can be negative.
The toString method should return a String with the following general form
(filling in appropriate values for x, y, width and height):
"rectangle at (<x>, <y>) of size (<width>, <height>)"
For example, given the following declaration:
Rectangle r = new Rectangle(3, 8, 12, 10);
The call r.toString() should return "rectangle at (3, 8) of size (12, 10)".
Recall that the area of a rectangle is the product of its width and height.
Your class should implement the Comparable<E> interface. Rectangles of
smaller area should be considered "less" than rectangles of larger area. If
two rectangles have the same area, then the rectangle closer to the origin
of (0, 0) should be considered to be "less." Recall that distance to the
origin is computed by finding the square root of the sum of the squares of
the x and y coordinates. You may call Math.sqrt to compute a square root.
Write your solution to Rectangle below.
6. Binary Trees, 20 points. Write a method construct that takes an integer n
as a parameter and that constructs a new tree of integers with n nodes. The
nodes should be numbered 0 through (n - 1) such that an inorder traversal of
the tree will produce the values in sequential order. The tree should be
balanced in that the number of values in any node's left subtree should
always be within one of the number of values in its right subtree. If there
is an extra value in one of a node's two subtrees, it should appear in the
right subtree. For example, given a variable t of type IntTree, the
following call:
t.construct(7);
should produce the following tree:
+----+
| 3 |
+----+
/ \
/ \
+----+ +----+
| 1 | | 5 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 0 | | 2 | | 4 | | 6 |
+----+ +----+ +----+ +----+
If the call had been:
t.construct(10);
the following tree should be produced:
+----+
| 4 |
+----+
/ \
/ \
+----+ +----+
| 1 | | 7 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 0 | | 2 | | 5 | | 8 |
+----+ +----+ +----+ +----+
\ \ \
\ \ \
+----+ +----+ +----+
| 3 | | 6 | | 9 |
+----+ +----+ +----+
Your method should replace any existing tree. If should construct an empty
tree if passed a value of 0 and should generate an IllegalArgumentException
if passed a negative value.
<continued on next page>
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
// post: constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}
// post: constructs a branch node 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 call any other methods of the class. You will need to construct new
nodes, but you may not use any auxiliary data structure to solve this
problem (no array, ArrayList, stack, queue, String, etc).
Write your solution to construct below.
7. Linked Lists, 20 points. Write a method shift that rearranges the elements
of a list of integers by moving to the end of the list all values that are
in odd-numbered positions and otherwise preserving list order. For example,
if you have a variable called list that stores the following values:
[0, 1, 2, 3, 4, 5, 6, 7]
then the call:
list.shift();
should rearrange the list to be:
[0, 2, 4, 6, 1, 3, 5, 7]
In this example the values in the original list were equal to their
positions and there were an even number of elements, but that won't
necessarily be the case. For example, if the list had instead stored:
[4, 17, 29, 3, 8, 2, 28, 5, 7]
then after a call on shift it would store:
[4, 29, 8, 28, 7, 17, 3, 2, 5]
Notice that it doesn't matter whether the value itself is odd or even. What
matters is whether the value appears in an odd index (index 1, 3, 5, etc).
Also notice that the original order of the list is otherwise preserved.
Assume that you are using a linked list that stores integers, as discussed
in lecture (handout 9).
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 shift 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