Practice problems for algorithms and data structures

4. Circular linked lists are occasionally useful because A. some operations may be done in constant time B. they are an alternative to red-black trees. C. they are useful for implementing circular queues. D. they avoid mallocs. 5. Which of the following binary trees has an illegal red-black tree coloring C. 6. Which of the following will not be true regarding the decision tree for MERGESORT for sorting input values? A. There will be n! leaves. B. Every path from the root to a leaf will have Odecisions. C. There will be a path from the root to a leaf with n-1 decisions. D. The height of the tree is (n log n) Which phase of counting sort actually "counts"? 7. A. first B. second C. third D. fourth 8. What is the worst-case time to find the predecessor of a key in an unbalanced binary search tree storing n keys? Assume that parent pointers are available 9. For which of the following sorts does the decision tree model not apply? A. Insertion B. LSD Radix Sort C. MERGE-SORT D. QUICKSORT 10. The expected number of comparisons for finding the kth largest of n keys using PARTITION is in which asymptotic set? A. (log n) (n) C. (nlogn) B. . The subset sum problem takes input values and attempts to find a combination of those values whose sum is m. The worst-case time to extract the solution from the dynamic programming table is: 12. If PoP is implemented as return stackl-SPl, then PUSH of element X is implemented as: 13. In a red-black tree holding n keys, what is the total number of left and right pointers that will be set to nil (the sentinel)? 14. The disadvantage of using LCS to solve an instance of LIS is: A, return stack[SP++] B. stack[SP++]=X C. stackl--SP-X D. stack[ ++SP1=X 1B. C. 1D. None of the previous answers A. it only works for the monotone case B. it takes ntime in the worst case C. the input must be free of duplicate values D. it requires sorting 15. Suppose that only numbers in 1 .. 1000 appear as keys in a binary search tree. while searching for 500, which of the following sequences of keys could not be examined? A. B. C. D. 300,400, 900, 800, 500 700, 200, 600,550, 500 200. 700, 600, 300, 400, 500 100, 1000, 200800, 300.900. 500