CSE143 Sample Final 1. Binary Tree Traversals, 6 points. Consider the following tree. +---+ | 2 | +---+ / \ / \ +---+ +---+ | 6 | | 7 | +---+ +---+ / \ \ / \ \ +---+ +---+ +---+ | 0 | | 1 | | 9 | +---+ +---+ +---+ / \ / \ / \ / \ +---+ +---+ +---+ +---+ | 3 | | 5 | | 8 | | 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: Kirk, Spock, Scotty, McCoy, Uhuru, Chekov, Sulu. Assume the search tree uses alphabetical ordering to compare words. 3. Binary Trees, 10 points. Write a method purebredOdds that returns the number of purebred odd values in a binary tree of integers. A purebred odd is an odd number all of whose ancestors in the tree are also odd numbers. For example, suppose that a variable t refers to the following tree: +----+ | 15 | +----+ / \ / \ +----+ +----+ | 27 | | 34 | +----+ +----+ / \ \ / \ \ +----+ +----+ +----+ | 29 | | 75 | | 83 | +----+ +----+ +----+ / \ / \ / \ / \ +----+ +----+ +----+ +----+ | 18 | | 33 | | 46 | | 51 | +----+ +----+ +----+ +----+ Then the call t.purebredOdds() should return 5 because this tree has a total of 5 purebred odd values: 15, 27, 29, 75, and 33. The values 83 and 51 are odd numbers, but not purebred odd numbers because they have an even number as an ancestor in the tree (the value 34). Notice that if the overall root is an even number, then the tree will have no purebred odd numbers at all because every other node has the overall root as an ancestor. 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 } public class IntTree { private IntTreeNode overallRoot; } 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. 4. Programming with inheritance, 20 points. You have been asked to extend a Java class called DocumentList that is used to store a list of Document objects. The DocumentList class has a set of methods that is similar to those we have seen for the built-in ArrayList and LinkedList classes: public DocumentList(int capacity) constructs an empty document list of given capacity public void add(Document d) appends d to end of list public void add(int index, Document d) inserts d at given index public void remove(int index) removes document at given index public int indexOf(Document d) returns index of first occurrence of d; -1 if not found public int size() returns # of elements in the list The class works correctly, but we are interested in analyzing how the list changes over time. In particular, we are going to collect statistics about the sequence of states the list goes through as it is modified. The list is constructed as an empty list and this will be the first state we want to keep track of. Then, each time that the list is modified, we want to keep track of that new state. The list is modified each time a client calls either of the add methods or the remove method. Each modification leads to a new state even if the list ends up returning to a value it had previously. For example, the list starts out as an empty list and it might go through a series of modifications that lead it to be empty a second time, but we would consider each to be a different state. You are to define a new class called AnalyzingDocumentList that extends through inheritance the DocumentList class so that it has the same functionality described above while also keeping track of information about the various states that the list goes through. In particular, it should provide the following additional public methods: public int totalStates() a count of the total number of states this list has gone through public int sizeCount(int size) a count of the number of states this list has gone through in which its size was the given size For example, suppose that an AnalyzingDocumentList called lst is manipulated in the following ways: the list is constructed (size is 0) a document is appended to the end of the list (size now 1) a document is appended to the end of the list (size now 2) a document is appended to the end of the list (size now 3) a document is added at index 1 (size now 4) the document at index 1 is removed (size now 3) the document at index 0 is removed (size now 2) a document is added at index 0 (size now 3) a document is appended to the end of the list (size now 4) Then the analyzing methods would return the following values: lst.totalStates() returns 9 (initial state plus 8 modifications) lst.sizeCount(0) returns 1 (1 state had size 0) lst.sizeCount(1) returns 1 (1 state had size 1) lst.sizeCount(2) returns 2 (2 states had size 2) lst.sizeCount(3) returns 3 (3 states had size 3) lst.sizeCount(4) returns 2 (2 states had size 4) lst.sizeCount(5) returns 0 (no states had size 5) ... 5. Comparable class, 20 points. Define a class 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 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. 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). 6. Binary Trees, 20 points. Write a method mirror that converts a binary tree of integers to its mirror image. For example, if a variable called t stores a reference to a binary tree and you make the following call: t.mirror(); then the links of the tree should be rearranged so that after the call, t stores the mirror image of what it stored before the call. Below is a specific example of how a tree would change: before | after +---+ | +---+ | 9 | | | 9 | +---+ | +---+ / \ | / \ / \ | / \ +---+ +---+ | +---+ +---+ | 6 | | 14| | | 14| | 6 | +---+ +---+ | +---+ +---+ / \ \ | / / \ / \ \ | / / \ +---+ +---+ +---+ | +---+ +---+ +---+ | 9 | | 2 | | 11| | | 11| | 2 | | 9 | +---+ +---+ +---+ | +---+ +---+ +---+ / \ | / \ / \ | / \ +---+ +---+ | +---+ +---+ | 4 | | 1 | | | 1 | | 4 | +---+ +---+ | +---+ +---+ After the call is made, the tree stores the structure that you would see if you were to hold the original tree's diagram up to a mirror. More precisely, the overall root (if it exists) remains in the same place in the mirror image and every other node is moved so that it's new path from the overall root is composed of the old path from the overall root with left and right links exchanged. For example, the node that stores 4 in the example above has the path (left, right, left) in the original tree. In the mirror image, it has path (right, left, right). The node that stores 1 has the path (left, right, right) in the original tree. In the mirror image it has path (right, left, left). 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 } public class IntTree { private IntTreeNode overallRoot; } 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 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 tree. 7. Linked Lists, 20 points. Write a method reverse3 that reverses each successive sequence of 3 values in a list of integers. For example, suppose that a variable called list stores the following sequence of values: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] and we make the following call: list.reverse3(); Afterwards the list should store the following sequence of values: [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13] The first sequence of 3 values (1, 2, 3) has been reversed to be (3, 2, 1). The second sequence of 3 values (4, 5, 6) has been reverse to be (6, 5, 4). And so on. If the list has extra values that are not part of a sequence of 3, those values are unchanged. For example, if the list had instead stored: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17] The result would have been: [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13, 16, 17] Notice that the values (16, 17) are unchanged in position because they were not part of a sequence of three values. These examples purposely used sequential integers to make the rearrangement clear, but you should not expect that the list will store sequential integers. For example, the following list: [3, 8, 19, 42, 7, 26, 19, -8, 193, 204, 6, -4, 99] would be rearranged as follows: [19, 8, 3, 26, 7, 42, 193, -8, 19, -4, 6, 204, 99] Your method should not change the list if it has fewer than three 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 } public class LinkedIntList { private ListNode front; } You are writing a method that will become part of the LinkedIntList class. You may not call any methods of the class to solve this problem, 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.