<![CDATA[
CSE143 Final
Winter 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.
+---+
| 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. Binary Trees, 10 points. Write a method evenBranches that returns the
number of branch nodes in a binary tree that contain even numbers. A branch
node is one that has one or two children (i.e., not a leaf). 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.evenBranches() should return 3 because there are three
branch nodes with even values (2, 8 and 6). Notice that the leaf nodes with
even values are not included (the nodes storing 0 and 4).
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 evenBranches below.
4. Programming with inheritance, 20 points. You have been asked to extend a
Java class called Calculator that performs various calculations on
integers. The Calculator class has the following public methods:
public Calculator(int seed) constructs a Calculator with given seed
public boolean isPrime(int n) returns true if n is prime
public int prime(int n) returns the nth prime (n >= 1)
public int fib(int n) returns the nth fibonacci number (n >= 1)
public int rand(int max) returns a random value between 0 and max
The class correctly computes its results, but it does so inefficiently. In
particular, it often computes the same value more than once. You are to
implement a technique known as "memoizing" to speed up the computation of
primes. The idea behind memoizing is to remember values that have been
computed previously. For example, suppose that the value prime(50) is
requested 100 times. There is no reason to compute it 100 different times.
Instead, you can compute it once and store its value, so that the 99 calls
after the first simply return the "memoized" value (the remembered value).
You are to define a new class called MemoCalculator that can be used in
place of a Calculator to speed up the prime computation. A MemoCalculator
object should behave just like a Calculator object except that it should
guarantee that the value of prime(n) is computed only once for any given
value of n. Your class should still rely on the Calculator class to compute
each value for prime(n). It is simply guaranteeing that the computation is
not performed more than once for any particular value of n. The isPrime
method calls the prime method, so it does not need to be memoized. You also
do not need to memoize the fibonacci computation. As indicated above, you
may assume that when prime(n) is called, n is greater than or equal to 1,
although you can't make any assumptions about how large n might be or about
the order in which the method is called with different values of n.
Your method should also provide the following public methods that will allow
a client to find out how many values have been directly computed versus how
many calls have been handled through memoization:
public int getComputeCount() returns number of values actually computed
public int getMemoCount() returns number of calls handled through
memoization
Space is provided on the next page for your answer.
Write your solution to MemoCalculator below.
5. Comparable class, 20 points. Define a class ClockTime that stores
information about time of day using a standard clock. Each ClockTime object
keeps track of hours, minutes, and a String to indicate "am" or "pm". It
has the following public methods:
ClockTime(hours, minutes, amPm) constructs a ClockTime with given
hours, minutes and amPm setting
getHours() returns the hours
getMinutes() returns the minutes
getAmPm() returns the am/pm setting
toString() returns a String representation of
the time
Assume that the values passed to your constructor are legal. In particular,
hours will be between 1 and 12 inclusive, minutes will be between 0 and 59
inclusive, and the am/pm parameter will be either the String "am" or the
String "pm". These values should be returned by the various "get" methods.
The toString method should return a String composed of the hours followed by
a colon followed by the minutes (2 digits) followed by a space followed by
the am/pm String. For example, given these declarations:
ClockTime time1 = new ClockTime(8, 31, "am");
ClockTime time2 = new ClockTime(12, 7, "pm");
time1.toString() should return "8:31 am" and time2.toString() should return
"12:07 pm". You must exactly reproduce the format of these examples.
Your class should implement the Comparable<E> interface. The earliest time
is 12:00 am and the latest time is 11:59 pm. In between the time increases
as it would in a standard clock. Keep in mind that 12:59 am is followed by
1:00 am, that 11:59 am is followed by 12:00 pm, and that 12:59 pm is
followed by 1:00 pm.
Write your solution to ClockTime below.
6. Binary Trees, 20 points. Write a method 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).
Write your solution to limitPathSum below.
7. Linked Lists, 20 points. Write a method takeSmallerFrom that compares two
lists of integers, making sure that the first list has smaller values in
corresponding positions. For example, suppose the the variables list1 and
list2 refer to lists that contain the following values:
list1: (3, 16, 7, 23)
list2: (2, 12, 6, 54)
If the following call is made:
list1.takeSmallerFrom(list2);
the method will compare values in corresponding positions and move the
smaller values to list1. It will find that among the first pair, 2 is
smaller than 3, so it needs to move. In the second pair, 12 is smaller than
16, so it needs to move. In the third pair, 6 is smaller than 7, so it
needs to move. In the fourth pair, 54 is not smaller than 23, so those
values can stay where they are. Thus, after the call, the lists should
store these values:
list1: (2, 12, 6, 23)
list2: (3, 16, 7, 54)
One list might be longer than the other, in which case those values should
stay at the end of their list. For example, for these lists:
list1: (2, 4, 6, 8, 10, 12)
list2: (1, 3, 6, 9)
the call:
list1.takeSmallerFrom(list2);
should leave the lists with these values:
list1: (1, 3, 6, 8, 10, 12)
list2: (2, 4, 6, 9)
Assume that you are using a linked list that stores integers, as discussed
in lecture (handouts 6 and 7).
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 two lists.
Space is provided on the next page for your answer.
Write your solution to takeSmallerFrom 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