<![CDATA[
CSE143X Sample Final, Autumn 2013 handout #30
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. Recursive Programming, 9 points. Write a method called printTwos that takes
an integer n as a parameter and that prints an expression composed of a
single odd number multiplied by twos that is equal to n. The twos should
surround the odd number with an equal number of twos on either side if
possible. For example, the call:
printTwos(80);
should produce the following output:
2 * 2 * 5 * 2 * 2
If the expression has an odd number of twos, then the "extra" two should
appear at the front of the expression. For example, the call:
printTwos(96);
should produce the following output:
2 * 2 * 2 * 3 * 2 * 2
If the number is odd to begin with, it should simply be printed. It is
possible that the odd number to print will be 1. For example, the following
calls:
printTwos(1);
System.out.println(); // to complete the line of output
printTwos(2);
System.out.println(); // to complete the line of output
printTwos(32);
System.out.println(); // to complete the line of output
should produce the following output:
1
2 * 1
2 * 2 * 2 * 1 * 2 * 2
You must exactly reproduce the format of the examples above. Your method
should throw an IllegalArgumentException if passed a value less than 1. You
are not allowed to construct any structured objects to solve this problem
(no array, String, StringBuilder, ArrayList, etc) and you may not use a
while loop, for loop or do/while loop to solve this problem; you must use
recursion.
3. Details of inheritance, 10 points. Assuming that the following classes have
been defined:
public class Horse extends Cat {
public void method1() {
System.out.println("Horse 1");
super.method2();
}
public void method2() {
System.out.println("Horse 2");
}
}
public class Dog {
public void method2() {
System.out.println("Dog 2");
}
}
public class Pig extends Horse {
public void method2() {
System.out.println("Pig 2");
}
}
public class Cat extends Dog {
public void method3() {
System.out.println("Cat 3");
method2();
}
}
And assuming the following variables have been defined:
Cat var1 = new Pig();
Dog var2 = new Dog();
Dog var3 = new Cat();
Object var4 = new Horse();
Cat var5 = new Horse();
Horse var6 = new Pig();
In the table below, indicate in the right-hand column the output produced by
the statement in the left-hand column. If the statement produces more than one
line of output, indicate the line breaks with slashes as in "a/b/c" to indicate
three lines of output with "a" followed by "b" followed by "c". If the
statement causes an error, fill in the right-hand column with either the phrase
"compiler error" or "runtime error" to indicate when the error would be
detected.
Statement Output
------------------------------------------------------------
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
var5.method3(); ____________________________
var6.method3(); ____________________________
((Pig)var5).method1(); ____________________________
((Cat)var3).method3(); ____________________________
((Cat)var4).method1(); ____________________________
((Pig)var1).method1(); ____________________________
((Horse)var4).method1(); ____________________________
((Cat)var2).method3(); ____________________________
((Horse)var3).method1(); ____________________________
((Dog)var4).method2(); ____________________________
4. Stacks/Queues, 10 points. Write a method called isSorted that takes a stack
of integers as a parameter and that returns whether or not the values in the
stack appear in sorted (nondecreasing) order starting from the bottom of the
stack (returning true if it does, returning false if it does not). For
example, if a stack s stores the following values:
bottom [-5, 0, 3, 18, 23, 42, 208] top
then the call isSorted(s) should return true. If the stack had instead
contained this set of values:
bottom [-5, 0, 3, 18, 23, 42, 208, 17, 20, 94] top
then the call should return false because 208 is followed by numbers smaller
than it (17, 20, and 94).
Your method must restore the stack so that it stores the same sequence of
values after the call as it did before. Any stack with fewer than two
values should be considered to be sorted.
You are to use one queue as auxiliary storage to solve this problem. You
may not use any other auxiliary data structures to solve this problem,
although you can have as many simple variables as you like. You also may
not solve the problem recursively. Your solution must run in O(n) time
where n is the size of the stack. Use the Stack and Queue structures
described in the cheat sheet and obey the restrictions described there.
5. Binary Trees, 10 points. Write a method called printLeaves that prints
the leaves of a binary tree from right to left. More specifically, the
leaves should be printed in the reverse order that they would be printed
using any of the standard traversals. For example, if t stores this tree:
+---+
| 2 |
+---+
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ / \
+---+ +---+ +---+
| 4 | | 5 | | 9 |
+---+ +---+ +---+
then the call:
t.printLeaves();
should produce the following output:
leaves: 9 5 4 0
You must exactly reproduce the format above for a nonempty tree. If the
tree is empty, your method should produce the output "no leaves". Your
method should always produce exactly one line of output. In other words,
if it is called n times, it should produce n lines of output.
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.
6. Collections Programming, 10 points. Write a method called convert that
takes as a parameter a set of strings representing phone numbers and that
returns a map of strings to sets of strings that represent the same phone
numbers split into exchange/suffix. In particular, the phone numbers in the
set passed to the method will each include a 3-digit exchange followed by a
dash followed by a four-digit suffix, as in:
[493-3923, 723-9278, 384-1917, 555-1795, 384-4923, 555-4923, 555-1212,
723-9823]
The method should split each string into the 3-digit exchanges that come
before the dash and the suffixes that come after. The method should
construct a map in which the keys are the 3-digit exchanges. Each such
exchange will be mapped to a set of 4-digit suffixes. For the set of phone
numbers above, the following map would be constructed:
{384=[1917, 4923], 493=[3923], 555=[1212, 1795, 4923], 723=[9278, 9823]}
Notice, for example, that three of the phone numbers in the original set
began with "555". In the map, the key "555" maps to a set of three elements
(the three suffixes that came after "555-").
Your method should construct the new map and each of the sets contained in
the map. Recall that the String class has a substring method that takes a
starting index (inclusive) and a stopping index (exclusive). For example:
"Australia".substring(1, 5) returns "ustr"
The keys of the new map should be ordered by the 3-digit exchanges and each
set should be ordered by the 4-digit suffixes in that set.
7. Comparable class, 15 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).
8. Binary Trees, 15 points. Write a method called makeFull that turns a binary
tree of integers into a full binary tree. A full binary tree is one in
which every node has either 0 or 2 children. Homework 10 involved a full
binary tree (Huffman). Your method should produce a full binary tree by
eliminating all nodes that have only one child. 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.makeFull();
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 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, 15 points. Write a method called reverse3 that reverses each
successive sequence of 3 values in a list of integers. For example, if a
variable called list stores the following 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 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.
The list will not always contain sequential integers. 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
<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 lists. Your solution must run in
O(n) time where n is the length of the list.
]]>