CS 2401 Test #3

Date: Wednesday, November 23, 2011.

Name: ___________________________________________________________________

1-2. Write Java methods for enqueue and dequeue when the queue is implemented (1) as a linked list and (2) as an array.

3. Assume that a queue of students waiting to be served at the UTEP's new sushi place is implemented as an array of size 3. Show, step-by-step, what will happen if these events occur in this order: student A joins the queue, then B and C join the queue, then the first student in line is served, then D and E join the queue.

4-6. Show, step by step, what will happen if we start with an empty binary search tree and add, one by one, the following elements: 11, 2, 3, 201, and 1. Perform two versions of this addition: For the resulting balanced tree:

7-8. Write a recursive algorithm (in English) for inserting for 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 9 into the following full binary tree of height 2:

                       /    \
                      5      15
                    /  \    /  \
                   3    8  13  18

9-10. Show how the heapsort algorithm sorts the list consisting of the elements 11, 2, 3, 201, and 1: 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?