# Sorting in Data Structure and Algorithms MCQs (500+ MCQs)

Q1. What is the average case running time of an insertion sort algorithm?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q2. Any algorithm that sorts by exchanging adjacent elements require O(N^2) on average..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q3. Which of the following options contain the correct feature of an insertion sort algorithm?.

B.  dependable.

C.  stable, not in-place.

Q4. Which of the following sorting algorithms is the fastest for sorting small arrays?.

A.  Quick sort.

B.  Insertion sort.

C.  Shell sort.

D.  Heap sort.

Q5. For the best case input, the running time of an insertion sort algorithm is?.

A.  Linear.

B.  Binary.

D.  Depends on the input.

Q6. Which of the following examples represent the worst case input for an insertion sort?.

A.  array in sorted order.

B.  array sorted in reverse order.

C.  normal unsorted array.

D.  large array.

Answer=  array sorted in reverse order

Q7. Which of the following is correct with regard to insertion sort?.

A.  insertion sort is stable and it sorts In-place.

B.  insertion sort is unstable and it sorts In-place.

C.  insertion sort is stable and it does not sort In-place.

D.  insertion sort is unstable and it does not sort In-place.

Answer=  insertion sort is stable and it sorts In-place

Q8. Which of the following sorting algorithm is best suited if the elements are already sorted?.

A.  Heap Sort.

B.  Quick Sort.

C.  Insertion Sort.

D.  Merge Sort.

Q9. The worst case time complexity of insertion sort is O(n^2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?.

A.  O(nlogn).

B.  O(n^2).

C.  O(n).

D.  O(logn).

Q10. Which of the following is good for sorting arrays having less than 100 elements?.

A.  Quick Sort.

B.  Selection Sort.

C.  Merge Sort.

D.  Insertion Sort.

Q11. Consider an array of length 5, arr = {9,7,4,2,1}. What are the steps of insertions done while running insertion sort on the array?.

A.  7 9 4 2 1    4 7 9 2 1    2 4 7 9 1    1 2 4 7 9.

B.  9 7 4 1 2    9 7 1 2 4    9 1 2 4 7    1 2 4 7 9.

C.  7 4 2 1 9    4 2 1 9 7    2 1 9 7 4    1 9 7 4 2.

D.  7 9 4 2 1    2 4 7 9 1    4 7 9 2 1    1 2 4 7 9.

Answer=  7 9 4 2 1    4 7 9 2 1    2 4 7 9 1    1 2 4 7 9

Q12. Statement 1: In insertion sort, after m passes through the array, the first m elements are in sorted order.Statement 2: And these elements are the m smallest elements in the array..

A.  Both the statements are true.

B.  Statement 1 is true but statement 2 is false.

C.  Statement 1 is false but statement 2 is true.

D.  Both the statements are false.

Answer=  Statement 1 is true but statement 2 is false

Q13. In insertion sort, the average number of comparisons required to place the 7th element into its correct position is ____.

A. 9.

B. 4.

C. 7.

D. 14.

Q14. Which of the following is not an exchange sort?.

A.  Bubble Sort.

B.  Quick Sort.

C.  Partition-exchange Sort.

D.  Insertion Sort.

Q15. What is an in-place sorting algorithm?.

A.  It needs O(1) or O(logn) memory to create auxiliary locations.

B.  The input is already sorted and in-place.

Answer=  It needs O(1) or O(logn) memory to create auxiliary locations

Q16. In the following scenarios, when will you use selection sort?.

A.  The input is already sorted.

B.  A large file has to be sorted.

C.  Large values need to be sorted with small keys.

D.  Small values need to be sorted with large keys.

Answer=  Large values need to be sorted with small keys

Q17. What is the worst case complexity of selection sort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q18. What is the advantage of selection sort over other sorting techniques?.

A.  It requires no additional storage space.

B.  It is scalable.

C.  It works best for inputs which are already sorted.

D.  It is faster than any other sorting technique.

Q19. What is the average case complexity of selection sort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q20. What is the disadvantage of selection sort?.

A.  It requires auxiliary memory.

B.  It is not scalable.

C.  It can be used for small keys.

D.  It takes linear time to sort the elements.

Q21. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are,.

A.  5 and 4.

B.  4 and 5.

C.  2 and 4.

D.  2 and 5.

Q22. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are,.

A.  5 and 4.

B.  1 and 4.

C.  0 and 4.

D.  4 and 1.

Q23. What is the best case complexity of selection sort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q24. What is an external sorting algorithm?.

A.  Algorithm that uses tape or disk during the sort.

B.  Algorithm that uses main memory during the sort.

C.  Algorithm that involves swapping.

D.  Algorithm that are considered ‘in place’.

Answer=  Algorithm that uses tape or disk during the sort

Q25. What is an internal sorting algorithm?.

A.  Algorithm that uses tape or disk during the sort.

B.  Algorithm that uses main memory during the sort.

C.  Algorithm that involves swapping.

D.  Algorithm that are considered ‘in place’.

Answer=  Algorithm that uses main memory during the sort

Q26. What is the worst case complexity of bubble sort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q27. What is the average case complexity of bubble sort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q28. What is the advantage of bubble sort over other sorting techniques?.

A.  It is faster.

B.  Consumes less memory.

C.  Detects whether the input is already sorted.

D.  All of the mentioned.

Q29. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?.

A. 4.

B. 2.

C. 1.

D. 0.

Q30. What is the best case efficiency of bubble sort in the improvised version?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q31. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?.

A. 4.

B. 2.

C. 1.

D. 0.

Q32. Merge sort uses which of the following technique to implement sorting?.

A.  backtracking.

B.  greedy algorithm.

C.  divide and conquer.

D.  dynamic programming.

Q33. What is the average case time complexity of merge sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q34. What is the auxiliary space complexity of merge sort?.

A.  O(1).

B.  O(log n).

C.  O(n).

D.  O(n log n).

Q35. Merge sort can be implemented using O(1) auxiliary space..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q36. What is the worst case time complexity of merge sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q37. Which of the following method is used for sorting in merge sort?.

A.  merging.

B.  partitioning.

C.  selection.

D.  exchanging.

Q38. What will be the best case time complexity of merge sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q39. Which of the following is not a variant of merge sort?.

A.  in-place merge sort.

B.  bottom up merge sort.

C.  top down merge sort.

D.  linear merge sort.

Q40. Choose the incorrect statement about merge sort from the following?.

A.  it is a comparison based sort.

B.  it is an adaptive algorithm.

C.  it is not an in place algorithm.

D.  it is stable algorithm.

Q41. Which of the following is not in place sorting algorithm?.

A.  merge sort.

B.  quick sort.

C.  heap sort.

D.  insertion sort.

Q42. Which of the following is not a stable sorting algorithm?.

A.  Quick sort.

B.  Cocktail sort.

C.  Bubble sort.

D.  Merge sort.

Q43. Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?.

A.  Quick sort.

B.  Insertion sort.

C.  Selection sort.

D.  Merge sort.

Q44. Merge sort is preferred for arrays over linked lists..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q45. Which of the following sorting algorithm makes use of merge sort?.

A.  tim sort.

B.  intro sort.

C.  bogo sort.

D.  quick sort.

Q46. Merge sort uses which of the following algorithm to implement sorting?.

A.  backtracking.

B.  greedy algorithm.

C.  divide and conquer.

D.  dynamic programming.

Q47. What is the average case time complexity of standard merge sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q48. What is the auxiliary space complexity of standard merge sort?.

A.  O(1).

B.  O(log n).

C.  O(n).

D.  O(n log n).

Q49. What is the space complexity of in place merge sort?.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q50. Merge sort uses which of the following method to implement sorting?.

A.  merging.

B.  partitioning.

C.  selection.

D.  exchanging.

Q51. Merge sort uses which of the following algorithm to implement sorting?.

A.  backtracking.

B.  greedy algorithm.

C.  divide and conquer.

D.  dynamic programming.

Q52. What is the average case time complexity of standard merge sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q53. What is the auxiliary space complexity of standard merge sort?.

A.  O(1).

B.  O(log n).

C.  O(n).

D.  O(n log n).

Q54. What is the auxiliary space complexity of bottom up merge sort?.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q55. What is the average time complexity of bottom up merge sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q56. Merge sort uses which of the following method to implement sorting?.

A.  merging.

B.  partitioning.

C.  selection.

D.  exchanging.

Q57. Bottom up merge sort uses recursion..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q58. Bottom up merge sort is a stable sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q59. Choose the correct statement about bottom up merge sort from the following?.

A.  bottom up merge sort has greater time complexity than standard merge sort.

B.  bottom up merge sort has lesser time complexity than standard merge sort.

C.  bottom up merge sort saves auxiliary space required on call stack.

D.  bottom up merge sort uses recursion..

Answer=  bottom up merge sort saves auxiliary space required on call stack

Q60. Which of the following sorting algorithms is the fastest?.

A.  Merge sort.

B.  Quick sort.

C.  Insertion sort.

D.  Shell sort.

Q61. Quick sort follows Divide-and-Conquer strategy..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q62. What is the worst case time complexity of a quick sort algorithm?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(log N).

Q63. Which of the following methods is the most effective for picking the pivot element?.

A.  first element.

B.  last element.

C.  median-of-three partitioning.

D.  random element.

Q64. Find the pivot element from the given input using median-of-three partitioning method.8, 1, 4, 9, 6, 3, 5, 2, 7, 0..

A. 8.

B. 7.

C. 9.

D. 6.

Q65. Which is the safest method to choose a pivot element?.

A.  choosing a random element as pivot.

B.  choosing the first element as pivot.

C.  choosing the last element as pivot.

D.  median-of-three partitioning method.

Answer=  choosing a random element as pivot

Q66. What is the average running time of a quick sort algorithm?.

A.  O(N^2).

B.  O(N).

C.  O(N log N).

D.  O(log N).

Q67. Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?.

A.  Merge sort.

B.  Shell sort.

C.  Insertion sort.

D.  Bubble sort.

Q68. Quick sort uses join operation rather than merge operation..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q69. How many sub arrays does the quick sort algorithm divide the entire array into?.

A.  one.

B.  two.

C.  three.

D.  four.

Q70. Which is the worst method of choosing a pivot element?.

A.  first element as pivot.

B.  last element as pivot.

C.  median-of-three partitioning.

D.  random element as pivot.

Q71. Which among the following is the best cut-off range to perform insertion sort within a quick sort?.

A.  N=0-5.

B.  N=5-20.

C.  N=20-30.

D.  N>30.

Q72. Quick sort is a __________.

A.  greedy algorithm.

B.  divide and conquer algorithm.

C.  dynamic programming algorithm.

D.  backtracking algorithm.

Q73. What is the worst case time complexity of the Quick sort?.

A.  O(nlogn).

B.  O(n).

C.  O(n3).

D.  O(n^2).

Q74. Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after first phase, pivot is first element?.

A.  6 4 3 7 11 9 14 12.

B.  6 3 4 7 9 14 11 12.

C.  7 6 14 11 9 4 3 12.

D.  7 6 4 3 9 14 11 12.

Answer=  6 3 4 7 9 14 11 12

Q75. The best case behaviour occurs for quick sort is, if partition splits the array of size n into __________.

A.  n/2 : (n/2) – 1.

B.  n/2 : n/3.

C.  n/4 : 3n/2.

D.  n/4 : 3n/4.

Answer=  n/2 : (n/2) – 1

Q76. Quick sort is a stable sorting algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q77. Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then.

A.  T(n) <= 2 T(n/4) + cn.

B.  T(n) <= T(n/4) + T(3n/4) + cn.

C.  T(n) <= 2 T(3n/4) + cn.

D.  T(n) <= T(n/3) + T(3n/4) + cn.

Answer=  T(n) <= T(n/4) + T(3n/4) + cn

Q78. Consider the Quick sort algorithm which sorts elements in ascending order using the first element as pivot. Then which of the following input sequence will require a maximum number of comparisons when this algorithm is applied on it?.

A.  22 25 56 67 89.

B.  52 25 76 67 89.

C.  22 25 76 67 50.

D.  52 25 89 67 76.

Answer=  22 25 56 67 89

Q79. A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. The minimum time needed to sort 200 elements will be approximately.

A.  60.2 sec.

B.  45.54 sec.

C.  31.11 sec.

D.  20 sec.

Q80. Which one of the following sorting algorithm is best suited to sort an array of 1 million elements?.

A.  Bubble sort.

B.  Insertion sort.

C.  Merge sort.

D.  Quick sort.

Q81. Quick sort is a space-optimised version of ____.

A.  Bubble sort.

B.  Selection sort.

C.  Insertion sort.

D.  Binary tree sort.

Q82. QuickSort can be categorized into which of the following?.

A.  Brute Force technique.

B.  Divide and conquer.

C.  Greedy algorithm.

D.  Dynamic programming.

Q83. What is the worst case complexity of QuickSort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q84. What is a randomized QuickSort?.

A.  The leftmost element is chosen as the pivot.

B.  The rightmost element is chosen as the pivot.

C.  Any element in the array is chosen as the pivot.

D.  A random number is generated which is used as the pivot.

Answer=  Any element in the array is chosen as the pivot

Q85. What is the best case complexity of QuickSort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q86. The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?.

A.  1 and 3.

B.  3 and 1.

C.  2 and 6.

D.  6 and 2.

Q87. What is the average case complexity of QuickSort?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

Q88. The given array is arr = {2,6,1}. What are the pivots that are returned as a result of subsequent partitioning?.

A.  1 and 6.

B.  6 and 1.

C.  2 and 6.

D. 1.

Q89. Which of the following is not true about QuickSort?.

A.  in-place algorithm.

B.  pivot position can be changed.

D.  can be implemented as a stable sort.

Answer=  pivot position can be changed

Q90. Quick sort uses which of the following algorithm to implement sorting?.

A.  backtracking.

B.  greedy algorithm.

C.  divide and conquer.

D.  dynamic programming.

Q91. What is a randomized quick sort?.

A.  quick sort with random partitions.

B.  quick sort with random choice of pivot.

C.  quick sort with random output.

D.  quick sort with random input.

Answer=  quick sort with random choice of pivot

Q92. What is the purpose of using randomized quick sort over standard quick sort?.

A.  so as to avoid worst case time complexity.

B.  so as to avoid worst case space complexity.

C.  to improve accuracy of output.

D.  to improve average case time complexity.

Answer=  so as to avoid worst case time complexity

Q93. What is the auxiliary space complexity of randomized quick sort?.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q94. What is the average time complexity of randomized quick sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q95. Quick sort uses which of the following method to implement sorting?.

A.  merging.

B.  partitioning.

C.  selection.

D.  exchanging.

Q96. Randomized quick sort is an in place sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q97. Randomized quick sort is a stable sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q98. What is the best case time complexity randomized quick sort?.

A.  O(log n).

B.  O(n log n).

C.  O(n^2).

D.  O(n^2 log n).

Q99. Which of the following is incorrect about randomized quicksort?.

A.  it has the same time complexity as standard quick sort.

B.  it has the same space complexity as standard quick sort.

C.  it is an in-place sorting algorithm.

D.  it cannot have a time complexity of O(n^2) in any case..

Answer=  it cannot have a time complexity of O(n^2) in any case.

Q100. What is the worst case time complexity of randomized quicksort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(n^2 log n).

Q101. Quick sort uses which of the following algorithm to implement sorting?.

A.  backtracking.

B.  greedy algorithm.

C.  divide and conquer.

D.  dynamic programming.

Q102. What is the median of three techniques in quick sort?.

A.  quick sort with random partitions.

B.  quick sort with random choice of pivot.

C.  choosing median element as pivot.

D.  choosing median of first, last and middle element as pivot.

Answer=  choosing median of first, last and middle element as pivot

Q103. What is the purpose of using a median of three quick sort over standard quick sort?.

A.  so as to avoid worst case time complexity.

B.  so as to avoid worst case space complexity.

C.  to improve accuracy of output.

D.  to improve average case time complexity.

Answer=  so as to avoid worst case time complexity

Q104. What is the auxiliary space complexity of a median of three quick sort?.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q105. What is the average time complexity of the median of three quick sort?.

A.  O(n log n).

B.  O(n^2).

C.  O(n^2 log n).

D.  O(n log n^2).

Q106. Quick sort uses which of the following method to implement sorting?.

A.  merging.

B.  partitioning.

C.  selection.

D.  exchanging.

Q107. Median of three quick sort is an in place sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q108. Median of three quick sort is a stable sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q109. What is the best case time complexity Median of three quick sort?.

A.  O(log n).

B.  O(n log n).

C.  O(n^2).

D.  O(n^2 log n).

Q110. What will be the pivot for the array arr={8,2,4,9} for making the first partition when a median of three quick sort is implemented?.

A. 8.

B. 2.

C. 4.

D. 9.

Q111. What is the other name for a shell sort algorithm?.

A.  Diminishing increment sort.

B.  Diminishing decrement sort.

C.  Insertion sort.

D.  Selection sort.

Q112. The worst case running time of shell sort, using Shell’s increments is?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q113. Who invented the shell sort algorithm?.

A.  John Von Neumann.

B.  Donald Shell.

C.  Tony Hoare.

D.  Alan Shell.

Q114. Shell sort algorithm is the first algorithm to break the quadratic time barrier..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q115. Shell sort algorithm is an example of?.

A.  External sorting.

B.  Internal sorting.

C.  In-place sorting.

D.  Bottom-up sorting.

Q116. Shell sort uses a sequence called a incrementing sequence to sort the elements..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q117. Which of the following sorting algorithms is closely related to shell sort?.

A.  Selection sort.

B.  Merge sort.

C.  Insertion sort.

D.  Bucket sort.

Q118. Why is Shell sort called as a generalization of Insertion sort?.

A.  Shell sort allows an exchange of far items whereas insertion sort moves elements by one position.

B.  Improved lower bound analysis.

C.  Insertion is more efficient than any other algorithms.

D.  Shell sort performs internal sorting.

Answer=  Shell sort allows an exchange of far items whereas insertion sort moves elements by one position

Q119. Given an array of the following elements 81,94,11,96,12,35,17,95,28,58,41,75,15.What will be the sorted order after 5-sort?.

A.  11,12,15,17,28,35,41,58,75,81,94,95,96.

B.  28,12,11,35,41,58,17,94,75,81,96,95,15.

C.  35,17,11,28,12,41,75,15,96,58,81,94,95.

D.  12,11,15,17,81,94,85,96,28,35,41,58,75.

Q120. Which of the following statements is the basic for loop for a shell sort algorithm?.

A.  for(increment=N/2;increment>0;increment/=2).

B.  for(i=1;i<n;i++).

C.  for(i=n/2;i>=0;i- -).

D.  for(i=0;i< n;i++;numelements- -).

Q121. On how many increment sequences does the worst case analysis of shell sort depends?.

A.  one.

B.  two.

C.  three.

D.  four.

Q122. What is the worst case running time of shell sort using Hibbard’s increments?.

A.  O(N).

B.  O(N^2).

C.  O(N1/2).

D.  O(N3/2).

Q123. What is the general form of Shell’s increments?.

A.  1,2,3,…,n.

B.  1,3,7,….,2k-1.

C.  1,3,5,7,….,k-1.

D.  1,5,10,15,…, k-1.

Q124. What is the worst case analysis of shell sort using Shell’s increments?.

A.  O(N).

B.  O(N^2).

C.  O(N1/2).

D.  O(N3/2).

Q125. What is the worst case analysis of Shell sort using Sedgewick’s increments?.

A.  O(N^2).

B.  O(N3/2).

C.  O(N4/3).

D.  O(N5/4).

Q126. Shell sort is also known as _____________.

A.  diminishing decrement sort.

B.  diminishing increment sort.

C.  partition exchange sort.

D.  diminishing insertion sort.

Q127. Statement 1: Shell sort is a stable sorting algorithm.Statement 2: Shell sort is an in-place sorting algorithm..

A.  Both statements are true.

B.  Statement 2 is true but statement 1 is false.

C.  Statement 2 is false but statement 1 is true.

D.  Both statements are false.

Answer=  Statement 2 is true but statement 1 is false

Q128. Shell sort is applied on the elements 27 59 49 37 15 90 81 39 and the chosen decreasing sequence of increments is (5,3,1). The result after the first iteration will be.

A.  27 59 49 37 15 90 81 39.

B.  27 59 37 49 15 90 81 39.

C.  27 59 39 37 15 90 81 49.

D.  15 59 49 37 27 90 81 39.

Answer=  27 59 39 37 15 90 81 49

Q129. Shell sort is an improvement on ____.

A.  insertion sort.

B.  selection sort.

C.  binary tree sort.

D.  quick sort.

Q130. An array that is first 7-sorted, then 5-sorted becomes _________.

A.  7-ordered.

B.  5-ordered.

C.  both 2-ordered and 5-ordered.

D.  both 7-ordered and 5-ordered.

Q131. If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2k–1) are used in a Shell sort implementation, then the best case time complexity will be ________.

A.  O(nlogn).

B.  O(n).

C.  O(n^2).

D.  O(logn).

Q132. Records R1, R2, R3,.. RN with keys K1, K2, K3,.. KN are said to be h-ordered, if ________.

A.  Ki <= Ki+h for 1<= i*h <= N.

B.  Kh <= Ki+h for 1<= i <= N.

C.  Ki <= Kh for 1<= i <= h.

D.  Ki <= Ki+h for 1<= i <= N-h.

Answer=  Ki <= Ki+h for 1<= i <= N-h

Q133. Shell sort is more efficient than insertion sort if the length of input arrays is small..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q134. Which of the following is true?.

A.  Shell sort’s passes completely sort the elements before going on to the next-smallest gap while Comb sort’s passes do not completely sort the elements.

B.  Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap like in Comb sort.

C.  Comb sort’s passes completely sort the elements before going on to the next-smallest gap like in Shell sort.

D.  Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap while Comb sort’s passes completely sort the elements.

Answer=  Shell sort’s passes completely sort the elements before going on to the next-smallest gap while Comb sort’s passes do not completely sort the elements

Q135. On which algorithm is heap sort based on?.

A.  Fibonacci heap.

B.  Binary tree.

C.  Priority queue.

D.  FIFO.

Q136. In what time can a binary heap be built?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q137. In what position does the array for heap sort contains data?.

A. 0.

B. 1.

C. -1.

D.  anywhere in the array.

Q138. In heap sort, after deleting the last minimum element, the array will contain elements in?.

A.  increasing sorting order.

B.  decreasing sorting order.

C.  tree inorder.

D.  tree preorder.

Q139. What is the typical running time of a heap sort algorithm?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q140. How many arrays are required to perform deletion operation in a heap?.

A. 1.

B. 2.

C. 3.

D. 4.

Q141. What is the time taken to perform a delete min operation?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q142. Heap sort is an extremely stable algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q143. What is the average number of comparisons used in a heap sort algorithm?.

A.  N log N-O(N).

B.  O(N log N)-O(N).

C.  O(N log N)-1.

D.  2N log N + O(N).

Answer=  2N log N + O(N)

Q144. What is the time taken to copy elements to and from two arrays created for deletion?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q145. What is the average number of comparisons used to heap sort a random permutation of N distinct items?.

A.  2N log N-O(N).

B.  2N log N-O(N log N).

C.  2N log N-O(N log log N).

D.  2N log N-O(log N).

Answer=  2N log N-O(N log log N)

Q146. Heap sort is an implementation of ____________ using a descending priority queue..

A.  insertion sort.

B.  selection sort.

C.  bubble sort.

D.  merge sort.

Q147. Which one of the following is false?.

A.  Heap sort is an in-place algorithm.

B.  Heap sort has O(nlogn) average case time complexity.

C.  Heap sort is stable sort.

D.  Heap sort is a comparison-based sorting algorithm.

Answer=  Heap sort is stable sort

Q148. The descending heap property is ___________.

A.  A[Parent(i)] = A[i].

B.  A[Parent(i)] <= A[i].

C.  A[Parent(i)] >= A[i].

D.  A[Parent(i)] > 2 * A[i].

Q149. What is its wort case time complexity of Heap sort?.

A.  O(nlogn).

B.  O(n^2logn).

C.  O(n^2).

D.  O(n3).

Q150. In average case Heap sort is as efficient as the Quick sort..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q151. Which one of the following is a variation of Heap sort?.

A.  Comb sort.

B.  Smooth sort.

C.  Binary tree sort.

D.  Shell sort.

Q152. Introsort algorithm is combination of _____________.

A.  Quick sort and Heap sort.

B.  Quick sort and Shell sort.

C.  Heap sort and Merge sort.

D.  Heap sort and insertion sort.

Answer=  Quick sort and Heap sort

Q153. How many elements can be sorted in O(logn) time using Heap sort?.

A.  O(1).

B.  O(n/2).

C.  O(logn/log(logn)).

D.  O(logn).

Q154. Which of the following sorting algorithm is used by C++ internally?.

A.  quicksort.

B.  introsort.

C.  merge sort.

D.  heap sort.

Q155. Which of the following sorting algorithm is not a constituent of introsort?.

A.  selection sort.

B.  quicksort.

C.  insertion sort.

D.  heap sort.

Q156. Introsort begins sorting the given array by using which of the following sorting algorithm?.

A.  selection sort.

B.  quick sort.

C.  insertion sort.

D.  heap sort.

Q157. Which of the following sorting algorithm is NOT stable?.

A.  Introsort.

B.  Brick sort.

C.  Bubble sort.

D.  Merge sort.

Q158. Which of the following sorting algorithm is in-place?.

A.  intro sort.

B.  merge sort.

C.  counting sort.

Q159. Introsort sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q160. What is the best case time complexity of introsort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q161. What is the worst case time complexity of introsort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q162. What is the average time complexity of introsort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q163. What is the auxiliary space requirement of introsort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q164. Why is heap sort preferred over merge sort for introsort implementation?.

A.  Because heap sort is faster.

B.  Because heap sort requires less space.

C.  Because heap sort is easy to implement.

D.  Because heap sort is easy to understand.

Answer=  Because heap sort requires less space

Q165. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for introsort implementation?.

A.  Because insertion sort is faster and adaptive.

B.  Because insertion sort requires less space.

C.  Because insertion sort is easy to implement.

D.  Because insertion sort is easy to understand.

Q166. What is the cut-off for switching from quick sort to insertion sort in the implementation of introsort?.

A. 4.

B. 8.

C. 16.

D. 32.

Q167. What is the cut-off for switching from quick sort to heap sort in the implementation of introsort?.

A. 16.

B.  n^2.

C.  n log(n).

D.  2 log (n).

Q168. Which of the following sorting algorithm will be preferred when the size of partition is between 16 and 2 log(n) while implementing introsort?.

A.  quick sort.

B.  insertion sort.

C.  heap sort.

D.  merge sort.

Q169. Which of the following is Python’s standard sorting algorithm?.

A.  quick sort.

B.  introsort.

C.  merge sort.

D.  tim sort.

Q170. Which of the following sorting algorithm is a constituent of tim sort?.

A.  selection sort.

B.  quick sort.

C.  merge sort.

D.  heap sort.

Q171. Tim sort begins sorting the given array by using which of the following sorting algorithm?.

A.  selection sort.

B.  quick sort.

C.  insertion sort.

D.  merge sort.

Q172. Which of the following sorting algorithm is stable?.

A.  Tim sort.

B.  Introsort.

C.  Quick sort.

D.  Heap sort.

Q173. Which of the following sorting algorithm is not in-place?.

A.  insertion sort.

B.  tim sort.

C.  quick sort.

D.  intro sort.

Q174. Tim sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q175. What is the best case time complexity of Tim sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q176. What is the average time complexity of Tim sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q177. What is the auxiliary space requirement of Tim sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q178. Which of the following algorithm is implemented internally in java when we use function arrays.sort()?.

A.  intro sort.

B.  quick sort.

C.  tim sort.

D.  merge sort.

Q179. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for Tim sort implementation?.

A.  Because insertion sort is faster and adaptive.

B.  Because insertion sort requires less space.

C.  Because insertion sort is easy to implement.

D.  Because insertion sort is easy to understand.

Q180. In which case will tim sort will work as an insertion sort?.

A.  when no. of elements are less than 64.

B.  when no. of elements are greater than 64.

C.  when no. of elements are less than size of run.

D.  when no. of elements are less than 32.

Answer=  when no. of elements are less than size of run

Q181. What is the usual size of a run in tim sort?.

A. 32.

B.  less than 32.

C.  32-64 depending on size of the array.

D. 64.

Answer=  32-64 depending on size of the array

Q182. Which of the following is an example of parallel sorting technique?.

A.  bogo sort.

B.  sleep sort.

C.  cube sort.

D.  merge sort.

Q183. What is the worst case time complexity of cube sort?.

A.  O(n).

B.  O(log n).

C.  O(n log n).

D.  O(n^2).

Q184. What is the auxiliary space requirement of cube sort?.

A.  O(n).

B.  O(1).

C.  O(log n).

D.  O(n log n).

Q185. What is the best case time complexity of cube sort?.

A.  O(n^2).

B.  O(n).

C.  O(n log n).

D.  O(1).

Q186. What is the average case time complexity of cube sort?.

A.  O(n^2).

B.  O(n log n).

C.  O(log n).

D.  O(n).

Q187. Which of the following algorithm is stable?.

A.  heap sort.

B.  cube sort.

C.  quick sort.

D.  bogosort.

Q188. Cube sort is an in place sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q189. Which of the following is a disadvantage of cube sort?.

A.  high memory overhead for small data.

B.  high memory overhead for any data.

C.  balancing is slow.

D.  Iteration is slow.

Q190. Cube sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q191. Which of the following sorting algorithm uses the method of insertion?.

A.  cube sort.

B.  bubble sort.

C.  quick sort.

D.  selection sort.

Q192. Consider the original array 17 8 12 4 26. How many comparisons are needed to construct the BST on the original array?.

A. 5.

B. 4.

C. 7.

D. 10.

Q193. In binary tree sort, we first construct the BST and then we perform _______ traversal to get the sorted order..

A.  inorder.

B.  postorder.

C.  preorder.

D.  level order.

Q194. What is the worst case time complexity of the binary tree sort?.

A.  O(n).

B.  O(nlogn).

C.  O(n^2).

D.  O(logn).

Q195. What is the best case time complexity of the binary tree sort?.

A.  O(n).

B.  O(nlogn).

C.  O(n^2).

D.  O(logn).

Q196. Binary tree sort is an in-place sorting algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q197. Which of the following is false?.

A.  Binary tree sort and quick sort have same running time.

B.  Binary tree sort used BST as work area.

C.  As the number of elements to sort gets larger, binary tree sort gets more and more efficient.

D.  Both quick sort and binary tree are in place sorting algorithms.

Answer=  Both quick sort and binary tree are in place sorting algorithms

Q198. Which of the following sorting algorithms can be considered as improvement to the binary tree sort?.

A.  Heap sort.

B.  Quick sort.

C.  Selection sort.

D.  Insertion sort.

Q199. Consider the following statements related to the binary tree sort.I. Element can be added gradually as they become availableII. It needs extra memory space.

A.  Statement I is true but Statement II is false.

B.  Both Statement I and Statement II are false.

C.  Both Statement I and Statement II are true.

D.  Statement II is true but Statement I is false.

Answer=  Both Statement I and Statement II are true

Q200. Which of the following is an example of an unstable sorting algorithm?.

A.  cycle sort.

B.  insertion sort.

C.  bubble sort.

D.  merge sort.

Q201. What is the worst case time complexity of cycle sort?.

A.  O(n).

B.  O(log n).

C.  O(n log n).

D.  O(n^2).

Q202. What is the auxiliary space requirement of cycle sort?.

A.  O(n).

B.  O(1).

C.  O(log n).

D.  O(n log n).

Q203. What is the best case time complexity of cycle sort?.

A.  O(n^2).

B.  O(n).

C.  O(n log n).

D.  O(1).

Q204. What is the average case time complexity of cycle sort?.

A.  O(n^2).

B.  O(n log n).

C.  O(log n).

D.  O(n).

Q205. Cycle sort is an adaptive sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q206. Which of the following sorting algorithm is in-place?.

A.  Merge sort.

B.  Cycle sort.

C.  Counting sort.

Q207. Which of the following is an advantage of cycle sort?.

A.  it can sort large arrays efficiently.

B.  it has a low time complexity.

C.  it requires minimal write operations.

D.  it is an adaptive sorting algorithm.

Answer=  it requires minimal write operations

Q208. Cycle sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q209. Which of the following sorting algorithm uses the method of insertion?.

A.  cycle sort.

B.  bubble sort.

C.  quick sort.

D.  selection sort.

Q210. How many write operations will be required to sort the array arr={2,4,3,5,1} using cycle sort?.

A. 4.

B. 5.

C. 6.

D. 3.

Q211. Which of the following algorithm is best suited for the case where swap operation is expensive?.

A.  bubble sort.

B.  cycle sort.

C.  cocktail sort.

D.  merge sort.

Q212. Which of the following is a disadvantage of library sort when compared to insertion sort?.

A.  library sort has greater time complexity.

B.  library sort has greater space complexity.

C.  library sort makes more comparisons.

D.  it has no significant disadvantage.

Answer=  library sort has greater space complexity

Q213. Library sort is an online sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q214. Library sort is a modified version of which of the following sorting algorithm?.

A.  Bubble sort.

B.  selection sort.

C.  insertion sort.

D.  quick sort.

Q215. Which of the following sorting algorithm is stable?.

A.  Selection sort.

B.  Quick sort.

C.  Library sort.

D.  Heap sort.

Q216. Which of the following sorting algorithm requires the use of binary search in their implementation?.

B.  library sort.

C.  odd-even sort.

Q217. Library sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q218. What is the average case time complexity of library sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q219. What is the best case time complexity of library sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q220. What is the worst case time complexity of library sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q221. Which of the following is an alternate name of library sort?.

A.  gapped insertion sort.

B.  binary insertion sort.

C.  recursive insertion sort.

D.  binary gap sort.

Q222. What is the advantage of library sort over insertion sort?.

A.  Library sort has a better average time complexity.

B.  Library sort has a better space complexity.

C.  Library sort has better best case time complexity.

D.  Library has better worst case time complexity.

Answer=  Library sort has a better average time complexity

Q223. What is the auxiliary space complexity of library sort?.

A.  O(n).

B.  O(1).

C.  O(n log n).

D.  O(n^2).

Q224. Which of the following is an adaptive sorting algorithm?.

A.  library sort.

B.  merge sort.

C.  heap sort.

D.  selection sort.

Q225. Which of the following sorting algorithm is not in place?.

A.  library sort.

B.  quick sort sort.

C.  heap sort.

D.  gnome sort.

Q226. Which of the following is not true about library sort?.

A.  it uses binary search and insertion sort in its implementation.

B.  gaps are created between successive elements in order to ensure faster insertion.

C.  array needs to be re balanced after every insertion.

D.  it is an in place sorting algorithm.

Answer=  it is an in place sorting algorithm

Q227. Which of the following is a disadvantage of library sort when compared to insertion sort?.

A.  library sort has greater time complexity.

B.  library sort has greater space complexity.

C.  library sort makes more comparisons.

D.  it has no significant disadvantage.

Answer=  library sort has greater space complexity

Q228. Library sort is an online sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q229. Library sort is a modified version of which of the following sorting algorithm?.

A.  Bubble sort.

B.  selection sort.

C.  insertion sort.

D.  quick sort.

Q230. Which of the following sorting algorithm is stable?.

A.  Selection sort.

B.  Quick sort.

C.  Library sort.

D.  Heap sort.

Q231. Which of the following sorting algorithm requires the use of binary search in their implementation?.

B.  library sort.

C.  odd-even sort.

Q232. Library sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q233. What is the average case time complexity of library sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q234. What is the best case time complexity of library sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q235. What is the worst case time complexity of library sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q236. Which of the following is an alternate name of library sort?.

A.  gapped insertion sort.

B.  binary insertion sort.

C.  recursive insertion sort.

D.  binary gap sort.

Q237. What is the advantage of library sort over insertion sort?.

A.  Library sort has a better average time complexity.

B.  Library sort has a better space complexity.

C.  Library sort has better best case time complexity.

D.  Library has better worst case time complexity.

Answer=  Library sort has a better average time complexity

Q238. What is the auxiliary space complexity of library sort?.

A.  O(n).

B.  O(1).

C.  O(n log n).

D.  O(n^2).

Q239. Which of the following is an adaptive sorting algorithm?.

A.  library sort.

B.  merge sort.

C.  heap sort.

D.  selection sort.

Q240. Which of the following sorting algorithm is not in place?.

A.  library sort.

B.  quick sort sort.

C.  heap sort.

D.  gnome sort.

Q241. Which of the following is not true about library sort?.

A.  it uses binary search and insertion sort in its implementation.

B.  gaps are created between successive elements in order to ensure faster insertion.

C.  array needs to be re balanced after every insertion.

D.  it is an in place sorting algorithm.

Answer=  it is an in place sorting algorithm

Q242. Which one of the following sorting algorithm requires recursion?.

A.  pigeonhole sort.

B.  strand sort.

C.  insertion sort.

D.  counting sort.

Q243. Strand sort is most efficient for data stored in?.

B.  arrays.

C.  trees.

D.  graphs.

Q244. In which of the following case strand sort is most efficient?.

A.  when input array is already sorted.

B.  when input array is reverse sorted.

C.  when input array is large.

D.  when input array is has randomly spread elements.

Q245. What is the auxiliary space complexity of strand sort?.

A.  O(n).

B.  O(1).

C.  O(log n).

D.  O(n log n).

Q246. Which of the following sorting algorithm is not in place?.

A.  quick sort.

B.  strand sort.

C.  cycle sort.

D.  heap sort.

Q247. Strand sort is a comparison based sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q248. Strand sort is a stable sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q249. What is the average time complexity of strand sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(n^2 log n).

Q250. What is the best case time complexity of strand sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(n^2 log n).

Q251. What is the worst case time complexity of strand sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(n^2 log n).

Q252. Strand sort algorithm used which of the following method for sorting a list?.

A.  merging.

B.  selection.

C.  insertion.

D.  partitioning.

Q253. Which of the following is an adaptive sorting algorithm?.

A.  heap sort.

B.  strand sort.

C.  selection sort.

D.  merge sort.

Q254. Cocktail sort is also known as ________________.

A.  bidirectional sort.

B.  bubble sort.

C.  brick sort.

D.  ripple sort.

Q255. Cocktail sort is a variation of _____________.

A.  Bubble sort.

B.  Selection sort.

C.  Insertion sort.

D.  Gnome sort.

Q256. Auxiliary space requirement of cocktail sort is _____________.

A.  O(n).

B.  O(log n).

C.  O(1).

D.  O(n^2).

Q257. Which of the following sorting algorithm is NOT stable?.

A.  Quick sort.

B.  Cocktail sort.

C.  Bubble sort.

D.  Merge sort.

Q258. Which of the following sorting algorithm is in place?.

A.  cocktail sort.

B.  merge sort.

C.  counting sort.

Q259. Cocktail sort is a comparison based sort..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q260. Cocktail sort uses which of the following methods for sorting the input?.

A.  selection.

B.  partitioning.

C.  merging.

D.  exchanging.

Q261. What is the worst case time complexity of cocktail sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q262. What is the best case time complexity of cocktail sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q263. What is the average case time complexity of odd-even sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q264. How many iterations are required to sort the array arr={2,3,4,5,1} using bubble sort and cocktail sort respectively?.

A.  4,2.

B.  5,3.

C.  5,2.

D.  4,3.

Q265. Comb sort is an improved version of _______.

A.  Selection sort.

B.  Bubble sort.

C.  Insertion sort.

D.  Merge sort.

Q266. The gap between two elements being compared shrinks by a factor of _______ after every iteration..

A. 1.1.

B. 1.2.

C. 1.3.

D. 1.4.

Q267. The initial gap between two elements being compared _______.

A.  is equal to number of elements in the array.

B.  is equal to 1.3.

C.  depends on the number of iterations.

D.  depends on the compiler being used.

Answer=  is equal to number of elements in the array

Q268. What is the worst case time complexity of comb sort?.

A.  O(n^2).

B.  O(n log n).

C.  O(n).

D.  O(n^2/2a) (a=number of increment).

Q269. The gap value after 3 iterations in an array with 6 elements will be _______.

A. 4.

B. 3.

C. 2.

D. 1.

Q270. Auxiliary space used by comb sort is _______.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q271. The given array is arr={7,4,5,8,1,2}. The number of iterations required to sort the array using comb sort and bubble sort respectively will be _______.

A.  7 and 8.

B.  5 and 6.

C.  5 and 5.

D.  4 and 5.

Q272. Comb sort is a stable sorting algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q273. What is the best case time complexity of comb sort and bubble sort respectively?.

A.  O(n^2) and O(n log n).

B.  O(n log n) and O(n).

C.  O(n) and O(n^2).

D.  O(n^2/2a) (a=number of increment) and O(n^2).

Answer=  O(n log n) and O(n)

Q274. What is the advantage of comb sort over merge sort?.

A.  Comb sort is an in place sorting algorithm.

B.  Comb sort is a stable sorting algorithm.

C.  Comb sort is more efficient.

Answer=  Comb sort is an in place sorting algorithm

Q275. Gnome sort is also called __________.

A.  Smart sort.

B.  Stupid sort.

C.  Bogo sort.

D.  Special sort.

Q276. How many loops are required to implement gnome sorting algorithm?.

A.  Single loop.

B.  2 nested loops.

C.  3 nested loops.

D.  It does not require any loop.

Q277. Which of the following pair of sorting algorithms are stable?.

A.  gnome sort and quick sort.

B.  merge sort and selection sort.

C.  gnome sort and merge sort.

D.  heap sort and merge sort.

Answer=  gnome sort and merge sort

Q278. Auxiliary space used by gnome sort is _________.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q279. The given array is arr = {1,2,4,3,5}.The number of iterations required to sort the array using gnome sort will be _________.

A. 5.

B. 6.

C. 7.

D. 8.

Q280. Gnome sort uses which of the following method to implement sorting?.

A.  Merging.

B.  Partitioning.

C.  Selection.

D.  Exchanging.

Q281. What is the best case time complexity of gnome sort?.

A.  O(n).

B.  O(n^2).

C.  O(n log n).

D.  O(log n).

Q282. What is the worst case time complexity of gnome sort?.

A.  O(n).

B.  O(n^2).

C.  O(n log n).

D.  O(log n).

Q283. What is the average case time complexity of gnome sort?.

A.  O(n).

B.  O(n^2).

C.  O(n log n).

D.  O(log n).

Q284. Which of the following is not an alternative name of bogosort?.

A.  stupid sort.

B.  permutation sort.

C.  donkey sort.

D.  monkey sort.

Q285. Bogosort works by __________.

A.  generating random permutations of its input.

B.  partitioning the array.

C.  dividing the value of input elements.

D.  generating permutations according to the value of first element of array.

Answer=  generating random permutations of its input

Q286. What is the auxiliary space requirement of bogosort?.

A.  O(n).

B.  O(1).

C.  O(log n).

D.  O(n log n).

Q287. What is the best case time complexity of bogosort?.

A.  O(n^2).

B.  O(n).

C.  O(n log n).

D.  O(1).

Q288. What is the worst case time complexity of bogosort?.

A.  O(n^2).

B.  O(n*n!).

C.  O(infinity).

D.  O(n log n).

Q289. Which of the following sorting algorithm is not stable __________.

A.  insertion sort.

B.  bubble sort.

C.  merge sort.

D.  bogosort.

Q290. Which of the following is an in-place sorting algorithm?.

A.  Merge sort.

B.  Bogosort.

D.  Counting sort.

Q291. Sleep sort should be preferred over bogosort as it has better time complexity..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q292. What is the average case time complexity of bogosort?.

A.  O(n^2).

B.  O(n*n!).

C.  O(infinity).

D.  O(n log n).

Q293. Which of the following header file is a must to implement sleep sort algorithm?.

A.  string.h.

B.  math.hw.

C.  bios.h.

D.  windows.h.

Q294. Sleep sort does not work for ___________.

A.  negative numbers.

B.  large numbers.

C.  small numbers.

D.  positive numbers.

Q295. In how many comparisons does the array arr={1,4,2,3,5} gets sorted if we use sleep sort?.

A. 5.

B. 3.

C. 1.

D. 0.

Q296. Sleep sort works by ___________.

A.  making elements to sleep for a time that is proportional to their magnitude.

B.  making elements to sleep for a time that is inversely proportional to their magnitude.

C.  partitioning the input array.

D.  dividing the value of input elements.

Answer=  making elements to sleep for a time that is proportional to their magnitude

Q297. Sleep sort code cannot compile online because ___________.

A.  it has very high time complexity.

B.  it has very high space complexity.

D.  online compilers are not efficient.

Q298. Time complexity of sleep sort can be approximated to be ___________.

A.  O(n + max(input)).

B.  O(n^2).

C.  O(n log n + max(input)).

D.  O(n log n).

Answer=  O(n log n + max(input))

Q299. Sleep sort can be preferred over which of the following sorting algorithms for large number of input elements?.

A.  Quick sort.

B.  Bubble sort.

C.  Selection sort.

D.  None of the mentioned.

Q300. Auxiliary space requirement of sleep sort is ___________.

A.  O(n).

B.  O(1).

C.  O(max(input)).

D.  O(log n).

Q301. Sleep sort does gives a correct output when ___________.

A.  any input element is negative.

B.  input array is reverse sorted.

C.  any input element is positive.

D.  when there is a very small number to the left of very large number.

Answer=  any input element is positive

Q302. Which of the following sorting algorithm is most closely related to the OS?.

A.  gnome sort.

B.  sleep sort.

D.  bogo sort.

Q303. How many comparisons will be made to sort the array arr={1,5,3,8,2} using pigeonhole sort?.

A. 5.

B. 7.

C. 9.

D. 0.

Q304. Which of the following is a non-comparison sort?.

A.  heap sort.

B.  quick sort.

C.  merge sort.

D.  pigeonhole sort.

Q305. In which of the following case pigeonhole sort is most efficient?.

A.  when range of input is less than number of elements.

B.  when range of input is more than number of elements.

C.  when range of input is comparable to the number of elements.

D.  when the given array is almost sorted.

Answer=  when range of input is comparable to the number of elements

Q306. What is the space complexity of pigeonhole sort (k=range of input)?.

A.  O(n*k).

B.  O(n).

C.  O(k).

D.  O(n+k).

Q307. The auxiliary array used in pigeonhole sorting is called ______________.

A.  bucket.

B.  pigeon.

C.  hole.

D.  pigeonhole.

Q308. Pigeonhole sort is a stable sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q309. Pigeonhole sort is an in place sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q310. What is the average time complexity of pigeonhole sort (k=range of input)?.

A.  O(n).

B.  O(n+k).

C.  O(n^2).

D.  O(n*k).

Q311. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case?.

A.  quick sort.

B.  insertion sort.

C.  pigeonhole sort.

D.  bubble sort.

Q312. Choose the correct statement from the following..

A.  pigeonhole sort is a comparison based sort.

B.  any comparison based sorting can be made stable.

C.  quick sort is not a comparison based sort.

D.  any comparison based sort requires at least O(n^2) time.

Q313. What is the advantage of pigeonhole sort over merge sort?.

A.  pigeonhole sort has lesser time complexity when range is comparable to number of input elements.

B.  pigeonhole sort has lesser space complexity.

C.  counting sort is not a comparison based sorting technique.

Answer=  pigeonhole sort has lesser time complexity when range is comparable to number of input elements

Q314. Which of the following algorithm takes linear time for sorting?.

A.  pigeonhole sort.

B.  heap sort.

C.  comb sort.

D.  cycle sort.

Q315. Which of the following is the distribution sort?.

A.  Heap sort.

B.  Smooth sort.

C.  Quick sort.

Q316. What is the worst case time complexity of LSD radix sort?.

A.  O(nlogn).

B.  O(wn).

C.  O(n).

D.  O(n + w).

Q317. LSD radix sort requires _____ passes to sort N elements..

A.  (w/logR).

B.  N(w/logR).

C.  (w/log(RN)).

D.  (wN/log(N)).

Q318. Which of the following is false?.

A.  LSD radix sort is an integer sorting algorithm.

B.  LSD radix sort is a comparison sorting algorithm.

C.  LSD radix sort is a distribution sort.

D.  LSD radix sort uses bucket sort.

Q319. Which of the following sorting algorithm is stable?.

A.  Heap sort.

B.  Selection sort.

Q320. LSD radix sort is faster than comparison sorts..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q321. Which of the following should be used to sort a huge database on a fixed-length key field?.

A.  Insertion sort.

B.  Merge sort.

D.  Quick sort.

Q322. Which of the following is a combination of LSD and MSD radix sorts?.

D.  Flash sort.

Q323. Which of the following is true for the LSD radix sort?.

A.  works best for variable length strings.

B.  accesses memory randomly.

C.  inner loop has less instructions.

D.  sorts the keys in left-to-right order.

Q324. What is the average time complexity of MSD radix sort (w= bits required to store each key)?.

A.  O(n + w).

B.  O(n.w).

C.  O(n^2).

D.  O(n log n).

Q325. MSD radix sort is an in place sorting algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q326. Which of the following statement is not a stable sorting algorithm?.

C.  Counting sort.

D.  Pigeonhole sort.

A.  Radix sort performs better than quick sort when we have log n bits for every digit.

B.  Radix sort has better cache performance than quick sort.

C.  Radix sort has higher values of constant factor in asymptotic notation.

D.  Radix sort takes more space than quick sort.

A.  radix sort performs better than quick sort when we have log n bits for every digit.

B.  radix sort has lesser space complexity.

C.  radix sort is not a comparison based sorting technique.

D.  radix sort has better cache performance than quick sort.

Answer=  radix sort performs better than quick sort when we have log n bits for every digit

Q329. What will be the order of elements of the array arr = {23, 67, 143, 654, 43} after first iteration of MSD sort is complete?.

A.  23, 43, 67, 143, 654.

B.  23, 67, 43, 143, 654.

C.  23, 67, 143, 654, 43.

D.  23, 143, 43, 654, 67.

Answer=  23, 67, 43, 143, 654

Q330. How many comparisons will be made to sort the array arr={1,5,3,8,2} using counting sort?.

A. 5.

B. 7.

C. 9.

D. 0.

Q331. Which of the following is not an example of non comparison sort?.

A.  bubble sort.

B.  counting sort.

D.  bucket sort.

Q332. Which of the following sorting techniques is most efficient if the range of input data is not significantly greater than a number of elements to be sorted?.

A.  selection sort.

B.  bubble sort.

C.  counting sort.

D.  insertion sort.

Q333. What is the auxiliary space requirement of counting sort?.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n+k) k=range of input.

Q334. It is not possible to implement counting sort when any of the input element has negative value..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q335. Which of the following sorting techniques is stable?.

A.  quick sort.

B.  counting sort.

C.  heap sort.

D.  selection sort.

Q336. Which of the following uses the largest amount of auxiliary space for sorting?.

A.  Bubble sort.

B.  Counting sort.

C.  Quick sort.

D.  Heap sort.

Q337. What is the average time complexity of counting sort?.

A.  O(n).

B.  O(n+k) k=range of input.

C.  O(n^2).

D.  O(n log n).

Q338. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case?.

A.  quick sort.

B.  insertion sort.

C.  counting sort.

D.  gnome sort.

Q339. Which of the following statement is true about comparison based sorting?.

A.  counting sort is a comparison based sort.

B.  any comparison based sorting can be made stable.

C.  bubble sort is not a comparison based sort.

D.  any comparison based sort requires at least O(n^2) time.

Q340. Counting sort is often used as a sub routine for radix sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q341. What is the advantage of counting sort over quick sort?.

A.  counting sort has lesser time complexity when range is comparable to number of input elements.

B.  counting sort has lesser space complexity.

C.  counting sort is not a comparison based sorting technique.

Answer=  counting sort has lesser time complexity when range is comparable to number of input elements

Q342. How many comparisons will be made to sort the array arr={1, 5, 3, 8, 2} using bucket sort?.

A. 5.

B. 7.

C. 9.

D. 0.

Q343. What is the alternate name of bucket sort?.

A.  group sort.

C.  bin sort.

D.  uniform sort.

Q344. Which of the following non-comparison sort can also be considered as a comparison based sort?.

A.  counting sort.

C.  bucket sort.

D.  pigeonhole sort.

Q345. Which of the following is not true about bucket sort?.

A.  It is a non comparison based integer sort.

B.  It is a distribution sort.

C.  It can also be considered as comparison based sort.

D.  It is in place sorting algorithm.

Answer=  It is in place sorting algorithm

Q346. Which of the following affect the time complexity of bucket sort?.

A.  algorithm implemented for sorting individual buckets.

B.  number of buckets used.

C.  distribution of input.

D.  all of the mentioned.

Q347. Bucket sort is most efficient in the case when __________.

A.  the input is non uniformly distributed.

B.  the input is uniformly distributed.

C.  the input is randomly distributed.

D.  the input range is large.

Answer=  the input is uniformly distributed

Q348. Bucket sort is a generalization of which of the following sort?.

B.  Pigeonhole sort.

C.  Counting sort.

Q349. What is the worst case time complexity of bucket sort (k = number of buckets)?.

A.  O(n + k).

B.  O(n.k).

C.  O(n^2).

D.  O(n log n).

Q350. What is the best time complexity of bucket sort (k= number of buckets)?.

A.  O(n + k).

B.  O(n.k).

C.  O(n^2).

D.  O(n log n).

Q351. Which of the following is not necessarily a stable sorting algorithm?.

A.  bucket sort.

B.  counting sort.

C.  merge sort.

D.  pigeonhole sort.

Q352. Bucket sort is an in place sorting algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q353. What is the worst space complexity of bucket sort (k = number of buckets)?.

A.  O(n + k).

B.  O(n.k).

C.  O(n^2).

D.  O(n log n).

Q354. Bead sort is also known as _________.

A.  gravity sort.

B.  strand sort.

C.  abacus sort.

D.  counting sort.

Q355. Which of the following sorting algorithm was inspired by the natural phenomenon of falling objects?.

A.  bogo sort.

B.  heap sort.

D.  strand sort.

Q356. Which of the following sorting algorithm is only applicable to positive integers?.

A.  quick sort.

B.  heap sort.

D.  strand sort.

Q357. What is the auxiliary space complexity of bead sort?.

A.  O(n).

B.  O(1).

C.  O(n^2).

D.  O(n log n).

Q358. Which of the following sorting algorithm is not in place?.

A.  quick sort.

C.  cycle sort.

D.  heap sort.

Q359. Bead sort is a comparison based sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q360. How many comparisons will be required to sort the array arr={5, 4, 7, 1, 9} using bead sort?.

A. 5.

B. 4.

C. 6.

D. 0.

Q361. What is the average time complexity of bead sort (S = sum of input elements)?.

A.  O(n).

B.  O(S).

C.  O(n^2).

D.  O(n log n).

Q362. What is the best case time complexity of bead sort (S = sum of input elements)?.

A.  O(n).

B.  O(S).

C.  O(n^2).

D.  O(n log n).

Q363. What is the worst case time complexity of bead sort (S= sum of input elements)?.

A.  O(n).

B.  O(S).

C.  O(n^2).

D.  O(n log n).

Q364. What is the time complexity for a given pancake sort given it undergoes “n” flip operations?.

A.  O(n).

B.  O(n^2).

C.  O(n3).

D.  O(2n).

Q365. Which operation is most essential to the process of pancake sort?.

A.  Flip the given data.

B.  Find the largest of given data.

C.  Finding the least of given data.

D.  Inserting something into the given data.

Q366. How many flips does the simplest of pancake sorting techniques require?.

A.  3n?3 flips.

B.  2n-4 flips.

C.  2n-3 flips.

D.  3n-2 flips.

Q367. Pancake Sorting appears in which of the following?.

A.  Frequency Scaling.

B.  Storage Virtualization.

C.  Parallel Processing.

D.  Neural Networking.

Q368. In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up _______.

A.  Faced down.

B.  Faced up.

C.  It doesn’t matter.

D.  Both sides are burnt.

Q369. In a computational complexity theory, a problem with decision making is said to be NP-complete when it is both in NP and NP-hard. What does NP mean?.

A.  Non Polynomial time.

B.  Non-deterministic Probabilistic.

C.  Non-deterministic Polynomial time.

D.  Non Probabilistic time.

Q370. When we realize a specific implementation of a pancake algorithm, every move when we find the greatest of the sized array and flipping can be modeled through __________.

A.  Combinations.

B.  Exponential functions.

C.  Logarithmic functions.

D.  Permutations.

Q371. The Pancake Problems (1975, 1979, 1973) did NOT involve which of the following people?.

A.  Bill Gates.

B.  Jacob Goodman.

D.  John Goodman.

Q372. Odd-even sort is also known as ____________.

A.  stupid sort.

B.  smart sort.

C.  brick sort.

D.  bogo sort.

Q373. Odd-even sort is a variation of ___________.

A.  Bubble sort.

B.  Selection sort.

C.  Insertion sort.

D.  Gnome sort.

Q374. Auxiliary space requirement of odd-even sort is ___________.

A.  O(n).

B.  O(log n).

C.  O(1).

D.  O(n^2).

Q375. Which of the following sorting algorithm is NOT stable?.

A.  Quick sort.

B.  Brick sort.

C.  Bubble sort.

D.  Merge sort.

Q376. Odd-even sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q377. Brick sort uses which of the following methods for sorting the input?.

A.  selection.

B.  partitioning.

C.  merging.

D.  exchanging.

Q378. What is the worst case time complexity of odd-even sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q379. What is the best case time complexity of odd-even sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q380. What is the average case time complexity of odd-even sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q381. How many odd and even phases are required respectively to sort the given array using odd-even sort.arr={3,2,3,8,5,6,2,1}..

A.  3,3.

B.  4,4.

C.  3,4.

D.  4,3.

Q382. Which one of the following sorting algorithm requires recursion?.

A.  odd even sort.

B.  stooge sort.

C.  selection sort.

D.  counting sort.

Q383. What is the recurrence relation for stooge sort?.

A.  T(n) = 2T(2/3n) + O(n).

B.  T(n) = 2T(2/3n) + O(1).

C.  T(n) = 3T(2/3n) + O(n).

D.  T(n) = 3T(2/3n) + O(1).

Answer=  T(n) = 3T(2/3n) + O(1)

Q384. In which of the following case stooge sort is most efficient (in terms of time complexity)?.

A.  when input array is already sorted.

B.  when input array is reverse sorted.

C.  when input array is large.

D.  it has the same time complexity in any case.

Answer=  it has the same time complexity in any case

Q385. What is the space complexity of stooge sort?.

A.  O(n).

B.  O(1).

C.  O(log n).

D.  O(n log n).

Q386. What is the first step in the algorithm of stooge sort(after base case)?.

A.  apply stooge sort on first 2/3 elements of array.

B.  apply stooge sort on last 2/3 elements of array.

C.  apply stooge sort on first 1/3 elements of array.

D.  compare first and last element of the array.

Answer=  compare first and last element of the array

Q387. Stooge sort is a comparison based sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q388. Stooge sort is a stable sorting algorithm..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q389. What is the average time complexity of stooge sort?.

A.  O(n^2).

B.  O(n3).

C.  O(n^2.6).

D.  O(n^2.7).

Q390. How many recursive statements are used in the algorithm of stooge sort?.

A. 0.

B. 1.

C. 2.

D. 3.

Q391. Which of the following sorting algorithm has the same time complexity in every case?.

A.  stooge sort.

B.  strand sort.

C.  quick sort.

D.  bubble sort.

Q392. Which of the following sorting algorithm is worst in terms of time complexity?.

A.  bubble sort.

B.  selection sort.

C.  insertion sort.

D.  stooge sort.

Q393. Which of the following is not an adaptive sorting algorithm?.

A.  insertion sort.

B.  strand sort.

C.  stooge sort.

D.  bubble sort.

Q394. Which of the following is not an alternative name of permutation sort?.

A.  stupid sort.

B.  bogo sort.

C.  donkey sort.

D.  monkey sort.

Q395. Permutation sort works by __________.

A.  generating random permutations of its input.

B.  partitioning the array.

C.  dividing the value of input elements.

D.  generating permutations according to the value of first element of array.

Answer=  generating random permutations of its input

Q396. What is the auxiliary space requirement of permutation sort?.

A.  O(n).

B.  O(1).

C.  O(log n).

D.  O(n log n).

Q397. What is the best case time complexity of permutation sort?.

A.  O(n^2).

B.  O(n).

C.  O(n log n).

D.  O(1).

Q398. What is the worst case time complexity of permutation sort?.

A.  O(n^2).

B.  O(n*n!).

C.  O(infinity).

D.  O(n log n).

Q399. Which of the following sorting algorithm is not stable __________.

A.  insertion sort.

B.  bubble sort.

C.  merge sort.

D.  bogosort.

Q400. Which of the following is an in-place sorting algorithm?.

A.  Merge sort.

B.  Permutation sort.

D.  Counting sort.

Q401. Sleep sort should be preferred over permutation sort as it has better time complexity..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q402. What is the average case time complexity of permutation sort?.

A.  O(n^2).

B.  O(n*n!).

C.  O(infinity).

D.  O(n log n).

Q403. Which of the following is an advantage of recursive bubble sort over its iterative version?.

A.  it has better time complexity.

B.  it has better space complexity.

C.  it is easy to implement.

D.  it has no significant advantage.

Q404. Bubble sort is also known as ___________.

A.  stupid sort.

B.  ship sort.

C.  sinking sort.

D.  shell sort.

Q405. What will be the recurrence relation of the code of recursive bubble sort?.

A.  T(n) = 2T(n/2) + n.

B.  T(n) = 2T(n/2) + c.

C.  T(n) = T(n-1) + n.

D.  T(n) = T(n-1) + c.

Answer=  T(n) = T(n-1) + n

Q406. Which of the following sorting algorithm is stable?.

A.  Selection sort.

B.  Quick sort.

C.  Bubble sort.

D.  Heap sort.

Q407. Which of the following is a variation of bubble sort?.

A.  selection sort.

B.  odd even sort.

C.  cocktail sort.

D.  stupid sort.

Q408. Recursive bubble sort is a comparison based sort..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q409. What is the average case time complexity of recursive bubble sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q410. What is the best case time complexity of recursive bubble sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q411. What is the worst case time complexity of recursive bubble sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q412. What are the number of swaps required to sort the array arr={1, 2, 4, 3, 7, 5, 6} using recursive bubble sort?.

A. 0.

B. 1.

C. 2.

D. 3.

Q413. Which of the following data structure is required for the implementation of tree sort?.

A.  any ordinary tree.

B.  balanced tree.

C.  binary search tree.

D.  unbalanced tree.

Q414. Tree sort is an online sorting algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q415. Which of the following traversal in a binary search tree results in a sorted output?.

A.  in order traversal.

B.  pre order traversal.

C.  post order traversal.

Q416. Which of the following sorting algorithm is stable?.

A.  Selection sort.

B.  Quick sort.

C.  Tree sort.

D.  Heap sort.

Q417. Which of the following sorting algorithm uses a binary search tree?.

B.  tree sort.

C.  odd-even sort.

Q418. Which of the following is a comparison based sort?.

A.  tree sort.

C.  counting sort.

D.  pigeonhole sort.

Q419. What is the average case time complexity of tree sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q420. What is the best case time complexity of tree sort?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q421. What is the worst case time complexity of tree sort (when implemented with a balanced tree)?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q422. What is the worst case time complexity of tree sort (when implemented with an unbalanced tree)?.

A.  O(n).

B.  O(n log n).

C.  O(n^2).

D.  O(log n).

Q423. What is the auxiliary space complexity of tree sort?.

A.  O(1).

B.  O(n).

C.  O(log n).

D.  O(n log n).

Q424. In which of the following case does a tree sort become adaptive?.

A.  when implemented with an unbalanced tree.

B.  when implemented with a balanced tree.

C.  when implemented with a splay tree as BST.

D.  when implemented with AVL tree as BST.

Answer=  when implemented with a splay tree as BST

Q425. Which of the following is not true about tree sort?.

A.  it is not an in place sorting algorithm.

B.  its every implementation is adaptive.

C.  it requires in order traversal of BST for sorting input elements.

D.  it is a stable sort.

Q426. Which of the following sorting algorithm is not in place?.

A.  insertion sort.

B.  quick sort.

C.  tree sort.

D.  gnome sort.

Q427. The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q428. Which of the following is not an advantage of tree sort?.

A.  it has a low space complexity.

B.  it has good time complexity for balanced BST.

C.  it is an online sorting algorithm.

D.  it is stable sorting algorithm.

Answer=  it has a low space complexity

Q429. Which of the following version of tree sort will have the highest worst case time complexity?.

A.  using AVL tree as BST.

B.  using red black tree as BST.

C.  using splay tree as BST.

D.  using ordinary BST.

Q430. What is a Rabin and Karp Algorithm?.

A.  String Matching Algorithm.

B.  Shortest Path Algorithm.

C.  Minimum spanning tree Algorithm.

D.  Approximation Algorithm.