A. InsertionB. LSD Radix Sort C. MERGE-SORT D. QUICKSORT 6. The most accurate description of the time to perform a deletion in an unbalanced binary search tree with n keys and height h is: 7. Based on dictionary search performance alone, the best justification for ordering a linked list is: A. Many more misses than hits are expected B. Sentinels are more effective in speeding up search Many more hits than misses are expected Less storage will be needed C. D. The purpose of the binary searches used when solving the longest (monotone) increasing subsequence (LIS) problem is A. to assure that the final solution is free of duplicate values B. to determine the longest possible increasing subsequence terminated by a particular input value C. to search a table that will contain only the LIS elements at termination D. to sort the original input An unsorted integer array with 1500 unique elements is subscripted starting with 0. You would like to iteratively use PARTITION to find the thirty largest values, but there is no requirement that the thirty largest values be ordered. Which of the following is not correct? A. If 1470 is returned from PARTITION, we are done B. If 1481 is returned from PARTITION, we must continue C. If 1468 is returned from PARTITION, we must continue D. If 1469 is returned from PARTITION, we must continue 8. 9. 10. Which of the following is a longest common subsequence for 0 1 201 2 and00 1212? A. 0011 B. 01212 C. 0012 D. 0120 11. Which of the following binary trees has multiple legal colorings as a red-black tree? 12The expected number of comparisons for finding the kth largest of n keys using PARTITION s in which asymptotic set? A. (log n) B. (n) (n log n C. 13. Which of the following will not be true regarding the decision tree for MERGESORT for sorting n input values? A. Every path from the root to a leaf will have O(nlogn) decisions 2 21 n-l decisions B. There will be a path from the root to a leaf with 4 C. The height of the tree is (n log n ) D. There will be ! leaves