8. In which situation will a sentinel be inappropriate? A. Search for a key in an unordered linked list, to simplify and speed-up code B. Red-black tree, to simplify code C. Binary search for a key in an ordered table, to simplify and speed-up code D. Search for a key in an unordered table, to simplify and speed-up code 9. A more accurate name for the subset sum problem is: A. Combination sum B. Indivisible, unbounded knapsack C. Maximum achievable sum D. Permutation sum 10. How should the successor of a node without a right child in an unbalanced binary search tree be found? A. Examine the ancestors of the node B. Go left, then proceed to the right C. Go right, then proceed to the left D. Preorder traversal 11. The purpose of the binary searches used when solving the longest (monotone) increasing subsequence (LIS) problem is: A. to sort the original input B. to assure that the final solution is free of duplicate values C. to determine the longest possible increasing subsequence terminated by a particular input value D. to search a table that will contain only the LIS elements at termination 12. Recursion is often an alternative to using which data structure? A. Linked list B. Queue C. Stack D. 2-d array 13. The expected number of comparisons for finding the kth largest of n keys using PARTITION is in which asymptotic set? A. O(logn) B. O(n) c. O(nlogn) D. (n) D. (mn) 14. The time to extract the LCS (for sequences of lengths m and n) after filling in the dynamic programming matrix is in: A. O(n) 15. Which binary tree traversal corresponds to the following recursive code? B. (m + n) void traverse (node x) { C. O(n log n) if (x==null) return; traverse (x->left); // process x here traverse(x->right); } A. inorder B. postorder C. preorder D. search for key x 4 Quicksort(All..r]) anisaid //Sorts a subarray by quicksort //Input: Subarray of array A[0..n-1]. defined by its left and right "I 1611T indices/ and r //Output: Subarray A[..r] sorted in nondecreasing order if I O m intiv bund s+Partition(A[..]) //s is a split positionid Quicksort(A[I..s-1]) bon viss no snizzim Quicksort(A[s+1..r]) 83 ALGORITHM Hoare Partition(A[I..r])led A it //Partitions a subarray by Hoare's algorithm, using the first element du as a pivot Juvies //Input: Subarray of array A[0..n-1], defined by its left and right indices and r (l