Algorithm and Data Structures related questions Explanation

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

Write your answer to the LEFT of each problem. In a binary search tree, which element does not have a predecessor? any one of the leaves the maximum the minimum the root Suppose the tree below is a binary search tree whose keys are not shown. Which node will contain the key that is the predecessor of the key stored at H? A B C G Which of the following will not be true regarding the decision tree for Mergesort for sorting n input values? There will be a path from the root to a leaf with ohm(n^2) decisions. There will be n! leaves. Every path from the root to a leaf will have O(n^2) decisions. The height of the tree is ohm(n log n). What is the worst-case time to perform Maximum(L) for an unordered, doubly-linked list with n nodes? Theta(1) Theta(log n) Theta(n) Theta(n log n) Given a pointer to a node, the worst-case time to delete the node from a doubly-linked list with n nodes in ascending order is: Theta(1) Theta(log n) Theta(n log n) Theta(n) 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. Theta(1) Theta(log n) Theta(n) Theta(n log n) An array with 150 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? If 119 is returned from PARTITION, we must continue. If 118 is returned from PARTITION, we must continue. If 131 is returned from PARTITION, we must continue. If 120 is returned from PARTITION, we are done. 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

Solution

Given 9 questions, I am answering only first 4.

1. Option C, i.e. the minimum. Note that leaves can have predecessor. Maximum can have predecessor as node with value less than maximum value. Similarly root can have predecessor in its left subtree

2. Option B, i.e. node B. Value of node A cannot be predecessor of H, as H is in left subtree of A. Similarly for C and G, as they are in right subtree of A, whereas H is in left subtree of A, they cannot be predecessor of H. Only option left is node B, and that is correct because, as H doesn\'t have left subtree, its predecessor would be B

3. option A. We can safely say that option C is correct, given to completely sort it, we need to compare every two numbers in worst case i.e. n*(n-1) comparison i.e. O(n2). From option C, we can conclude A is incorrect.

4. O(n), as linked list is unordered, we have iterate over all elements atleast once, to find maximum of the list, thus O(n)