You may include scanned or photographed hand-drawn diagrams, but if you do, make sure they're
neat and easy to understand.
This is an open-notes, open-Internet, open-book exam. The only thing you aren't allowed
to do is consult with other people about the exam (except for Jeff and Kate, with whom you
may discuss the exam as much as you like). Just to be clear: posting questions on online
forums counts as consulting with other people, and is thus prohibited. If you use information
obtained online or from a book, cite your sources.
- (5 points) Imagine starting with an empty binary search tree whose nodes
have characters for keys, and adding the letters F A C E T I O U S L Y to the tree
in that order.
- Show the resulting tree.
- If I search for the letter R in this BST, to which letters will I compare
R, and in what order?
(7 points) Start with an empty max-heap H of integers, implemented as an array A with root node to be
placed at A[1] (i.e. we will ignore A[0], as we did when discussing heaps in class).
Suppose we start by adding the following integers to H, in this order:
10, 3, 12, 14, 9, 2, 11, 16, 13, 7
- Show the contents of the array A after those items are added.
- Now perform two dequeue (also known as serve or delete or offer) operations
on H. Which integers get dequeued?
- Show the contents of A after the two dequeue operations from the previous question are complete.
HEADS UP: H is a MAX-heap, not a min-heap. We did min-heaps in class.
(9 points) Consider a graph G with 9 nodes numbered 0 through 8,
whose edge set is {(0,3), (0,1), (0,7), (3,6), (3,4), (1,4), (4,5),
(4,2), (7,5), (6,2), (8,2)}.
- Draw the graph.
- Using this breadth-first search
algorithm, list the nodes in the order in which
they will be visited in a search starting at node 0. Draw the
resulting spanning tree.
- Using this depth-first search
algorithm, list the nodes in the order in which
they will be visited in a search starting at node 0. Draw the
resulting spanning tree.
During your BFS and DFS, you will sometimes have to choose which neighbor
of a specific node to add to your queue or stack next. When you're choosing between
neighbors, you should choose the smaller-numbered neighbor first.
(12 points) Consider this stripped-down version of my Sorter.java:
SorterForTest.java.
I have added an implementation of Quicksort, and deleted all the fancy command-line processing and
timing code to keep the overall program as clean as possible.
Each of the following questions assumes that we start with this int[]
array called numbers, loaded with values like so:
- Assuming we call insertionSort(numbers) on the array shown above,
show the contents of numbers after three iterations
of the outer loop in insertionSort.
- Assuming we call selectionSort(numbers) on the array shown above,
show the contents of numbers after three iterations
of the outer loop in selectionSort.
- Assuming we call quickSort(numbers) on the array shown above,
show the contents of the parameters of quickSortRange the
second time quickSortRange gets called.
- Assuming we call mergeSort(numbers) on the array shown above,
show the contents of the parameters of mergeSortRange the
second time mergeSortRange gets called.
- (3 points) I'm always reading a couple books, but the last few I've
read have been kind of unsatisfying. What should I read next?
(9 points) For each of the following scenarios, recommend a
data structure. Briefly justify your recommendation, using complexity arguments and
Big-O notation where appropriate.
- You have a database of a few hundred items, each of which
has a single search key. You plan to do lots of adding and
deleting, and millions of searches. It is essential that
you keep search times as short as possible. You can have
as much memory as you want.
- You have a database of a few million items, and it's
mostly static. That is, you are seldom going
to add items to or delete items from the database.
Each item in the database has a single search key, and
you plan to do lots of searches.
Memory is extremely limited, though it is sufficient to hold all
the items. (Note that this scenarios can actually happen on low-memory
handheld devices, on chips embedded in cars and appliances, etc.)
- You're writing a system that processes credit card validation
requests. The requests often come in faster than you can process them,
so they need to be stored in some sort of data structure while the processor
handles other requests. Furthermore, some of your company's clients have paid a
big fee to be "Preferred Customers." When a credit card validation request
comes in from a Preferred Customer, it needs to be processed before the
ordinary non-preferred customer requests.
(8 points) Suppose you have a binary tree node class, like this:
class Node {
public int data;
public Node left;
public Node right;
}
- Write a method to compute the sum of the data values in the binary tree:
/**
* Returns the sum of the data values in the binary tree rooted at
* the specified Node root, or 0 if root is null.
*/
public int sum(Node root)
Recursion is your friend.
- Using Big-O notation, describe the running time of the sum method
you just wrote. Explain why your answer is correct.
Just include your code for sum in your exam document. No need to submit
a .java file.