## 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:
(a) with no balancing, and
(b) with balancing.
For the resulting balanced tree:
• show the elements in pre-order, in-order, and post-order; then
• draw the tree as it would be constructed in a link-list-based implementation of trees; and
• show what will happen if we delete the root element.

```

```
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:

```                         10
/    \
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?