<![CDATA[
CSE143 Final
Spring 2011
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
The exam is divided into ten questions with the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Binary Tree Traversal 6 _____
2 Binary Search Tree 4 _____
3 Collections Mystery 5 _____
4 Collections Programming 5 _____
5 Binary Trees 10 _____
6 Collections Programming 10 _____
7 Comparable class 20 _____
8 Binary Trees 20 _____
9 Linked Lists 20 _____
10 Art (bonus) 1 _____
----------------------------------
Total 100 _____
This is a closed-book/closed-note exam. You are allowed to have one
hand-written index card up to 5" x 8". Space is provided for your answers.
Use the backs of the pages of this test if necessary. The last two pages
include the "cheat sheet" and can be used as scratch paper. You are not
allowed to access any other paper during the exam (not even scratch paper).
Anyone caught with extra paper will lose at least 10 points.
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. Anyone caught using an electronic device will receive a
10 point penalty.
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.
+---+
| 3 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 1 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 4 | | 5 | | 6 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 7 | | 0 | | 9 | | 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: Lee, Britt, Chris, Vin, Bernardo,
Harry, Chico.
3. Collections Mystery, 5 points. Consider the following method:
public Map<String, String> mystery(List<String> list1,
List<String> list2) {
Map<String, String> result = new TreeMap<String, String>();
for (int i = 0; i < list1.size(); i++) {
result.put(list1.get(i), list2.get(i));
result.put(list2.get(i), list1.get(i));
}
return result;
}
The three entries below have specific values for the first and second
parameters to method mystery (when you see text like the letter b, that
indicates that the list stores the String "b" in that position). For each
entry, indicate what values would be stored in the map returned by method
mystery if the given lists are passed as parameters. Map elements should be
listed with "key=value" elements, as in {b=z, d=e}. You should list the map
entries in their proper order.
list1: [b, l, u, e]
list2: [s, p, o, t]
map returned:__________________________________________________________
list1: [k, e, e, p]
list2: [s, a, f, e]
map returned:__________________________________________________________
list1: [s, o, b, e, r]
list2: [b, o, o, k, s]
map returned:__________________________________________________________
4. Collections Programming, 5 points. Write a method called removeEvenLength
that takes a Set of strings as a parameter and that removes all of the
strings of even length from the set. For example, if a set called s stores
the following values:
[I, Sam, am, and, do, eggs, green, ham, like, not, them]
and the following call is made:
removeEvenLength(s);
then s should store the following values after the call:
[I, Sam, and, green, ham, not]
You may construct iterator objects, but you are not allowed to construct any
structured objects to solve the problem (no set, list, stack, queue, string,
etc).
5. Binary Trees, 10 points. Write a method called printLeaves that prints
the leaves of a binary tree from right to left. More specifically, the
leaves should be printed in the reverse order that they would be printed
using any of the standard traversals. For example, if t stores this tree:
+---+
| 2 |
+---+
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ / \
+---+ +---+ +---+
| 4 | | 5 | | 9 |
+---+ +---+ +---+
then the call:
t.printLeaves();
should produce the following output:
leaves: 9 5 4 0
You must exactly reproduce the format above for a nonempty tree. If the
tree is empty, your method should produce the output "no leaves". Your
method should always produce exactly one line of output. In other words,
if it is called n times, it should produce n lines of output.
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.
6. Collections Programming, 10 points. Write a method called split that
takes a set of strings as a parameter and that returns the result of
splitting the strings into different sets based on the length of the
strings. In particular, your method should return a map whose keys are
integers and whose values are sets of strings of that length. For example,
if a variable called words contains the following set of strings:
[to, be, or, not, that, is, the, question]
then the call split(words) should return a map whose values are sets of
strings of equal length and whose keys are the string lengths:
{2=[be, is, or, to], 3=[not, the], 4=[that], 8=[question]}
Notice that strings of length 2 like "be" and "is" appear in a set whose key
is 2. If the set had instead stored these strings:
[four, score, and, seven, years, ago, our, fathers, brought, forth]
Then the method would return this map:
{3=[ago, and, our], 4=[four], 5=[forth, score, seven, years],
7=[brought, fathers]}
The set of strings passed to your method will not necessarily be in order,
but the map returned by your method should be ordered numerically by key and
each set contained in the map should be ordered alphabetically, as in the
examples above.
Your method should construct the new map and each of the sets contained in
the map but should otherwise not construct any new data structures. It
should also not modify the set of words passed as a parameter.
7. 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.
8. 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.
9. Linked Lists, 20 points. Write a method called shift that rearranges the
elements of a list of integers by moving to the end of the list all values
that are in even-numbered positions and otherwise preserving list order.
For example, if you have a variable called list that stores the following:
[0, 1, 2, 3, 4, 5, 6, 7]
then the call:
list.shift();
should rearrange the list to be:
[1, 3, 5, 7, 0, 2, 4, 6]
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:
[17, 3, 2, 5, 4, 29, 8, 28, 7]
Notice that it doesn't matter whether the value itself is odd or even.
What matters is whether the value appears in an even index (index 0, 2, 4,
etc). Also notice that the original order of the list is otherwise
preserved.
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 define private helper methods to solve this problem, but otherwise
you may not assume that any particular methods are available. You are
allowed to define your own variables of type ListNode, but 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 on the next page.
Write your solution to shift below.
10. 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