<![CDATA[
CSE143 Final
Spring 2009
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 Comparable class 20 _____
5 Programming with Inheritance 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.
+---+
| 4 |
+---+
/ \
/ \
+---+ +---+
| 5 | | 6 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 2 | | 3 | | 0 | | 1 |
+---+ +---+ +---+ +---+
\ \ /
\ \ /
+---+ +---+ +---+
| 9 | | 7 | | 8 |
+---+ +---+ +---+
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: Karl, Chris, Simon, John, Zoe,
Anton, Zach. Assume the search tree uses alphabetical ordering to compare
words.
3. Binary Trees, 10 points. Write a method called oddDepthSum that returns
the sum of the values of a binary tree of integers that occur at nodes with
odd depth. More specifically, the overall root is considered to have a
depth of 1, so it has an odd depth. It's children have a depth of 2, so
they have even depth. The overall root's grandchildren have a depth of 3,
so they have odd depth. And so on. For example, if the variable t refers
to the following tree:
+---+
| 5 |
+---+
/ \
/ \
+---+ +---+
| 1 | | 3 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 2 | | 4 | | 8 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 0 | | 9 | | 6 | | 7 |
+---+ +---+ +---+ +---+
Then the nodes with odd depth are those storing 5, 2, 4, and 8. So the call
t.oddDepthSum() would return 19. If the tree is empty, the method should
return 0.
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. Comparable class, 20 points. Define a class TeamData that keeps track of
information for a team of students competing in a programming contest. The
class has the following public methods:
TeamData(name, problems) constructs a TeamData object with the given
team name and the given number of problems
success(problem, time) record the successful completion of the
given problem with the given time
solved() returns the total number of problems solved
time() returns the total time for problems solved
percentCorrect() returns the percent of problems solved
toString() returns a String with name, problems
solved, total problems, and total time
Each time a team solves a problem, the success method for the team will be
called once giving the problem number and the time for that problem. The
TeamData object must keep track of the total number of problems solved and
the sum of all of the times. It does NOT have to keep track of which
problems have been solved. Below is an example of a typical usage:
TeamData team1 = new TeamData("UW Red", 8);
team1.success(3, 18);
team1.success(4, 82);
team1.success(6, 130);
System.out.println(team1);
The println should produce the following output:
UW Red solved 3 of 8 in 230 minutes
Your toString method must exactly reproduce this format. After this
interaction, the call team1.solved() would return 3, the call team1.time()
would return 230, and the call team1.percentCorrect() would return 37.5.
The TeamData class should implement the Comparable<E> interface. Teams that
perform better should be considered to be "less" than other teams so that
they appear at the beginning of a sorted list. In general, the team that
solves the most problems is considered the best, but when there is a tie for
the number of problems solved, then total time determines the winner. The
team with the lower total time wins in the case of a tie for total problems
solved.
You may assume that all values passed to your methods are valid and that the
total number of problems is greater than 0.
Write your solution to TeamData on the next page.
Write your solution to TeamData below.
5. Programming with inheritance, 20 points. You are to extend the TeamData
class described in problem 4. The TeamData class only keeps track of total
problems solved and total time. This new version will keep track of more
detailed information about each problem, including how many failed attempts
were made.
You are going to write a class called ExtendedTeamData that extends TeamData
through inheritance to have some extra functionality. It should have a
constructor that takes the same parameters as TeamData and should have
almost the same behavior. It should include two new methods:
fail(problem) record a failed attempt for given problem
detailString() return detailed information about each problem solved
The ExtendedTeamData class will keep track of the number of failed
submissions for each question. If a team successfully completes a problem,
then the time for that problem is adjusted by adding 20 minutes for each
failed attempt. Below is a typical scenario:
ExtendedTeamData team2 = new ExtendedTeamData("UW Blue", 8);
team2.fail(1);
team2.fail(2);
team2.fail(1);
team2.success(2, 40);
team2.fail(1);
team2.success(1, 100);
team2.success(3, 130);
team2.fail(4);
team2.fail(4);
The team successfully completed problem 1 but only after 3 failed attempts.
As a result, the time for problem 1 should be recorded as 160 minutes (100
minutes plus 3 occurrences of the 20-minute penalty). The time for problem
2 should be recorded as 60 minutes (40 plus one 20-minute penalty). The
time for problem 3 would be recorded as 130 minutes because there were no
penalties. Failed attempts only become relevant if a team solves a problem,
so the two failed attempts to solve problem 4 don't affect the total time
for the team. You may assume that all calls on fail for a given problem
happen before the call on success for that problem.
Suppose that after the scenario above, you make these calls:
System.out.println(team2);
System.out.println(team2.detailString());
You should get the following output:
UW Blue solved 3 of 8 in 350 minutes
solved: 1 (100+60) 2 (40+20) 3 (130)
Notice that the total time reported by toString includes the penalties. The
detailString method gives detailed information about each solved problem,
showing the problem number and the time for that problem broken down into
the actual time plus any penalty. Notice that there is no plus inside
parentheses for problem 3 because there was no penalty for that problem.
You must exactly reproduce this format. If a team solves no problems, you
should produce just the string "solved: ". The detailString method does not
provide information about failed attempts for problems that weren't solved
by the team.
The inherited methods of the TeamData class should continue to behave
properly, reporting total time, problems solved, and percent correct.
Write your solution to ExtendedTeamData on the next page.
Write your solution to ExtendedTeamData below.
6. Binary Trees, 20 points. Write a method called stretch that stretches
each node that has only one child in a binary tree of integers. More
specifically, each node that has a single child should be replaced by a new
node storing the data 1 and with the old node as a child in the same
direction as the original node's child. For example, suppose a variable t
stores a reference to the following tree:
+----+
| 13 |
+----+
/ \
/ \
+----+ +----+
| 48 | | 17 |
+----+ +----+
/ \
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/ \
/ \
+----+ +----+
| 65 | | 10 |
+----+ +----+
There are two nodes in this tree that have a single child: the nodes storing
48 and 17. Each of those nodes is replaced in the tree with a new node
storing the value 1 and with the original node as a child in the same
direction as its only child. The node storing 48 has a left child, so it
appears to the left of a new node storing 1. The node 17 has a right child,
so it appears to the right of a new node storing 1. So after the call:
t.stretch();
The tree should look like this:
+----+
| 13 |
+----+
/ \
/ \
+----+ +----+
| 1 | | 1 |
+----+ +----+
/ \
/ \
+----+ +----+
| 48 | | 17 |
+----+ +----+
/ \
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/ \
/ \
+----+ +----+
| 65 | | 10 |
+----+ +----+
This stretching process should be performed on every node in the original
tree that has a single child.
<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
// post: constructs an IntTreeNode 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 assume that any particular methods are available. You are NOT to
change the data field of the existing nodes in the tree. You will, however,
construct new nodes to be inserted into the tree and you will change the
links of the tree to include these new nodes.
7. Linked Lists, 20 points. Write a method called markMultiples that takes an
integer n as a parameter and that adds nodes to a linked list of integers to
indicate where the multiples of n occur. For example, suppose that a
variable list stores the following sequence of values:
[6, 5, 8, 13, 12, 3, 5, 2, 0]
and we make the following call:
list.markMultiples(3);
There are four multiples of 3 in this list (6, 12, 3, and 0). Each should
be marked by inserting a 0 in front of it:
[0, 6, 5, 8, 13, 0, 12, 0, 3, 5, 2, 0, 0]
Notice that even the 0 at the end of the original list has a 0 inserted in
front of it because it is a multiple of 3. Assume that you are using a
linked list that stores integers, as discussed in lecture:
public class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
// post: constructs a node with given data and given link
public ListNode(int data, ListNode next) {
this.data = data;
this.next = next;
}
}
public class LinkedIntList {
private ListNode front;
<methods>
}
You are writing a method that will become part of the LinkedIntList class.
You may not assume that any particular methods are available. You are NOT
to change the data field of the existing nodes in the list. You will,
however, construct new nodes to be inserted into the list and you will
change the links of the list to include these new nodes. Your method should
throw an IllegalArgumentException if the value passed to it is less than 1.
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