1. Short Answer

Answer each of the following in just a few words.

Part A [2 pts]

What is the difference between a complete binary tree and a perfect binary tree?

Part B [2 pts]

The worst-case efficiency of inserting into a hash table is technically O(N), but in practice they are usually O(1). Why?

Part C [2 pts]

What is the largest, signed value that can be stored in a 6-byte integer? You do not need to reduce your answer. Be certain to show your work, and also very clearly circle your answer!

Part D [2 pts]

If you implement a queue with an ArrayList, can all the operations be O(1)? Why or why not?

Part E [2 pts]

Why should testcases be able to run and checking passing/failure automatically? (As opposed to requiring the developer to manually inspect the output.)

Part F [1 pts]

What does it mean when you get a NullPointerException?

---

2. Big-Oh

Determine the big-oh runtime of each of the following, in terms of N as specified in each problem. Circle your final answer for each.

Part A [3 pts]

// a contains N items
public static ArrayList<Integer> bigO1(HashSet<Integer> a) {
    ArrayList<Integer> b = new ArrayList<Integer>();
    for (int i : a) {
        i = Math.abs(i);
        if (i < 100) {
            b.add(i);
        }
    }
    return b;
}

Part B [3 pts]

// a contains N items, b contains N items
public static void bigO2(ArrayList<Integer> a, TreeSet<Integer> b) {
    for (int i : a) {
        if (!b.contains(i)) {
            b.add(i);
        }
    }
}

Part C [3 pts]

Be careful…

// a contains N items, b contains N items
public static void bigO3(HashSet<Integer> a, TreeSet<Integer> b) {
    ArrayList<Integer> c = bigO1(a);
    bigO2(c, b);
}

---

3. Linked List Memory Diagram [8 pts]

Consider the following code snippet that creates a linked list. You may assume that the ListNode class exists and was defined as in class.

ListNode<Integer> head = null;
ListNode<Integer> tmp = null;
ListNode<Integer> tmp2 = null;
ListNode<Integer> other = null;

head = new ListNode<Integer>(10);
printList(head);
// Stop and draw Diagram A.

tmp = new ListNode<Integer>(20);
tmp2 = new ListNode<Integer>(30);
other = new ListNode<Integer>(40);

tmp2 = head;
while(tmp2.next != null) {
    tmp2 = tmp2.next;
}
tmp2.next = tmp;
// Stop and draw Diagram B.

other.next = tmp;
// Stop and draw Diagram C.

head.next = other;
// Stop and draw Diagram D.

other.next.next = head;
head.next = null;
head = other;
// Stop and draw Diagram E.

Draw the state of the linked list, at each of the commented lines of code. The linked list is defined as starting at head. You do not need to draw the other three references (tmp, tmp2, or other).

The first one is drawn for you:

Draw the remaining four diagrams: Diagram B, Diagram C, Diagram D, and Diagram E.

Be sure to label each picture clearly with which Diagram it is.

---

4. BST Building

Imagine you are constructing a binary search tree of integers, and the following integers are added in the following order:

80, 13, 73, 59, 88, 60, 67, 94, 81, 6

Part A [4 pts]

Draw the resulting binary search tree.

Part B [4 pts]

Assuming you are using the in-order successor removal technique discussed in class, draw the state of your tree from Part A after 13 has been removed from it.

---

5. BST Traversal

Consider the following binary search tree:

Part A [3 pts]

Assuming the tree is traversed pre-order and the nodes printed, what is the resulting sequence? (Within the traversal, assume that left is followed before right.)

Part B [3 pts]

Assuming the tree is traversed post-order and the nodes printed, what is the resulting sequence? (Within the traversal, assume that left is followed before right.)

Part C [3 pts]

Assuming the tree is traversed in-order and the nodes printed, what is the resulting sequence? (Within the traversal, assume that left is followed before right.)

---

6. Heaps

Consider the following array representation of a binary heap:

	80	77	61	72	76	39	55	35	51	47

Part A [3 pts]

Draw the heap represented by this array.

Part B [2 pts]

Draw the heap after adding 70 to it. Show your work, but clearly mark your final answer. (Do not write your answer as an array, instead draw the final state of the heap.)

Part C [2 pts]

Building on your answer from part b, draw the heap after calling removeMax() on it. Show your work, but clearly mark your final answer. (Do not write your answer as an array, instead draw the final state of the heap.)

---

7. Free Response: The Quiz Policy [8 pts]

Consider the following excerpt from a course syllabus:

In order to reward improvement, I will replace one quiz score that is immediately followed by two higher scores. So, if you have a quiz that goes very badly, but your next two quizzes are each better than that bad quiz, I will replace that low quiz with the higher of the two scores immediately following it. If you have multiple "bad" quizzes that meet the criteria, I will replace the one that maximizes your point gain.

Write the static function lowestBeforeTwoIncreases which takes as an argument an array of integers (representing quiz scores), finds the quiz that needs to be replaced according the policy, and returns the difference between that quiz and the larger of the two quizzes that follow it. If there is no quiz that will be replaced, simply return 0.

For example, the following two examples each print 30:

int[] a = { 40, 20, 40, 35, 50, 65 };
System.out.println(lowestBeforeTwoIncreases(a));

int[] b = { 25, 30, 20, 45, 40, 60, 70, 80, 90, 100 };
System.out.println(lowestBeforeTwoIncreases(b));

The first example prints 30 because the quiz to be replaced is the 35, and it will be replaced by a 65, and the difference between those two is 30.

The second example prints 30 because the quiz to be replaced is the 40, and it will be replaced by a 70, and the difference between those two is 30.

Hint: You don’t actually need to figure out which element of the array will ultimately be replaced. Instead, you just need to figure out the largest difference among all candidates that meet the “lower before two higher” criteria.

---

8. Most Frequent Word [10 pts]

Consider the WordCounter class. It is used to catalog the occurrences of words and keep track of which word it has seen most often. It has the following methods:

• addWord(String word). Add a word to the catalog. This method must be O(1).
• loadFile(String filename). Load a file, filename, that contains words, one per line. Load each word into the catalog. This method must be O(N), where N is the number of words in the file.
• mostFrequentWord(). Return the most frequent word seen in the catalog so far. This method must be O(1). If there is a tie (meaning there is more than one most common word), then return whichever you would like.

Consider the following testcase:

WordCounter w = new WordCounter();
w.addWord("bun");
w.addWord("cat");
w.addWord("dog");
w.addWord("bun");
w.addWord("dog");
w.addWord("dog");

// This next line will print "dog", because "dog"
// has occurred 3 times in total.
System.out.println(w.mostFrequentWord());

w.loadFile("words.txt");

// This next line will print "bun", because "bun"
// has occurred 4 times in total.
System.out.println(w.mostFrequentWord());

words.txt contains:

bun
monkey
monkey
bun
monkey

Write the WordCounter class.

Note:

• Pay special attention to the efficiency requirements. Getting mostFrequentWord to be O(1) will require some extra thought.
• If your solution is not as efficient as required, you can still receive partial credit.

---

9. BST Free Response [10 pts]

Consider the following definition of a TreeNode:

public class TreeNode<DataType extends Comparable<DataType>> {
    public DataType data;
    public TreeNode<DataType> left;
    public TreeNode<DataType> right;

    public TreeNode(DataType data) {
        this.data = data;
    }
}

Notice this is a generic binary tree node, and could be used to build any sort of binary tree. (For example, this node could be used to build a binary search tree or a heap.)

Write the public static method isValidBST which takes as an argument a TreeNode representing the root of a tree, and returns true if that tree is a valid binary search tree and false otherwise.

Hints:

• Recursion is your friend here.
• Because it takes an argument, your static method can call itself recursively if you’d like.
• Remember, not all binary trees are binary search trees. This should only return true if the root node passed in represents the root of a tree that meets all the criteria of a binary search tree.
• An empty tree can be considered a valid BST.

---

10. Welcome to the Jungle [20 pts]

In this problem you are going to write an Animal class. Here are some important requirements for your class:

• An Animal has a species and age. When a new Animal is created, these items are passed to the constructor. (You must provide the constructor.)

• The only way for code outside of Animal to read and modify the attributes of an Animal must be using appropriately named getters and setters. (You must provide the getters and setters.)

• An animal’s age must be between 0 and 200. (0 because the animal could be newly born, and 200 because some tortoises can live to be very old.) If an attempt is made to set the age to something invalid, an IllegalArgumentException must be thrown.

• When printing an Animal, its type and the value of its instance variables should appear. (Such as when System.out.println(someAnimal) is used.)

• An Animal needs to be able to be properly used in HashSets and HashMaps.

• An array of Animals must be sortable using Arrays.sort(someArrayOfAnimals). Animals should be sorted by species, and if that is the same, then by age.

Write the Animal class to the above specifications. Pay careful attention to which classes you may need to extend or implement as well as which methods you need to write or override.