1. (20 points) Sort the following asymptotic growth rates in an increasing order: (! )#, 𝑛!, 4#, 𝑛!, log𝑛, (log𝑛)".
"
2. (20 points) Using Figure 10.1 (Textbook Exercise 10.1-1) as a model, illustrate the result of each operation in the sequence PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S) on an initially empty stack S stored in array S[1, 2, …, 6].
3. (20 points) Using Figure 10.2 (Textbook Exercise 10.1-3) as a model, illustrate the result of each operation in the sequence ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), and ENQUEUE(Q, 8) on an initially empty queue Q stored in array Q[1, 2, …, 6].
4. (20 points) The structure of a singly linked list is shown as follows:
Please give the pseudocode of the operations Insertion and Deletion on a singly linked list. For Deletion, it is required that deleting the first key from the list. (Hint: refer to the operations of insertion and deletion on a doubly linked list in Chapter 10.2).
5. (20 points) Write the pseudocode of Tree-Predecessor procedure. (Hint: predecessor of a node x is the largest key smaller than x in tree and the idea to find a predecessor is similar to Tree-Successor procedure in Textbook.)
1
