*Multiple Choice Questions on Data Structure and Algorithm Design*

*Q1. If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes*

*one of the following time.*

*(a) O(n log n)*

**(b) O(n^3)***(c) O(n^2)*

*(d) O(log n)*

*(e) O(n^4).*

*Q2. The upper bound on the time complexity of the non deterministic sorting algorithm is*

**(a) O(n)***(b) O(n log n)*

*(c) O(1)*

*(d) O( log n)*

*(e) O(n^2).*

*Q3. The worst case time complexity of the non deterministic dynamic knapsack*

*algorithm is*

*(a) O(n log n)*

*(b) O( log n)*

*(c) O(n^2)*

**(d) O(n)***Q4. Recursive algorithms are based on*

*(a) Divideand conquer approach*

*(b) Top-down approach*

*(c) Bottom-up approach**(d) Hierarchical approach*

*Q5. What do you call the selected keys in the quick sort method?*

*(a) Outer key*

*(b) Inner Key*

*(c) Partition key*

*(d) Pivot key*

*Q6. The time complexity of the normal quick sort, randomized quick sort algorithms in the*

*worst case is*

*(a) O(n^2), O(n log n)*

*(b) O(n^2), O(n^2)**(c) O(n log n), O(n^2)*

*(d) O(n log n), O(n log n)*

*Q7. Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it, how many times a swap function is called to complete the execution?*

*(a) N log N times*

*(b) log N times*

*(c) N^2 times*

*(d) N-1 times*

*Q8. The Sorting method which is used for external sort is*

*(a) Bubble sort*

*(b) Quick sort*

*(c) Merge sort*

*(d) Radix sort*

*Q9. In analysis of algorithm, approximate relationship between the size of the job and the amount of work required to do is expressed by using _________*

*(a) Central tendency*

*(b) Differential equation*

*(c) Order of execution**(d) Order of magnitude*

*Q10. Worst case efficiency of binary search is*

*(a) log2 n + 1**(b) n*

*(c) n^2*

*(d) 2^n*

*Q11. For analyzing an algorithm, which is better computing time?*

*(a) O(100 Log N)**(b) O(N)*

*(c) O(2^N)*

*(d) O(N logN)*

*Q12. Breadth first search __________*

*(a) Scans each incident node along with its children.*

*(b) Scans all incident edges before moving to other node.**(c) Issame as backtracking*

*(d) Scans all the nodes in random order.*

*Q13. Which method of traversal does not use stack to hold nodes that are waiting to be*

*processed?*

*(a) Dept First*

*(b) D-search*

*(c)Breadth first**(d) Back-tracking*

*Q14. The Knapsack problem where the objective function is to minimize the profit is*

*______*

*(a) Greedy*

*(b) Dynamic 0 / 1*

*(c) Back tracking*

*(d) Branch & Bound 0/1*

*Q15. Sorting is not possible by using which of the following methods?*

*(a) Insertion*

*(b) Selection*

*(c) Deletion**(d) Exchange*

*Q16. What is the type of the algorithm used in solving the 8 Queens problem?*

*(a)Backtracking**(b) Dynamic*

*(c) Branch and Bound*

*(d) DandC*

*Q17. For the quick sort algorithm, what is the time complexity of the best/worst case?*

*(a) best case: O(n) worst case: O(n*n)*

*(b) best case: O(n) worst case: O(n*log(n))*

*(c) best case: O(n*log(n)) worst case: O(n*log(n))*

*(d) best case: O(n*log(n)) worst case: O(n*n)*

*Q18. In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K.*

*The computation time needed to find a data item on T is*

*(a) O(K*K)*

*(b) O(M*M)*

*(c) O(N)**(d) O(K)*

*Q19. Which of the following belongs to the algorithm paradigm?*

*(a) Minimum & Maximum problem*

*(b) Knapsack problem**(c) Selection problem*

*(d) Merge sort*

*Q20. The time taken by NP-class sorting algorithm is*

*(a) O(1)*

*(b) O(log n)*

*(c) O(n^2)*

*(d) O(n)*

*Q21. The time complexity of binary search in best, worst cases for an array of size N is*

*(a) N, N^2*

*(b) 1, Log N**(c) Log N, N^2*

*(d) 1, N log N*

*Q22. Which of following algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desired order?*

*(a) Insertion sort*

*(b) Quick sort*

*(c) Shell sort*

*(d) Bubble sort*

*Q23. From the following choose the one which belongs to the algorithm paradigm other than to which others from the following belongs to.*

*(a) Minimum & Maximum problem*

*(b) Knapsack problem**(c) Selection problem*

*(d) Merge sort*

*Q24. Identify the name of the sorting in which time is not proportional to n^2.*

*(a) Selection sort*

*(b) Bubble sort*

*(c) Qucik sort*

**(d) Insertion sort**.

*Q25. The optimal solution to a problem is a combination of optimal solutions to its sub-problems. This is known as*

*(a) Principleof Duality*

*(b) Principle of Feasibility*

*(c) Principle of Optimality**(d) Principle of Dynamicity.*

*Thanks*

*Mukesh Rajput*
## No comments:

## Post a Comment

Thanks

Mukesh Rajput