Include your source code for #6 in your PDF file. You don't need to submit your source code separately.
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 Ondich, 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.
(6 points) Let's pretend you have a queue implemented as a circular array of 4 String references (it's a small queue, admittedly), with indices called front and back to keep track of the state of the queue. front always points to the first item in the queue, and back points to the last item in the queue.
(6 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:
(4 points) Consider the following binary search tree, whose nodes' keys are letters of the alphabet:
(In this representation of a tree, I have written each row of the tree from left to right, with a "-" wherever there is no node. So J is the root, the children of N are K and P, and Q has a right child R but no left child.)
Show the tree that results when you delete the root (J) from the tree using the BST node deletion algorithm in your textbook (p. 323 in section 6.4).
(6 points) Start with an array of characters containing the letters A R T I C H O K E S at indices 0 through 9.
(12 points) For each of the following scenarios, recommend a data structure. Briefly justify your recommendation, using complexity arguments and big-oh notation where appropriate.
(6 points) Suppose you have a binary tree node class, like this:
Write a method to compute the maximum data value in a binary tree:
Don't forget: (1) this is a binary tree, not necessarily a binary search tree, and (2) recursion is your friend.
(6 points) Elmo, Zoe, and Grover are planning to implement a hash table that will have 1024 slots. They have agreed to resolve collisions with chaining. The items the hash table will contain will be English words. They are arguing over what hash function to use. Criticize (positively or negatively) each of these proposals.
(2 points) Please direct me to a web site that you think I should see. Maybe it's amusing or enlightening or stupidly entertaining or just weird or disturbing or whatever.
(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)}.
(6 points) Suppose I have an array in which I'm storing integers as my program generates them. I don't know at compile time how much space I will need, so I decide to start with an array of 1024 integers, and reallocate the space if I need to.
Whenever I generate a new integer, I put it in the first available slot in the array. If the array is full when the new integer arrives, I (1) allocate a new array, bigger than the first, (2) copy all of the old array's contents to the new array, and (3) add the new integer to the end of the new array.
Your job is to analyze the running time of this plan by counting integer assignment statements. Thus, every time we add an integer to an existing array, you should count 1. Also, whenever we copy the old array to the new array, count 1 for each element of the old array.
Assume that we start with an array containing 1024 elements, and that the program generates 10,000 elements. Compute the number of integer assignments for each of the following reallocation strategies. Then, assume the program generates N elements, and give a big-oh/theta/omega analysis of each strategy.