<![CDATA[
CSE143 Final
Spring 2010
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 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 _____
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.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 5 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 4 | | 2 | | 9 |
+---+ +---+ +---+
/ \ \ /
/ \ \ /
+---+ +---+ +---+ +---+
| 7 | | 6 | | 1 | | 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: Jeff, Britta, Shirley, Abed,
Troy, Pierce, Annie. Assume the search tree uses alphabetical ordering to
compare words.
3. Collections Mystery, 5 points. Consider the following method:
public Set<Integer> mystery(int[][] data) {
Set<Integer> result = new TreeSet<Integer>();
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
result.add(i * 10 + data[i][j]);
}
}
return result;
}
In the left-hand column below are specific two-dimensional arrays. You are
to indicate in the right-hand column what values would be stored in the set
returned by method mystery if the array in the left-hand column is passed as
a parameter to mystery. Set elements should be listed in proper order as a
comma-separated bracketed list, as in [3, 18, 25].
Two-Dimensional Array Contents of Set Returned
------------------------------------------------------------------
[[1, 2], [3, 4]] ______________________________
[[7], [], [8, 8, 9, 10]] ______________________________
[[3, 14], [5, 13, 4], [4, 3, 1]] ______________________________
4. Collections Programming, 5 points. Write a method called retainAll that
takes two sets of integers as parameters and that removes any values in the
first set that are not found in the second set. For example, given sets:
s1: [0, 19, 8, 9, 12, 13, 14, 15]
s2: [0, 19, 2, 4, 5, 9, 10, 11]
If the following call is made:
retainAll(s1, s2);
after the call, the sets would store the following values:
s1: [0, 19, 9]
s2: [0, 19, 2, 4, 5, 9, 10, 11]
You are implementing a two-argument alternative to the standard Set method
called retainAll, so you are not allowed to call that method to solve this
problem. You are also not allowed to construct any structured objects to
solve the problem (no set, list, stack, queue, string, etc). Your method
should not change the second set passed as a parameter.
5. Binary Trees, 10 points. Write a method called hasPathSum that takes an
integer n as a parameter and that returns true if there is some path from
the overall root of a tree to a node of the tree in which the sum of the
data stored in the nodes adds up to n (returning false if no such path
exists). For example if the variable t refers to the following tree:
+----+
| 5 |
+----+
/ \
/ \
+----+ +----+
| 1 | | 21 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| -9 | | 2 | | 20 |
+----+ +----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 3 | | 30 | | 13 | | 4 |
+----+ +----+ +----+ +----+
Below are various calls and an explanation for the value returned:
t.hasPathSum(8) returns true because of the path (5, 1, 2)
t.hasPathSum(26) returns true because of the path (5, 21)
t.hasPathSum(0) returns true because of the path (5, 1, -9, 3)
t.hasPathSum(5) returns true because of the path (5)
t.hasPathSum(1) returns false because no path with that sum exists
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
extra data structures to solve this problem.
6. Collections Programming, 10 points. Write a method called convert that
takes as a parameter a set of strings representing phone numbers and that
returns a map of strings to sets of strings that represent the same phone
numbers split into exchange/suffix. In particular, the phone numbers in the
set passed to the method will each include a 3-digit exchange followed by a
dash followed by a four-digit suffix, as in:
[493-3923, 723-9278, 384-1917, 555-1795, 384-4923, 555-4923, 555-1212,
723-9823]
The method should split each string into the 3-digit exchanges that come
before the dash and the suffixes that come after. The method should
construct a map in which the keys are the 3-digit exchanges. Each such
exchange will be mapped to a set of 4-digit suffixes. For the set of phone
numbers above, the following map would be constructed:
{384=[1917, 4923], 493=[3923], 555=[1212, 1795, 4923], 723=[9278, 9823]}
Notice, for example, that three of the phone numbers in the original set
began with "555". In the map, the key "555" maps to a set of three elements
(the three suffixes that came after "555-").
Your method should construct the new map and each of the sets contained in
the map. Recall that the String class has a substring method that takes a
starting index (inclusive) and a stopping index (exclusive). For example:
"Australia".substring(1, 5) returns "ustr"
The keys of the new map should be ordered by the 3-digit exchanges and each
set should be ordered by the 4-digit suffixes in that set.
7. Comparable class, 20 points. Define a class BookData that keeps track of
information for a book and how it is rated by customers (real numbers
between 0.0 and 5.0). The class has the following public methods:
BookData(title, author) constructs a BookData object with the given
title and author
review(rating) records a review for the book with given rating
getTitle() returns the title of the book
getRating() returns the average of all ratings (0.0 if none)
toString() returns a String with title, author, average
rating, and number of ratings
<continued on next page>
Below is an example for a book that has been reviewed four times:
BookData book = new BookData("1984", "George Orwell");
book.review(4.7);
book.review(5);
book.review(4.9);
book.review(4.9);
After these calls, the call book.getRating() would return 4.875 (the average
of the ratings). The toString method should return a string of the form:
<title>, by <author>, <rating> (<count> reviews)
The rating should be truncated to a single digit after the decimal point.
For example, given the previous calls, book.toString() would produce:
"1984, by George Orwell, 4.8 (4 reviews)"
If a book has been reviewed just once, then toString should include the
grammatically correct text "1 review" rather than "1 reviews".
The BookData class should implement the Comparable<E> interface. Books that
have a higher average rating should be considered "less" than other books so
that they appear at the beginning of a sorted list. You should use the
complete value of the average rating rather than the truncated value
displayed by toString. Books that have the same average rating should be
ordered by the number of reviews, with books that have been reviewed more
often considered "less" than books that have been reviewed less frequently.
8. Binary Trees, 20 points. Write a method called removeLeftLeaves that
removes left leaves from a tree until it has no left leaves remaining. A
left leaf is a leaf that is the left child of some other node. For example,
suppose a variable t stores a reference to the following tree:
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 0 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 4 | | 2 | | 5 | | 9 |
+---+ +---+ +---+ +---+
/ / / / \
/ / / / \
+---+ +---+ +---+ +---+ +---+
| 7 | | 6 | | 1 | | 8 | | 3 |
+---+ +---+ +---+ +---+ +---+
The left leaves of this tree are the nodes that store 7, 6, 1, and 8. If we
make the call:
t.removeLeftLeaves();
then these four nodes will be removed. But notice that once those four
leaves have been removed, we are left with new left leaves storing 4 and 5.
These also are removed, leaving this tree:
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 0 |
+---+ +---+
\ \
\ \
+---+ +---+
| 2 | | 9 |
+---+ +---+
\
\
+---+
| 3 |
+---+
The overall root would never be a left leaf because it has no parent.
<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
<constructors>
}
public class IntTree {
private IntTreeNode overallRoot;
<methods>
}
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
allowed to change the data fields of the existing nodes in the tree, you are
not allowed to construct new nodes or additional data structures, and your
solution must run in O(n) time where n is the number of nodes in the tree.
9. Linked Lists, 20 points. Write a method called compressDuplicates that
replaces each sequence of duplicates in a list of integers with a pair of
values representing a count of the number of duplicates followed by the
number. For example, suppose a variable called list stores the following
sequence of values:
[2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17]
and we make the following call:
list.compressDuplicates();
Then list should store the following values after the call:
[5, 2, 2, -5, 4, 3, 2, 4, 1, 1, 1, 0, 2, 17]
This new list indicates that the original had 5 occurrences of 2 at the
front of the list, followed by 2 occurrences of -5, followed by 4
occurrences of 3, and so on. This process works best when there are many
duplicates in a row. For example, if the list instead had stored:
[10, 20, 10, 20, 10, 20]
Then the resulting list ends up being longer than the original:
[1, 10, 1, 20, 1, 10, 1, 20, 1, 10, 1, 20]
If the list is empty, your method should not change it.
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 fields 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
construct exactly one new node for each sequence of duplicates in the list
and it should run in O(n) time where n is the number of nodes in the list.
Write your solution to compressDuplicates on the next page.
Write your solution to compressDuplicates 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