<![CDATA[
CSE143 Final
Fall 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. Space is provided for your answers.
There is a 2-page "cheat sheet" at the end that you can use as scratch paper or
to write answers. You are not allowed to access any other paper during the
exam (not even scratch paper). Use the backs of the pages of this test if
necessary. 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.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 4 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 2 | | 1 | | 7 |
+---+ +---+ +---+
\ / \ \
\ / \ \
+---+ +---+ +---+ +---+
| 9 | | 6 | | 5 | | 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: Leonard, Penny, Sheldon, Howard,
Raj, Amy, Bernadette.
3. Collections Mystery, 5 points. Consider the following method:
public Map<String, String> mystery(Map<String, Integer> map1,
Map<Integer, String> map2) {
Map<String, String> result = new TreeMap<String, String>();
for (String s1 : map1.keySet()) {
if (map2.containsKey(map1.get(s1))) {
result.put(s1, map2.get(map1.get(s1)));
}
}
return result;
}
The three entries below have specific values for the first and second
parameter to method mystery. For each entry, indicate what values would be
stored in the map returned by method mystery if the given maps are passed as
parameters. Map elements should be listed with "key=value" elements, as in
{3=8, 7=9}. You should list the map entries in their proper order.
map1: {bar=1, baz=2, foo=3, mumble=4}
map2: {1=earth, 2=wind, 3=air, 4=fire}
map returned:__________________________________________________________
map1: {five=105, four=104, one=101, six=106, three=103, two=102}
map2: {99=uno, 101=dos, 103=tres, 105=quatro}
map returned:__________________________________________________________
map1: {a=42, b=9, c=7, d=15, e=11, f=24, g=7}
map2: {1=four, 3=score, 5=and, 7=seven, 9=years, 11=ago}
map returned:__________________________________________________________
4. Collections Programming, 5 points. Write a method called extractEqual that
takes a set of Point objects and that returns a new set that contains all of
the Point objects where the x and y values are equal to each other. For
example, if a set called points contains the following values:
[[x=42,y=3], [x=4,y=2], [x=18,y=1], [x=7,y=8], [x=-2,y=-2], [x=3,y=3],
[x=7,y=7], [x=0,y=82], [x=14,y=14], [x=3,y=13], [x=-3,y=4], [x=1,y=3]]
then the call extractEqual(points) should return the following set:
[[x=-2,y=-2], [x=3,y=3], [x=7,y=7], [x=14,y=14]]
The original set should be unchanged and you should not construct any new
Point objects in solving this problem. As a result, both sets will end up
referring to the Point objects in which the x and y coordinates are equal.
Your method is expected to have reasonable efficiency in that it shouldn't
lead to more set operations than it needs to.
5. Binary Trees, 10 points. Write a method called printLevel that takes an
integer n as a parameter and that prints the values at level n from left to
right. The values should be printed one per line. By definition, the
overall root is at level 1, it's children are at level 2, and so on. For
example, if a variable t stores a reference to the following tree:
+----+
| 12 |
+----+
/ \
+----+ +----+
| 19 | | 93 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| 11 | | 14 | | 15 |
+----+ +----+ +----+
then the call:
t.printLevel(3);
would produce the output:
11
14
15
If there are no values at the level, your method should produce no output.
Your method should throw an IllegalArgumentException if passed a value for
level that is less than 1.
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 call any other methods of the class. You may not define any
auxiliary data structures to solve this problem.
6. Collections Programming, 10 points. Write a method called indexMap that
takes a list of strings as a parameter and that returns a map that
associates each string from the list to a list of indexes at which that
string occurs. For example, if a variable called list stores the following:
[to, be, or, not, to, be]
then the call indexMap(list) should return the following map:
{be=[1, 5], not=[3], or=[2], to=[0, 4]}
Notice that each string from the original list maps to a list of indexes.
For example, the string "to" appeared at index 0 and 4 in the original list,
so it maps to a list with the values 0 and 4. The map returned by your
method should be ordered alphabetically and the lists that each string maps
to should have indexes in increasing order, as in the example.
Your method should construct the new map and each of the lists contained in
the map and can construct iterators but should otherwise not construct any
new data structures. It should also not modify the list of words passed as
a parameter and it should be reasonably efficient.
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
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 to determine the ordering. 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.
Write your solution to BookData on the next page.
Write your solution to BookData below.
8. Binary Trees, 20 points. Write a method called limitLeaves that takes an
integer n as a parameter and that removes nodes from a tree to guarantee
that all leaf nodes store values that are greater than n. For example,
suppose a variable t stores a reference to the following tree:
+----+
| 13 |
+----+
/ \
+----+ +----+
| 18 | | 10 |
+----+ +----+
/ / \
+----+ +----+ +----+
| 82 | | 17 | | 23 |
+----+ +----+ +----+
/ \ \ \
+----+ +----+ +----+ +----+
| 92 | | 8 | | 12 | | 20 |
+----+ +----+ +----+ +----+
And we make the following call:
t.limitLeaves(20);
Then your method must guarantee that all leaf node values are greater than
20. So it must remove the leaves that store 8, 12, and 20. But notice that
this creates a new leaf that stores 17 when its child is removed. This new
leaf must also be removed. Thus, we end up with this tree:
+----+
| 13 |
+----+
/ \
+----+ +----+
| 18 | | 10 |
+----+ +----+
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/
+----+
| 92 |
+----+
Notice that the nodes storing 13, 18, and 10 remain even though those values
are not greater than 20 because they are branch nodes. Also notice that you
might be required to remove nodes at many levels. For example, if the node
storing 23 instead had stored the value 14, then we would have removed it as
well, which would have led us to remove the node storing 10.
Your method should remove the minimum number of nodes that satisfies the
constraint that all leaf nodes store values greater than the given n.
<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 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
allowed to change the data fields of the existing nodes in the tree, and you
are not allowed to construct new nodes or additional data structures.
9. Linked Lists, 20 points. Write a method called bubble that performs one
pass of the bubble sort algorithm on a list of integers, returning true if
any changes were made and returning false otherwise. As Wikipedia
describes, bubble sort "works by repeatedly stepping through the list to be
sorted, comparing each pair of adjacent items and swapping them if they are
in the wrong order. The pass through the list is repeated until no swaps
are needed, which indicates that the list is sorted."
For example, suppose that a variable called list stores the following:
[5, 1, 4, 2, 8]
There are four pairs of adjacent values to compare, which leads to the
following changes:
Starting list New list explanation
-------------------------------------------------------
[5, 1, 4, 2, 8] [1, 5, 4, 2, 8] 1st pair is swapped
[1, 5, 4, 2, 8] [1, 4, 5, 2, 8] 2nd pair is swapped
[1, 4, 5, 2, 8] [1, 4, 2, 5, 8] 3rd pair is swapped
[1, 4, 2, 5, 8] [1, 4, 2, 5, 8] no change
All of these changes should be made in the first pass (i.e., on a single
call to bubble). Notice that the list is not sorted because this represents
just one pass of the algorithm. A second pass would swap the pair (4, 2),
which would leave the list in sorted order. A third pass would not swap any
values.
Remember that your method is performing just one pass, but it should return
true if it swapped something and should return false if no swaps were
performed. Thus, a client can use your method to sort a list by saying:
boolean sorted = false;
while (!sorted) {
System.out.println(list);
sorted = !list.bubble();
}
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 bubble on the next page.
Write your solution to bubble 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