<![CDATA[
CSE143 Sample Final, Spring 2021 handout #23
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 6 | | 5 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 3 | | 0 | | 9 |
+---+ +---+ +---+
\ / \ \
\ / \ \
+---+ +---+ +---+ +---+
| 8 | | 2 | | 1 | | 4 |
+---+ +---+ +---+ +---+
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: Java, Rust, Kotlin, Swift,
Python, C, Go. 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 pos, int n) {
Set<Integer> result = new TreeSet<Integer>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result.add(data[i + pos][j + pos]);
}
}
return result;
}
Suppose that a variable called grid has been declared as follows:
int[][] grid = {{3, 1, 7, 1, 7, 2}, {5, 5, 9, 1, 4, 3},
{3, 4, 3, 5, 3, 1}, {2, 5, 3, 6, 8, 8}};
which means it will store the following 4-by-6 grid of values:
3 1 7 1 7 2
5 5 9 1 4 3
3 4 3 5 3 1
2 5 3 6 8 8
For each call below, indicate what value is returned. If the method call
results in an exception being thrown, write "exception" instead.
Method Call Contents of Set Returned
mystery(grid, 3, 1) _________________________________
mystery(grid, 2, 2) _________________________________
mystery(grid, 1, 3) _________________________________
4. Collections Programming, 5 points. Write a method called switchXY that
takes a set of Point objects as a parameter and that removes all points with
x/y coordinates that are equal and that returns a new set composed of the
points with nonequal x/y coordinates switched. For example, suppose that a
set called points stores the following values:
[[x=4,y=8], [x=4,y=4], [x=38,y=4], [x=0,y=0], [x=12,y=2], [x=3,y=3],
[x=5,y=6], [x=-3,y=14], [x=7,y=4]]
then the call switchXY(points) should leave the set points storing:
[[x=4,y=8], [x=38,y=4], [x=12,y=2], [x=5,y=6], [x=-3,y=14], [x=7,y=4]]
and the set returned should store the following values:
[[x=8,y=4], [x=4,y=38], [x=2,y=12], [x=6,y=5], [x=14,y=-3], [x=4,y=7]]
Notice that the three points with equal x/y coordinates have been removed
from the original set and that the set returned contains the remaining
points with their x/y coordinates switched. The values in the returned set
can appear in any order. You may construct iterators, the set to be
returned, and Point objects to add to the new set, but you are not allowed
to construct other structured objects (no string, set, list, etc.).
5. Binary Trees, 10 points. Write a method of the IntTree class called
inorderList that returns a list containing the sequence of values obtained
from an inorder traversal of the tree. For example, if a variable t stores
a reference to the following tree:
+---+
| 7 |
+---+
/ \
+---+ +---+
| 4 | | 2 |
+---+ +---+
/ / \
+---+ +---+ +---+
| 9 | | 5 | | 0 |
+---+ +---+ +---+
then the call t.inorderList() should return the following list:
[9, 4, 7, 5, 2, 0]
Your method should construct an ArrayList to return. If the tree is empty,
your method should return an empty list.
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 other than the ArrayList you are returning.
6. Collections Programming, 10 points. Write a method called recordDate that
records information about a date between two people. For each person, the
map records an ordered list of people that person has dated. For example,
the map might record these entries for two people
Michael => [Ashley, Samantha, Joshua, Brittany, Amanda, Amanda]
Amanda => [Michael, Daniel, Michael]
The dates are listed in reverse order. The list for Michael indicates that
he most recently dated Ashley and before that Samantha and before that
Joshua, and so on. Notice that he has dated Amanda twice. The list for
Amanda indicates that she most recently dated Michael and before that Daniel
and before that Michael. All names are stored as string values.
The method takes three parameters: the map, the name of the first person,
and the name of the second person. It should record the date for each
person and should return what date number this is (1 for a first date, 2 for
a second date, and so on). Given the entries above, if we make this call:
int n = recordDate(dates, "Michael", "Amanda");
The method would record the new date at the front of each list:
Michael => [Amanda, Ashley, Samantha, Joshua, Brittany, Amanda, Amanda]
Amanda => [Michael, Michael, Daniel, Michael]
The method would return the value 3 indicating that this is the third date
for this pair of people. When someone is first added to the map, you
should construct a LinkedList object (we use LinkedList instead of
ArrayList because it has fast insertion at the front of the list).
7. Comparable class, 20 points. Define a class called FoodData that stores
information about a food item. Each FoodData object keeps track of the name
of the food along with its number of grams of fat, carbohydrate, and
protein. For example:
FoodData item1 = new FoodData("sausage biscuit", 31.0, 39.0, 11.0);
FoodData item2 = new FoodData("strawberry sundae", 6.0, 49.0, 6.0);
FoodData item3 = new FoodData("banana", 0.4, 31.1, 1.5);
In calling the constructor, the name is followed by fat grams, followed by
carbohydrate grams, followed by protein grams. For example, the sausage
biscuit above has 31 grams of fat, 39 grams of carbohydrate, and 11 grams
of protein. As in the third example, these values can be real numbers.
Your constructor should throw an IllegalArgumentException if any of the
numeric values passed to it is negative.
This class is being designed for programs that will help people who want to
use a low-fat diet. For example, it is a bit surprising that the McDonalds
sausage biscuit (item1) gets over 58% of its calories from fat while the
McDonalds strawberry sundae (item2) gets only around 19.7% of its calories
from fat. The banana (item3) gets less than 2.7% of its calories from fat.
Your class should have the following public methods:
getName() returns the name of this food item
getCalories() returns total calories for this food item
percentFat() returns the percent of calories from fat for this item
toString() returns a String representation of this item
To compute total calories and percent fat, assume that each gram of fat is 9
calories and that each gram of carbohydrate and protein is 4 calories. For
example, the calories for the strawberry sundae (item2 above) are 274:
9 * (fat grams) + 4 * (carb grams) + 4 * (protein grams) =
9 * 6.0 + 4 * 49.0 + 4 * 6.0 = 274.0
Its percent fat is a little over 19.7 because the calories from fat are 54
and the total calories are 274. As usual, percentages should be expressed
as real numbers in the range of 0.0 to 100.0. You may assume that the
number of calories will be greater than 0.
The toString method should include the name of the item followed by a colon
followed by the fat, carbohydrate and protein grams, separated by commas,
and labeled, as in the following examples for item1, item2, and item3 above:
sausage biscuit: 31.0g fat, 39.0g carbohydrates, 11.0g protein
strawberry sundae: 6.0g fat, 49.0g carbohydrates, 6.0g protein
banana: 0.4g fat, 31.1g carbohydrates, 1.5g protein
Your class should also implement the Comparable interface. Items should be
ordered first by percent of calories coming from fat (lowest to highest) and
then by name (sorted alphabetically).
8. Binary Trees, 20 points. Write a method of the IntTree class called tighten
that eliminates branch nodes that have only one child from the tree. For
example, if a variable called t stores a reference to the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 28 | | 19 |
+----+ +----+
/ /
/ /
+----+ +----+
| 94 | | 32 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 65 | | -8 | | 72 |
+----+ +----+ +----+
\ / \
\ / \
+----+ +----+ +----+
| 10 | | 42 | | 50 |
+----+ +----+ +----+
then the call:
t.tighten();
should leave t storing the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 94 | | 72 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 65 | | 10 | | 42 | | 50 |
+----+ +----+ +----+ +----+
Notice that the nodes that stored the values 28, 19, 32, and -8 have all
been eliminated from the tree because each had one child. When a node is
removed, it is replaced by its child. Notice that this can lead to multiple
replacements because the child might itself be replaced (as in the case of
19 which is replaced by its child 32 which is replaced by its child 72).
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 of the LinkedIntList class called
shiftLastOf3 that shifts the third value in each successive group of three
from a list of integers to the front of the list, preserving the relative
order of the values and returning a count of the number of nodes that were
shifted. For example, if a variable called list stores these values:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
| | | | | | | |
+-----+ +-----+ +-----+ +------+
group group group group
Then after the call:
int count = list.shiftLastOf3();
the list should store the following values:
[2, 5, 8, 11, 0, 1, 3, 4, 6, 7, 9, 10]
and the variable count would be set to 4. Notice that the original list has
four groups of three values. The last value in each group (2, 5, 8, and 11)
has been shifted to the front of the list but otherwise all values still
have the same relative ordering as they did in the original list. Because
four values were shifted, the method returns a value of 4.
This example uses consecutive integers to make it easier to see the effect
of the shifting, but you should not make any assumptions about the values in
the list. It also has no stray values at the end. If there are extra
values at the end of a list that don't make a complete group of three, then
they are not shifted. For example, if a list contains fewer than three
values, then no values are shifted and the method would return a count of 0.
As another example, if list had instead stored these values:
[3, 19, 7, 45, -2, 8, 6, 18, 42, 5, 12]
| | | | | |
+------+ +------+ +-------+
group group group
then after the method is called, it would store these values:
[7, 8, 42, 3, 19, 45, -2, 6, 18, 5, 12]
and the method would return 3 to indicate that three values were shifted.
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, you may not use any auxiliary data structure to
solve this problem (no array, ArrayList, stack, queue, String, etc), and
your solution must run in O(n) time where n is the number of nodes in the
list. You also may not change any data fields of the nodes. You MUST solve
this problem by rearranging the links of the list.
]]>