CS 2401 Test #3

Date: Tuesday, November 22, 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 cars waiting to enter UTEP parking garage 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 two students in line are 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, 22, 20, 1, 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) 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 searching for a given element in a binary search tree. Then implement the algorithm in Java code, and trace it on an example of searching for the element 22 in the following full binary tree of height 2.

```                         20
/    \
15      25
/  \    /  \
12   17  22  27

```
9-10. Show how the heapsort algorithm sorts the list consisting of the elements 11, 22, 20, 1, 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?