Dark Mode On/Off

# DS & Algorithms Multiple Choice Questions

This Test will cover basic concepts of data Structure and related algorithm.
Q. Consider a quick sort algorithm where n/6th element is selected as pivot element which can be done in O(n) time then what will be the worst case recurrence equation to sort the elements?
 A. T(N)= T(n/6) + O(n) B. T(N) = 2T(N/6) +O(n) C. T(N) =T(N/6) +T(5n/6)+O(n) D. T(N)=T(N-5) + O(n)
Q. Which of the following statements are false :
(I) Binary search can be applied to linked list.
(II) Worst case time complexity of bubble sort is O(n).
(III) Merge sort is in-place algorithm.
(IV) Heap sort is stable algorithm.
 A. Only (I) and (iV) B. Only (III) C. Only (I) D. (I),(II),(III)
Q. What is the maximum profit which can be gained from the below jobs such that no two jobs can be done simultaneously?
 Job J1 J2 J3 J4 J5 J6 Deadline 5 3 3 2 4 2 Profit 199 179 189 299 119 99
 A. 995 B. 985 C. 1000 D. 994

Q. What is the maximum number of spanning trees possible for the below non-weighted graph?

 A. 125 B. 120 C. 160 D. 195
Q. What is the minimum weight possible for minimum spanning tree of below graph?

 A. 11 B. 12 C. 13 D. 14
Q. Which of the following statements are true:
(I) Prim's and kruskal's algorithm for minimal spanning tree may give different trees for some graph.
(II) Any edge with minimum weight will always be present in minimal spanning trees with unique edge weight.
(III) There can be more than one minimal spanning tress for a given weighted connected graph.
 A. I&II B. II only C. III only D. I, II & III
Q. Which of the following is not a stable sorting algorithm pair in its typical implementation?
 A. Quick sort &Heap sort B. Insertion sort & shell sort C. Bubble sort & Counting sort D. Insertion sort & bubble sort
Q. What is the time complexity of optimal merge partition algorithm?
 A. O(n) B. O(logn) C. O(n log n) D. O(2)

Q. What is the time complexity of the following program:
``````
for (i=1; 2<=n; i++)
printf("Study tonight");
```
```
 A. O(logn) B. O( 2) C. O( 0.5) D. O(n log n)
Q. What is the time complexity of the following recurrence relation:
T(n) = 16 T(n/4) + 2
 A. O(n log n) B. O( 2) C. O(16 log n) D. O(3)
Q. What is the total time required to merge 2 unsorted lists (of size n) using two way merging algorithm ?
 A. O(n logn) B. O(n+log n) C. O( 2) D. O( 2 log n)
Q. What is the total time required to apply quick sort algorithm for the elements present in the following array?
 2 2 2 2 2 2 2
 A. O( 2) B. (n log n) C. O(n) D. O(1)

Q. What is the time complexity to insert an element into sorted array using best possible algorithm?
 A. O(log n) B. O( 2) C. O(n) D. O(n log n)
Q. What is the recurrence relation for the searching an element into sorted list using best possible algorithm?
 A. T(n) = T(n/2) + c B. T(n) = 2T(n/2) + c C. T(n) = T(n/2) + n D. T(n) = 2T(n/2) + log n
Q. Which of the following Is representing 3-ary max heap correctly.
 A. 11, 13, 5, 6, 8, 19 B. 9, 6, 3, 11, 18, 5 C. 9, 13, 6, 8, 5, 1 D. 9, 8, 7, 6, 5, 4