**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.

- 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 189-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?