CS 2401 Test #3

Date: Thursday, April 28, 2011.

Name: ___________________________________________________________________

1-2. Write Java methods for push and peek when the stack is implemented (1) as an array and (2) as a linked list.

3. Assume that queue of students interested in checking out an interesting library book is implemented as an array of size 3. Show, step-by-step, what will happen if these events occur in this order: Student 1 joins the queue, Student 2 joins the queue, Student 1 gets the book, and Students 3, 4, and 5 join the queue.

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

6-7. Show, step by step, what will happen if we start with an empty binary search tree and add, one by one, the following elements: 4, 28, 20, and 11. Balance the tree every time such a balancing is needed. Then draw the final tree as it would be constructed in (a) a link-list-based and (b) an array-based implementation of trees.

8. Write a recursive algorithm for inserting a given element into a binary search tree. Then implement the algorithm in Java.

9-10. Show how the heapsort algorithm sorts the list consisting of the elements 4, 28, 20, and 11: 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?