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).
Answer= 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.
Answer= TRUE
Q3. Which of the following options contain the correct feature of an insertion sort algorithm?.
A. anti-adaptive.
B. dependable.
C. stable, not in-place.
D. stable, adaptive.
Answer= stable, adaptive
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.
Answer= Insertion sort
Q5. For the best case input, the running time of an insertion sort algorithm is?.
A. Linear.
B. Binary.
C. Quadratic.
D. Depends on the input.
Answer= Linear
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.
Answer= Insertion 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).
Answer= O(n^2)
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.
Answer= Insertion Sort
Q11. Consider an array of length 5, arr[5] = {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.
Answer= 4
Q14. Which of the following is not an exchange sort?.
A. Bubble Sort.
B. Quick Sort.
C. Partition-exchange Sort.
D. Insertion Sort.
Answer= 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.
C. It requires additional storage.
D. It requires additional space.
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).
Answer= 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.
Answer= It requires no additional storage space
Q19. What is the average case complexity of selection sort?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= 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.
Answer= It is not scalable
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.
Answer= 5 and 4
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.
Answer= 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).
Answer= 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).
Answer= 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).
Answer= 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.
Answer= Detects whether the input is already sorted
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.
Answer= 4
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).
Answer= O(n)
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.
Answer= 2
Q32. Merge sort uses which of the following technique to implement sorting?.
A. backtracking.
B. greedy algorithm.
C. divide and conquer.
D. dynamic programming.
Answer= divide and conquer
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).
Answer= O(n log n)
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).
Answer= O(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.
Answer= true
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).
Answer= O(n log n)
Q37. Which of the following method is used for sorting in merge sort?.
A. merging.
B. partitioning.
C. selection.
D. exchanging.
Answer= merging
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).
Answer= O(n log n)
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.
Answer= 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.
Answer= it is an adaptive algorithm
Q41. Which of the following is not in place sorting algorithm?.
A. merge sort.
B. quick sort.
C. heap sort.
D. insertion sort.
Answer= merge sort
Q42. Which of the following is not a stable sorting algorithm?.
A. Quick sort.
B. Cocktail sort.
C. Bubble sort.
D. Merge sort.
Answer= Quick 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.
Answer= 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.
Answer= false
Q45. Which of the following sorting algorithm makes use of merge sort?.
A. tim sort.
B. intro sort.
C. bogo sort.
D. quick sort.
Answer= tim 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.
Answer= divide and conquer
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).
Answer= O(n log n)
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).
Answer= O(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).
Answer= O(log n)
Q50. Merge sort uses which of the following method to implement sorting?.
A. merging.
B. partitioning.
C. selection.
D. exchanging.
Answer= merging
Q51. Merge sort uses which of the following algorithm to implement sorting?.
A. backtracking.
B. greedy algorithm.
C. divide and conquer.
D. dynamic programming.
Answer= divide and conquer
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).
Answer= O(n log n)
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).
Answer= O(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).
Answer= O(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).
Answer= O(n log n)
Q56. Merge sort uses which of the following method to implement sorting?.
A. merging.
B. partitioning.
C. selection.
D. exchanging.
Answer= merging
Q57. Bottom up merge sort uses recursion..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
Q58. Bottom up merge sort is a stable sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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.
Answer= Quick sort
Q61. Quick sort follows Divide-and-Conquer strategy..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
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).
Answer= O(N^2)
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.
Answer= median-of-three partitioning
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.
Answer= 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).
Answer= O(N 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.
Answer= Insertion 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.
Answer= true
Q69. How many sub arrays does the quick sort algorithm divide the entire array into?.
A. one.
B. two.
C. three.
D. four.
Answer= two
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.
Answer= first 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.
Answer= N=5-20
Q72. Quick sort is a __________.
A. greedy algorithm.
B. divide and conquer algorithm.
C. dynamic programming algorithm.
D. backtracking algorithm.
Answer= divide and conquer 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).
Answer= 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.
Answer= FALSE
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.
Answer= 31.11 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.
Answer= Quick sort
Q81. Quick sort is a space-optimised version of ____.
A. Bubble sort.
B. Selection sort.
C. Insertion sort.
D. Binary tree sort.
Answer= 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.
Answer= Divide and conquer
Q83. What is the worst case complexity of QuickSort?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= 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).
Answer= O(nlogn)
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.
Answer= 1 and 3
Q87. What is the average case complexity of QuickSort?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= O(nlogn)
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.
Answer= 1
Q89. Which of the following is not true about QuickSort?.
A. in-place algorithm.
B. pivot position can be changed.
C. adaptive sorting algorithm.
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.
Answer= divide and conquer
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).
Answer= O(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).
Answer= O(n log n)
Q95. Quick sort uses which of the following method to implement sorting?.
A. merging.
B. partitioning.
C. selection.
D. exchanging.
Answer= partitioning
Q96. Randomized quick sort is an in place sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
Q97. Randomized quick sort is a stable sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
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).
Answer= O(n 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).
Answer= O(n^2)
Q101. Quick sort uses which of the following algorithm to implement sorting?.
A. backtracking.
B. greedy algorithm.
C. divide and conquer.
D. dynamic programming.
Answer= divide and conquer
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).
Answer= O(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).
Answer= O(n log n)
Q106. Quick sort uses which of the following method to implement sorting?.
A. merging.
B. partitioning.
C. selection.
D. exchanging.
Answer= partitioning
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.
Answer= true
Q108. Median of three quick sort is a stable sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
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).
Answer= O(n 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.
Answer= 8
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.
Answer= Diminishing increment 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).
Answer= O(N^2)
Q113. Who invented the shell sort algorithm?.
A. John Von Neumann.
B. Donald Shell.
C. Tony Hoare.
D. Alan Shell.
Answer= Donald 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.
Answer= TRUE
Q115. Shell sort algorithm is an example of?.
A. External sorting.
B. Internal sorting.
C. In-place sorting.
D. Bottom-up sorting.
Answer= Internal 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.
Answer= TRUE
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.
Answer= Insertion 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.
Answer= 35,17,11,28,12,41,75,15,96,58,81,94,95
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- -).
Answer= for(increment=N/2;increment>0;increment/=2)
Q121. On how many increment sequences does the worst case analysis of shell sort depends?.
A. one.
B. two.
C. three.
D. four.
Answer= three
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).
Answer= 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.
Answer= 1,3,7,….,2k-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).
Answer= O(N^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).
Answer= O(N4/3)
Q126. Shell sort is also known as _____________.
A. diminishing decrement sort.
B. diminishing increment sort.
C. partition exchange sort.
D. diminishing insertion sort.
Answer= diminishing increment 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.
Answer= insertion 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.
Answer= 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).
Answer= O(nlogn)
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.
Answer= FALSE
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.
Answer= Priority queue
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).
Answer= O(N)
Q137. In what position does the array for heap sort contains data?.
A. 0.
B. 1.
C. -1.
D. anywhere in the array.
Answer= 0
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.
Answer= decreasing sorting order
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).
Answer= O(N log N)
Q140. How many arrays are required to perform deletion operation in a heap?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
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).
Answer= O(log N)
Q142. Heap sort is an extremely stable algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(N)
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.
Answer= selection 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].
Answer= A[Parent(i)] >= 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).
Answer= O(nlogn)
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.
Answer= FALSE
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.
Answer= Smooth 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).
Answer= O(logn/log(logn))
Q154. Which of the following sorting algorithm is used by C++ internally?.
A. quicksort.
B. introsort.
C. merge sort.
D. heap sort.
Answer= introsort
Q155. Which of the following sorting algorithm is not a constituent of introsort?.
A. selection sort.
B. quicksort.
C. insertion sort.
D. heap sort.
Answer= selection 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.
Answer= quick sort
Q157. Which of the following sorting algorithm is NOT stable?.
A. Introsort.
B. Brick sort.
C. Bubble sort.
D. Merge sort.
Answer= Introsort
Q158. Which of the following sorting algorithm is in-place?.
A. intro sort.
B. merge sort.
C. counting sort.
D. radix sort.
Answer= intro sort
Q159. Introsort sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(n 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).
Answer= O(n 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).
Answer= O(n 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).
Answer= 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.
Answer= Because insertion sort is faster and adaptive
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.
Answer= 16
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).
Answer= 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.
Answer= quick sort
Q169. Which of the following is Python’s standard sorting algorithm?.
A. quick sort.
B. introsort.
C. merge sort.
D. tim sort.
Answer= 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.
Answer= merge 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.
Answer= insertion sort
Q172. Which of the following sorting algorithm is stable?.
A. Tim sort.
B. Introsort.
C. Quick sort.
D. Heap sort.
Answer= Tim sort
Q173. Which of the following sorting algorithm is not in-place?.
A. insertion sort.
B. tim sort.
C. quick sort.
D. intro sort.
Answer= tim sort
Q174. Tim sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(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).
Answer= O(n 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).
Answer= O(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.
Answer= tim 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.
Answer= Because insertion sort is faster and adaptive
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.
Answer= cube 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).
Answer= O(n log n)
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).
Answer= O(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).
Answer= O(n)
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).
Answer= O(n log n)
Q187. Which of the following algorithm is stable?.
A. heap sort.
B. cube sort.
C. quick sort.
D. bogosort.
Answer= bogosort
Q188. Cube sort is an in place sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
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.
Answer= high memory overhead for small data
Q190. Cube sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
Q191. Which of the following sorting algorithm uses the method of insertion?.
A. cube sort.
B. bubble sort.
C. quick sort.
D. selection sort.
Answer= cube 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.
Answer= 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.
Answer= inorder
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).
Answer= O(n^2)
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).
Answer= O(nlogn)
Q196. Binary tree sort is an in-place sorting algorithm..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= FALSE
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.
Answer= Heap 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.
Answer= cycle 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).
Answer= 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).
Answer= O(1)
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).
Answer= O(n^2)
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).
Answer= O(n^2)
Q205. Cycle sort is an adaptive sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
Q206. Which of the following sorting algorithm is in-place?.
A. Merge sort.
B. Cycle sort.
C. Counting sort.
D. Radix sort.
Answer= Cycle 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.
Answer= true
Q209. Which of the following sorting algorithm uses the method of insertion?.
A. cycle sort.
B. bubble sort.
C. quick sort.
D. selection sort.
Answer= cycle 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.
Answer= 4
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.
Answer= cycle 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.
Answer= true
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.
Answer= insertion sort
Q215. Which of the following sorting algorithm is stable?.
A. Selection sort.
B. Quick sort.
C. Library sort.
D. Heap sort.
Answer= Library sort
Q216. Which of the following sorting algorithm requires the use of binary search in their implementation?.
A. radix sort.
B. library sort.
C. odd-even sort.
D. bead sort.
Answer= library sort
Q217. Library sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(n 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).
Answer= O(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).
Answer= O(n^2)
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.
Answer= gapped insertion 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).
Answer= O(n)
Q224. Which of the following is an adaptive sorting algorithm?.
A. library sort.
B. merge sort.
C. heap sort.
D. selection sort.
Answer= library 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.
Answer= library 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.
Answer= true
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.
Answer= insertion sort
Q230. Which of the following sorting algorithm is stable?.
A. Selection sort.
B. Quick sort.
C. Library sort.
D. Heap sort.
Answer= Library sort
Q231. Which of the following sorting algorithm requires the use of binary search in their implementation?.
A. radix sort.
B. library sort.
C. odd-even sort.
D. bead sort.
Answer= library sort
Q232. Library sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(n 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).
Answer= O(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).
Answer= O(n^2)
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.
Answer= gapped insertion 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).
Answer= O(n)
Q239. Which of the following is an adaptive sorting algorithm?.
A. library sort.
B. merge sort.
C. heap sort.
D. selection sort.
Answer= library 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.
Answer= library 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.
Answer= strand sort
Q243. Strand sort is most efficient for data stored in?.
A. linked list.
B. arrays.
C. trees.
D. graphs.
Answer= linked list
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.
Answer= when input array is already sorted
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).
Answer= O(n)
Q246. Which of the following sorting algorithm is not in place?.
A. quick sort.
B. strand sort.
C. cycle sort.
D. heap sort.
Answer= strand sort
Q247. Strand sort is a comparison based sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
Q248. Strand sort is a stable sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(n^2)
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).
Answer= O(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).
Answer= O(n^2)
Q252. Strand sort algorithm used which of the following method for sorting a list?.
A. merging.
B. selection.
C. insertion.
D. partitioning.
Answer= selection
Q253. Which of the following is an adaptive sorting algorithm?.
A. heap sort.
B. strand sort.
C. selection sort.
D. merge sort.
Answer= strand sort
Q254. Cocktail sort is also known as ________________.
A. bidirectional sort.
B. bubble sort.
C. brick sort.
D. ripple sort.
Answer= ripple sort
Q255. Cocktail sort is a variation of _____________.
A. Bubble sort.
B. Selection sort.
C. Insertion sort.
D. Gnome sort.
Answer= Bubble sort
Q256. Auxiliary space requirement of cocktail sort is _____________.
A. O(n).
B. O(log n).
C. O(1).
D. O(n^2).
Answer= O(1)
Q257. Which of the following sorting algorithm is NOT stable?.
A. Quick sort.
B. Cocktail sort.
C. Bubble sort.
D. Merge sort.
Answer= Quick sort
Q258. Which of the following sorting algorithm is in place?.
A. cocktail sort.
B. merge sort.
C. counting sort.
D. radix sort.
Answer= cocktail sort
Q259. Cocktail sort is a comparison based sort..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
Q260. Cocktail sort uses which of the following methods for sorting the input?.
A. selection.
B. partitioning.
C. merging.
D. exchanging.
Answer= 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).
Answer= O(n^2)
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).
Answer= O(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).
Answer= O(n^2)
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.
Answer= 4,2
Q265. Comb sort is an improved version of _______.
A. Selection sort.
B. Bubble sort.
C. Insertion sort.
D. Merge sort.
Answer= Bubble 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.
Answer= 1.3
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).
Answer= O(n^2)
Q269. The gap value after 3 iterations in an array with 6 elements will be _______.
A. 4.
B. 3.
C. 2.
D. 1.
Answer= 2
Q270. Auxiliary space used by comb sort is _______.
A. O(1).
B. O(n).
C. O(log n).
D. O(n log n).
Answer= O(1)
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.
Answer= 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.
Answer= FALSE
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.
D. It has no advantage.
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.
Answer= Stupid 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.
Answer= Single 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).
Answer= O(1)
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.
Answer= 6
Q280. Gnome sort uses which of the following method to implement sorting?.
A. Merging.
B. Partitioning.
C. Selection.
D. Exchanging.
Answer= 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).
Answer= O(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).
Answer= O(n^2)
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).
Answer= O(n^2)
Q284. Which of the following is not an alternative name of bogosort?.
A. stupid sort.
B. permutation sort.
C. donkey sort.
D. monkey sort.
Answer= donkey 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).
Answer= O(1)
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).
Answer= O(n)
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).
Answer= O(infinity)
Q289. Which of the following sorting algorithm is not stable __________.
A. insertion sort.
B. bubble sort.
C. merge sort.
D. bogosort.
Answer= bogosort
Q290. Which of the following is an in-place sorting algorithm?.
A. Merge sort.
B. Bogosort.
C. Radix sort.
D. Counting sort.
Answer= Bogosort
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.
Answer= false
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).
Answer= O(n*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.
Answer= windows.h
Q294. Sleep sort does not work for ___________.
A. negative numbers.
B. large numbers.
C. small numbers.
D. positive numbers.
Answer= negative 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.
Answer= 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.
C. it requires multithreading process.
D. online compilers are not efficient.
Answer= it requires multithreading process
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.
Answer= 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).
Answer= O(1)
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.
C. radix sort.
D. bogo sort.
Answer= sleep 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.
Answer= 0
Q304. Which of the following is a non-comparison sort?.
A. heap sort.
B. quick sort.
C. merge sort.
D. pigeonhole sort.
Answer= 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).
Answer= O(n+k)
Q307. The auxiliary array used in pigeonhole sorting is called ______________.
A. bucket.
B. pigeon.
C. hole.
D. pigeonhole.
Answer= pigeonhole
Q308. Pigeonhole sort is a stable sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
Q309. Pigeonhole sort is an in place sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
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).
Answer= 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.
Answer= pigeonhole 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.
Answer= any comparison based sorting can be made stable
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.
D. pigeonhole sort is adaptive.
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.
Answer= pigeonhole sort
Q315. Which of the following is the distribution sort?.
A. Heap sort.
B. Smooth sort.
C. Quick sort.
D. LSD radix sort.
Answer= LSD radix 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).
Answer= O(wn)
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)).
Answer= (w/logR)
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.
Answer= LSD radix sort is a comparison sorting algorithm
Q319. Which of the following sorting algorithm is stable?.
A. Heap sort.
B. Selection sort.
C. In-place MSD radix sort.
D. LSD radix sort.
Answer= LSD radix sort
Q320. LSD radix sort is faster than comparison sorts..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= FALSE
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.
C. LSD radix sort.
D. Quick sort.
Answer= LSD radix sort
Q322. Which of the following is a combination of LSD and MSD radix sorts?.
A. Forward radix sort.
B. 3-way radix quick sort.
C. Trie base radix sort.
D. Flash sort.
Answer= Forward radix 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.
Answer= accesses memory randomly
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).
Answer= O(n.w)
Q325. MSD radix sort is an in place sorting algorithm..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= FALSE
Q326. Which of the following statement is not a stable sorting algorithm?.
A. LSD radix sort.
B. MSD radix sort.
C. Counting sort.
D. Pigeonhole sort.
Answer= MSD radix sort
Q327. Which of the following is not true about radix 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.
Answer= Radix sort has better cache performance than quick sort
Q328. What is the advantage of radix sort over 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.
Answer= 0
Q331. Which of the following is not an example of non comparison sort?.
A. bubble sort.
B. counting sort.
C. radix sort.
D. bucket sort.
Answer= bubble 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.
Answer= counting 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.
Answer= 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.
Answer= FALSE
Q335. Which of the following sorting techniques is stable?.
A. quick sort.
B. counting sort.
C. heap sort.
D. selection sort.
Answer= counting 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.
Answer= Counting 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).
Answer= O(n+k) k=range of input
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.
Answer= counting 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.
Answer= any comparison based sorting can be made stable
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.
Answer= true
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.
D. it has no advantage.
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.
Answer= 0
Q343. What is the alternate name of bucket sort?.
A. group sort.
B. radix sort.
C. bin sort.
D. uniform sort.
Answer= bin sort
Q344. Which of the following non-comparison sort can also be considered as a comparison based sort?.
A. counting sort.
B. MSD radix sot.
C. bucket sort.
D. pigeonhole sort.
Answer= bucket 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.
Answer= 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?.
A. LSD radix sort.
B. Pigeonhole sort.
C. Counting sort.
D. MSD radix sort.
Answer= Pigeonhole 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).
Answer= O(n^2)
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).
Answer= O(n + k)
Q351. Which of the following is not necessarily a stable sorting algorithm?.
A. bucket sort.
B. counting sort.
C. merge sort.
D. pigeonhole sort.
Answer= bucket sort
Q352. Bucket sort is an in place sorting algorithm..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= FALSE
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).
Answer= O(n.k)
Q354. Bead sort is also known as _________.
A. gravity sort.
B. strand sort.
C. abacus sort.
D. counting sort.
Answer= gravity sort
Q355. Which of the following sorting algorithm was inspired by the natural phenomenon of falling objects?.
A. bogo sort.
B. heap sort.
C. bead sort.
D. strand sort.
Answer= bead sort
Q356. Which of the following sorting algorithm is only applicable to positive integers?.
A. quick sort.
B. heap sort.
C. bead sort.
D. strand sort.
Answer= bead 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).
Answer= O(n^2)
Q358. Which of the following sorting algorithm is not in place?.
A. quick sort.
B. bead sort.
C. cycle sort.
D. heap sort.
Answer= bead sort
Q359. Bead sort is a comparison based sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
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.
Answer= 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).
Answer= O(S)
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).
Answer= O(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).
Answer= O(S)
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).
Answer= O(n^2)
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.
Answer= Flip 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.
Answer= 2n-3 flips
Q367. Pancake Sorting appears in which of the following?.
A. Frequency Scaling.
B. Storage Virtualization.
C. Parallel Processing.
D. Neural Networking.
Answer= Parallel Processing
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.
Answer= Faced down
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.
Answer= Non-deterministic Polynomial 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.
Answer= Permutations
Q371. The Pancake Problems (1975, 1979, 1973) did NOT involve which of the following people?.
A. Bill Gates.
B. Jacob Goodman.
C. Christos Papadimitriou.
D. John Goodman.
Answer= John Goodman
Q372. Odd-even sort is also known as ____________.
A. stupid sort.
B. smart sort.
C. brick sort.
D. bogo sort.
Answer= brick sort
Q373. Odd-even sort is a variation of ___________.
A. Bubble sort.
B. Selection sort.
C. Insertion sort.
D. Gnome sort.
Answer= Bubble sort
Q374. Auxiliary space requirement of odd-even sort is ___________.
A. O(n).
B. O(log n).
C. O(1).
D. O(n^2).
Answer= O(1)
Q375. Which of the following sorting algorithm is NOT stable?.
A. Quick sort.
B. Brick sort.
C. Bubble sort.
D. Merge sort.
Answer= Quick sort
Q376. Odd-even sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
Q377. Brick sort uses which of the following methods for sorting the input?.
A. selection.
B. partitioning.
C. merging.
D. exchanging.
Answer= 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).
Answer= O(n^2)
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).
Answer= O(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).
Answer= O(n^2)
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.
Answer= 4,4
Q382. Which one of the following sorting algorithm requires recursion?.
A. odd even sort.
B. stooge sort.
C. selection sort.
D. counting sort.
Answer= stooge 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).
Answer= O(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.
Answer= true
Q388. Stooge sort is a stable sorting algorithm..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
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).
Answer= 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.
Answer= 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.
Answer= stooge 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.
Answer= 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.
Answer= stooge 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.
Answer= donkey 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).
Answer= O(1)
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).
Answer= O(n)
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).
Answer= O(infinity)
Q399. Which of the following sorting algorithm is not stable __________.
A. insertion sort.
B. bubble sort.
C. merge sort.
D. bogosort.
Answer= bogosort
Q400. Which of the following is an in-place sorting algorithm?.
A. Merge sort.
B. Permutation sort.
C. Radix sort.
D. Counting sort.
Answer= Permutation 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.
Answer= false
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).
Answer= O(n*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.
Answer= it has no significant advantage
Q404. Bubble sort is also known as ___________.
A. stupid sort.
B. ship sort.
C. sinking sort.
D. shell sort.
Answer= sinking 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.
Answer= Bubble 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.
Answer= odd even sort
Q408. Recursive bubble sort is a comparison based sort..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
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).
Answer= O(n^2)
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).
Answer= O(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).
Answer= O(n^2)
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.
Answer= 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.
Answer= binary search tree
Q414. Tree sort is an online sorting algorithm..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
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.
D. breadth first traversal.
Answer= in order traversal
Q416. Which of the following sorting algorithm is stable?.
A. Selection sort.
B. Quick sort.
C. Tree sort.
D. Heap sort.
Answer= Tree sort
Q417. Which of the following sorting algorithm uses a binary search tree?.
A. radix sort.
B. tree sort.
C. odd-even sort.
D. bead sort.
Answer= tree sort
Q418. Which of the following is a comparison based sort?.
A. tree sort.
B. radix sort.
C. counting sort.
D. pigeonhole sort.
Answer= tree 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).
Answer= O(n 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).
Answer= O(n 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).
Answer= O(n 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).
Answer= O(n^2)
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).
Answer= O(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.
Answer= its every implementation is adaptive
Q426. Which of the following sorting algorithm is not in place?.
A. insertion sort.
B. quick sort.
C. tree sort.
D. gnome sort.
Answer= tree 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.
Answer= FALSE
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.
Answer= 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.
Answer= String Matching Algorithm
Q431. What is the pre-processing time of Rabin and Karp Algorithm?.
A. Theta(m2).
B. Theta(mlogn).
C. Theta(m).
D. Big-Oh(n).
Answer= Theta(m)