CS 2401 Test #3

Date: Thursday, August 3, 2012.

Name: ___________________________________________________________________

1-2. To get tickets for different events of the 2012 Olympics, tourists stand in a line (queue). For simplicity, let us assume that a queue is implemented as an array of size 4. Show, step-by-step, what will happen if first tourists A, B, C, and D join the queue, then A gets a ticket, then B gets a ticket, and then E and F join the queue. Write Java methods for enqueue and dequeue when a queue is implemented as an array.

For extra credit: write Java methods for enqueue and dequeue when a queue is implemented as a linked list.

3-4. Suppose that for five athletes, the following running times were recorded: 9.71, 9.82, 9.89, 9.70, and 9.73 sec. Show, step-by-step, what will happen if we start with an empty balanced binary search tree and add, one by one, the above times. For the resulting balanced tree, show the elements in pre-order, in-order, and post-order; which of the three orders corresponds to sorting? Draw the tree as it would be constructed in a link-list-based implementation of trees.

5-6. Show how the heapsort algorithm sorts the list consisting of the elements 9.71, 9.82, 9.89, 9.70, and 9.73: first make it a heap, and then convert, step by step, the resulting heap into a sorted list. What is the worst-case computational complexity of heapsort? How does it compare with other sorting algorithms that you know? What are advantages of disadvantages of heapsort in comparison to other sorting algorithms?

7-8. Write a recursive algorithm (in English) for inserting a given element in a binary search tree. Then implement the algorithm in Java code, and trace it on an example of inserting an element 19 into the following full binary tree of height 2:

                         20
                       /    \
                     15      25
                    /  \    /  \
                   13  18  23   28

9-10. Suppose that we use mod 4 as a hash function. Show what will happen is we insert elements 20, 15, and 28 into the corresponding hash table. What are the main advantages and disadvantages of hash tables?