Algorithm and Data Structures related questions Explanation

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

Which version of rat-in-a-maze finds the shortest path? A. queue B. recursive C. red-black tree D. stack How should the successor of a leaf in an unbalanced binary search tree be found? A. Examine the ancestors B. Go right, then proceed to the left C. Inorder traversal D. Preorder traversal If Pop is implemented as return stack[SP], then Push of element X is implemented as: A. return stack[SP++] B. stack[SP++] = X C. stack[SP] = X D. stack[++SP] = X What is the worst-case time to perform MAXIMUM(L) for a circular, sorted, doubly-linked list with n nodes? A. 0(1) B. 0(log n) C. 0(n) D. 0(n log n) For which of the following sorts does the decision tree model not apply? A. Insertion B. LSD Radix Sort C. MERGE-SORT D. QUICKSORT The most accurate description of the time to perform a deletion in an unbalanced binary search tree with n keys and height h is: A. 0(1) B. 0(log n) C. 0(n) D. 0(h) 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 C. Many more hits than misses are expected D. Less storage will be needed 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 List 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. Which of the following is a longest common subsequence for 0 1 2 0 1 2 and 0 0 12 12? A. 0 0 11 B. 0 1 2 1 2 C. 0 0 1 2 D. 0 1 2 0 Which of the following binary trees has multiple legal colorings as a red-black tree? The expected number of comparisons for finding the kth largest of n keys using Partition is in which asymptotic set? A. 0(log n) B. 0(n) C. 0(n log n) D. 0(n^2)

Solution

ANSWER:

1) A (queue).

2) C (Inorder traversal)

explanation:

in binary tree inorder successor of a node is the next node in inorder traversal of the binary tree and null for the last node in inorder traversal

3) C

push of element X is implemented as stack[--sp]=X.

4) D

5) B (LSD Radix sort)

explanation:

lower bound of comparison sorting algorithm does not apply to counting sort radix sort bucket sort ,only applies to insertion,selection,merge ,heap sorts.

11) A

12) B

explanation:

The partition based algorithm are generally done in place,which thus results in partially sorting the data.they can be done out of place ,not changing the originl data at the cost of O(n) additional space