Algorithm and Data Structures related questions Explanation

Algorithm and Data Structures related questions (Explanation with the answers will be appreciated) :

In which situation will a sentinel be inappropriate? Search for a key in an unordered linked list, to simplify and speed-up code Red-black tree, to simplify code Binary search for a key in an ordered table, to simplify and speed-up code Search for a key in an unordered table, to simplify and speed-up code A more accurate name for the subset sum problem is: Combination sum Indivisible, unbounded knapsack Maximum achievable sum Permutation sum How should the successor of a node without a right child in an unbalanced binary search tree be found? Examine the ancestors of the node Go left, then proceed to the right Go right, then proceed to the left D. Preorder traversal The purpose of the binary searches used when solving the longest (monotone) increasing subsequence (LIS) problem is: to sort the original input to assure that the final solution is free of duplicate values to determine the longest possible increasing subsequence terminated by a particular input value to search a table that will contain only the LIS elements at termination Recursion is often an alternative to using which data structure? Linked list Queue Stack 2-d array The expected number of comparisons for finding the kth largest of n keys using PARTITION is in which asymptotic set? Theta(logn) Theta(n) Theta(n log n) Theta(n^2) The time to extract the LCS (for sequences of lengths m and n) after filling in the dynamic programming matrix is in: Theta(n) Theta(m + n) Theta(n log n) Theta(mn) Which binary tree traversal corresponds to the following recursive code? void traverse(node x) {if (x = = null) return; traverse(x rightarrow left);//process x here traverse (x rightarrow right);} inorder postorde preorder search fo key x

Solution

9)B.ubset sum can also be thought of as a special case of theknapsack problem.

11)D to search table table will contain only LIS elements

12)C Because recursion uses stack for function call

14)Time Complexity of the above implementation is O(mn) which is much better than the worst case time complexity of Naive Recursive implementation.

15)Inorder traversal as it is traverse in order left-root-right