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.
- Write a method to compute the sum of the data values in the binary tree: