5. (10 points) Consider the array A = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

a. (5 points) After we call Build-Heap(A), what are the last 3 elements of the ar-

ray?

A. 3,2,1

B. 1,3,2 C. 4,3,1 D. 1,4,2

b. (5 points) When we do one iteration of Heapsort, how many swaps are made in Heapify to restore the array to heap? Count the swap between the root and the last nodes as the first swap.

A. 2 B. 3 C. 4 D. 5

5. (10 points) Consider the array A = (1,2,3,4,5,6,7,8,9,10). a. (5 points) After we call BUILD-HEAP(A), what are the last 3 elements of the ar- ray? A. (3.2.1) B. (1,3,2) C. (4.3.1) D. (1,4,2) b. (5 points) When we do one iteration of HEAPSORT, how many swaps are made in HEAPIFY to restore the array to heap? Count the swap between the root and the last nodes as the first swap. A. 2 B. 3 C. 4 D. 5 6. (5 points) Consider the RANDOMIZED-QUICKSORT algorithm on the following array A. Which would give you the optimal performance used as the first pivot? A = (27,6.24, 18, 23. 12. 20,29,5.1.13,30,19,7.26) A. 29 B. 5 C. 19 D. The running time does not depend on the first pivot