<![CDATA[
CSE143 Final
Autumn 2014
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 Fiction (bonus) 1 _____
----------------------------------
Total 100 _____
This is a closed-book/closed-note exam. Space is provided for your answers.
There is a "cheat sheet" at the end that you can use as scratch paper or to
write answers. You can also request scratch paper from a TA. You are not
allowed to access any of your own papers during the exam.
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, to declare variables and
parameters using interfaces when possible, and to avoid the use of break
statements and return from a void method. 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). Do not use Java 8 constructs.
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 | | 9 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 1 | | 2 | | 4 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 5 | | 8 | | 7 | | 6 |
+---+ +---+ +---+ +---+
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: Ephraim, Ben, Dan, Frank, Caleb,
Gideon, Adam. Assume the search tree uses alphabetical ordering to compare
words.
3. Collections Mystery, 5 points. Consider the following method:
public int mystery(int[][] data, int pos) {
int sum = 0;
for (int i = 0; i < data.length - pos; i++) {
sum += data[i][i + pos];
}
return sum;
}
Suppose that a variable called grid has been declared as follows:
int[][] grid = {{2, 2, 6, 7, 7, 5}, {6, 3, 4, 7, 9, 3},
{7, 6, 1, 2, 3, 6}, {9, 3, 6, 6, 9, 4},
{3, 1, 8, 8, 2, 7}, {5, 7, 9, 2, 1, 6}};
which means it will store the following 6-by-6 grid of values:
2 2 6 7 7 5
6 3 4 7 9 3
7 6 1 2 3 6
9 3 6 6 9 4
3 1 8 8 2 7
5 7 9 2 1 6
For each call below, indicate what value is returned. If the method call
results in an exception being thrown, write "exception" instead.
Method Call Value Returned
mystery(grid, 5) ____________________
mystery(grid, 3) ____________________
mystery(grid, 1) ____________________
4. Collections Programming, 5 points. Write a method called acronymFor that
takes a list of strings as a parameter and that returns the corresponding
acronym. You form an acronym by combining the capitalized first letter of a
series of words. For example, the list [laughing, out, loud] produces the
acronym "LOL". The list [Computer, Science and, Engineering] produces the
acronym "CSE". You may assume that all of the strings are nonempty. Your
method is not allowed to change the list passed to it as a parameter. If
passed an empty list, your method should return the empty string.
You may construct iterators and strings, but you are not allowed to
construct other structured objects (no set, list, stack, queue, etc.).
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. 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 this tree:
+----+
| 12 |
+----+
/ \
+----+ +----+
| 19 | | 93 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| 11 | | 14 | | 15 |
+----+ +----+ +----+
then the call:
t.printLevel(3);
t.printLevel(5);
would produce the output:
nodes at level 3 = 11 14 15
nodes at level 5 =
Notice that if there are no values at the level (e.g., level 5), your
method should produce no output after the equals sign. You must exactly
reproduce the format of this 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 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 acronyms that
takes a set of word lists as a parameter and that returns a map whose keys
are acronyms and whose values are the word lists that produce that acronym.
Acronyms are formed from each list as described in problem 4. Recall that
the list [laughing, out, loud] produces the acronym "LOL". The list
[League, of, Legends] also produces the acronym "LOL". Suppose that a
variable called lists stores this set of word lists:
[[attention, deficit], [Star, Trek, Next, Generation],
[laughing, out, loud], [International, Business, Machines],
[League, of, Legends], [anno, domini], [art, director],
[Computer, Science and, Engineering]]
Each element of this set is a list of values of type String. You may assume
that each list is nonempty and that each string in a list is nonempty.
Your method should construct a map whose keys are acronyms and whose values
are sets of the word lists that produce that acronym. For example, the call
acronyms(lists) should produce the following map:
{AD=[[attention, deficit], [anno, domini], [art, director]],
CSE=[[Computer, Science and, Engineering]],
IBM=[[International, Business, Machines]],
LOL=[[laughing, out, loud], [League, of, Legends]],
STNG=[[Star, Trek, Next, Generation]]}
Notice that there are 5 unique acronyms produced by the 8 lists in the set.
Each acronym maps to a set of the word lists for that acronym. Your method
should not make copies of the word lists; the sets it constructs should
store references to those lists. As in the example above, the keys of the
map that you construct should be in sorted order. You may assume that a
working version of acronymFor as described in problem 4 is available for you
to use no matter what you wrote for problem 4. Your method is not allowed
to change either the set passed as a parameter or the lists within the set.
7. Comparable class, 20 points. Define a class called 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)
In this string the rating should be truncated to a single digit after the
decimal point (truncated, not rounded). 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 (what we
called "morphing" in assignments 7 and 8), 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 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) {
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. Fiction, 1 point (bonus). Your TA has woken up in jail. Explain why. You
may express your answer in any way you choose by writing a story, drawing a
picture, writing a poem, etc. 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