This is an exam. You may use your textbook, your notes, my example code, and your own programs. Do not use the Internet or other sources of information. Explain your answers clearly. Have fun.
(8 points) Suppose you want the CharList class to store not just a list of characters, but a list of characters sorted in increasing order. You will need to modify the add( char ch ) method, and then use the modified method to rewrite the set( String s ) method. Make the appropriate changes and submit your code for add and set on paper along with the rest of the exam.
(6 points) The usual way to traverse an array is with a loop. You start an index variable at 0, and run the index up to the length of the array minus 1, printing or adding or doing something along the way. But you can also traverse an array without loops. Show how you would write a recursive method to print out the contents of an array. Your method must not contain any loops.
(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.
How should you initialize front and back to indicate an empty queue?
Show the state of the queue (including the contents of the array and the values of the indices) after you have initialized to empty and then performed Add("goat"), Add("newt"), Add("sea cucumber"), Delete(), Add("coatimundi"), Delete(), Add("vole").
How can you tell whether the queue is full?
(8 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.
When you reallocate, add an extra 1024 integers. The arrays will thus be 1024, 2048, 3072, 4096, etc. integers long.
When you reallocate, double the size of the array. The arrays in this case will be 1024, 2048, 4096, 8192, etc. integers long.
(8 points) For each of the following algorithms, describe the running time T(N) in terms of big oh, omega, and theta.
Using the usual scan from one end to the other, find the maximum value in an unsorted array of N integers.
Search for a given integer in a sorted array of N integers using binary search.
Sort an array of N integers using Insertion Sort.
(3 points) I just finished reading a couple books, and I could use something interesting to read. Any suggestions?
(6 points) Start with an empty binary search tree, whose nodes will have integer keys. Add the following integers to the tree, one at a time, in this order: 10, 3, 9, 14, 27, 11, 13, 6, 12, 16.
Show the tree after you have added the integers.
If you call the following method with the root of this tree as its parameter, what output appears? (Assume a BSTNode like the one we have used in class.
public static void Visit( BSTNode root )
{
if( root != null )
{
Visit( root.left );
Visit( root.right );
System.out.println( root.data );
}
}