CS 2401 Test #3

Date: Wednesday, April 27, 2011.

Name: ___________________________________________________________________

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

3. Assume that a queue of students waiting to be advised 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, B joins the queue, A is served, and C and D and R join the queue.

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

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: 0, 4, 2, 7, 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 searching for a given element in a binary search tree. Then implement the algorithm in Java.

9-10. Show how the heapsort algorithm sorts the list consisting of the elements 0, 4, 2, 7, 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?