Sunday, 22 October 2017

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