<![CDATA[
CSE143X Sample Final, Autumn 2023 handout #23
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 4 | | 7 |
+---+ +---+
/ \
/ \
+---+ +---+
| 9 | | 6 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 2 | | 1 | | 5 |
+---+ +---+ +---+
/ \
/ \
+---+ +---+
| 8 | | 3 |
+---+ +---+
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: Moira, Stevie, Alexis, Ted,
Roland, Johnny, David. 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, int n) {
Set<Integer> result = new TreeSet<>();
for (int j = 0; j < data[n].length; j++) {
result.add(data[n][j]);
}
for (int i = 0; i < data.length; i++) {
result.remove(data[i][n]);
}
return result;
}
Suppose that a variable called grid has been declared as follows:
int[][] grid = {{5, 2, 2, 2, 4, 2}, {6, 2, 4, 3, 5, 9},
{5, 2, 1, 2, 9, 8}, {5, 3, 4, 2, 6, 4}};
which means it will store the following 4-by-6 grid of values:
5 2 2 2 4 2
6 2 4 3 5 9
5 2 1 2 9 8
5 3 4 2 6 4
For each call below, indicate what value is returned. If the method call
results in an exception being thrown, write "exception" instead. Recall
that the remove method does nothing if a set does not contain a given value.
Method Call Contents of Set Returned
mystery(grid, 0) _________________________________
mystery(grid, 1) _________________________________
mystery(grid, 3) _________________________________
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) although you can
construct iterators. Your method should not change the second set passed
as a parameter.
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 these two lines of 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 (trailing spaces are okay). 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 pointMap that
takes a list of points as a parameter and that returns a map that
associates each point from the list with a list of indexes at which that
point occurs. For example, if a variable called list stores the following:
[[x=1,y=3], [x=7,y=7], [x=1,y=3], [x=7,y=8], [x=1,y=3], [x=1,y=3],
[x=7,y=7], [x=7,y=8], [x=4,y=2], [x=7,y=8], [x=7,y=8], [x=4,y=2],
[x=1,y=3], [x=4,y=2]]
then the call pointMap(list) should return the following map:
{[x=4,y=2]=[8, 11, 13], [x=1,y=3]=[0, 2, 4, 5, 12], [x=7,y=7]=[1, 6],
[x=7,y=8]=[3, 7, 9, 10]}
Notice that each point from the original list maps to a list of indexes.
For example, the point [x=1,y=3] appeared at indexes 0, 2, 4, 5, and 12,
so it maps to a list with those values. The lists that each point 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
other structured objects (no string, set, list, etc.). It should also not
modify the list of points passed as a parameter and it should be reasonably
efficient.
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.
8. Binary Trees, 20 points. Write a method called add that takes as a
parameter a reference to a second binary tree and that adds the values in
the second tree to this tree. If the method is called as follows:
tree1.add(tree2);
it should add all values in tree2 to the corresponding nodes in tree1. In
other words, the value stored at the root of tree2 should be added to the
value stored at the root of tree1 and the values in tree2's left and right
subtrees should be added to the corresponding positions in tree1's left and
right subtrees. The values in tree2 should not be changed by your method.
Below is an example of what should happen given the call above.
initial tree1 initial tree2 final tree1
+---+ +---+ +---+
| 1 | | 2 | | 3 |
+---+ +---+ +---+
/ \ / \ / \
+---+ +---+ +---+ +---+ +---+ +---+
| 4 | | 7 | | 3 | | 1 | | 7 | | 8 |
+---+ +---+ +---+ +---+ +---+ +---+
Notice that after the call the root node of tree1 stores 3 as its data (the
sum of 1 and 2 from the initial trees), its left child stores 7 (the sum of
4 and 3 from the initial trees) and its right child stores 8 (the sum of 7
and 1 from the initial trees).
If tree1 has a node that has no corresponding node in tree2, then that node
is unchanged. For example, if tree2 is empty, tree1 is not changed at all.
It is also possible that tree2 will have one or more nodes that have no
corresponding node in tree1. For each such node, create a new node in tree1
in the corresponding position with the value stored in tree2's node. For
example:
initial tree1 initial tree2 final tree1
+---+ +---+ +---+
| 6 | | 1 | | 7 |
+---+ +---+ +---+
/ / \ / \
+---+ +---+ +---+ +---+ +---+
| 2 | | 4 | | 5 | | 6 | | 5 |
+---+ +---+ +---+ +---+ +---+
/ \ / \
+---+ +---+ +---+ +---+
| 8 | | 2 | | 8 | | 2 |
+---+ +---+ +---+ +---+
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
replace any of the existing nodes in the tree although you will update the
data stored in the existing nodes. You will also construct new nodes to be
inserted into the tree as described above (notice the 3-argument IntTreeNode
constructor that can be used to do so). 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 of the LinkedIntList class called
switchPairsOfPairs that rearranges each successive sequence of 4 values by
switching the order of the two pairs that make up the sequence. Suppose,
for example, that a variable called list stores the following values:
[1, 2, 3, 4, 5, 6, 7, 8]
| | | | | | | |
+--+ +--+ +--+ +--+
pair pair pair pair
As indicated, this list has four pairs. If the following call is made:
list.switchPairsOfPairs();
the following sequence would be produced:
[3, 4, 1, 2, 7, 8, 5, 6]
| | | | | | | |
+--+ +--+ +--+ +--+
pair pair pair pair
Notice that the pair (1, 2) has been switched with the pair (3, 4) and that
the pair (5, 6) has been switched with the pair (7, 8).
This example purposely used sequential integers to make the rearrangement
clear, but you should not expect that the list will store sequential
integers. It also might have extra values at the end that are not part of a
group of four. Such values should not be moved. For example, if the list
had stored this sequence of values:
[3, 8, 19, 42, 7, 26, 19, -8, 193, 204, 6, -4, 99, 2]
then a call on the method would have produced this sequence:
[19, 42, 3, 8, 19, -8, 7, 26, 6, -4, 193, 204, 99, 2]
Notice that the values 99 and 2 that appear at the end have not been moved
because they are not part of a complete group of four values.
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>
}
Your method 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.
]]>