Quiz
C++ [Sorting Algorithms MCQ | 57 questions]
Create a free account to finish this quiz
Save your progress and see your final score.
Already have an account? Sign in
Questions in this quiz (57)
1What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
- ARecurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
- BRecurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
- CRecurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
- DRecurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
2Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.
- AO(n^2 Logn)
- BO(n^2)
- CO(n Logn Logn)
- DO(nLogn)
3Which of the following is not a stable sorting algorithm in its typical implementation.
- AInsertion Sort
- BMerge Sort
- CQuick Sort
- DBubble Sort
4Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).
- AQuick Sort
- BHeap Sort
- CMerge Sort
- DInsertion Sort
5Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
- AInsertion Sort with time complexity O(kn)
- BHeap Sort with time complexity O(nLogk)
- CQuick Sort with time complexity O(kLogk)
- DMerge Sort with time complexity O(kLogk)
6Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?
- AHeap Sort
- BSelection Sort
- CInsertion Sort
- DMerge Sort
7Which of the following is not true about comparison based sorting algorithms?
- AThe minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array
- BAny comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
- CCounting Sort is not a comparison based sorting algortihm
- DHeap Sort is not a comparison based sorting algorithm.
8Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10- AThe pivot could be either the 7 or the 9.
- BThe pivot could be the 7, but it is not the 9
- CThe pivot is not the 7, but it could be the 9
- DNeither the 7 nor the 9 is the pivot.
9Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28 How many heapify operations have been performed on root of heap?
- A1
- B2
- C3 or 4
- D5 or 6
10What is the best time complexity of bubble sort?
- AN^2
- BNlogN
- CN
- DN(logN)^2
11You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?
- AHeap sort
- BMerge sort
- CQuick sort
- DInsertion sort
12What is the worst case time complexity of insertion sort where position of the data to be inserted is calculated using binary search?
- AN
- BNlogN
- CN^2
- DN(logN)^2
13The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
- AN
- BN^2
- CNlogN
- DN(logN)^2
14In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.
- AN(logN base 3)
- BN(logN base 2/3)
- CN(logN base 1/3)
- DN(logN base 3/2)
15Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
- AInsertion Sort
- BHeap Sort
- CMerge Sort
- DSelection Sort
16A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
- AO (n log n)
- BO (n^2 log n)
- CO (n^2 + log n)
- DO (n^2)
17In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
(A) θ (n)
(B) θ (nLogn)
(C) θ (n^2)
(D) θ (n^2 log n)- AA
- BB
- CC
- DD
18Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then:
- AT(n) <= 2T(n/5) + n
- BT(n) <= T(n/5) + T(4n/5) + n
- CT(n) <= 2T(4n/5) + n
- DT(n) <= 2T(n/2) + n
19Which of the following sorting algorithms has the lowest worst-case complexity?
- AMerge Sort
- BBubble Sort
- CQuick Sort
- DSelection Sort
20Which sorting algorithms is most efficient to sort string consisting of ASCII characters?
- AQuick sort
- BHeap sort
- CMerge sort
- DCounting sort
21The number of elements that can be sorted in θ (logn) time using heap sort is:
- Aθ (1)
- Bθ (√logn)
- Cθ (Logn/LogLogn)
- Dθ (Logn)
22Which of the following is true about merge sort?
- AMerge Sort works better than quick sort if data is accessed from slow sequential memory.
- BMerge Sort is stable sort by nature
- CMerge sort outperforms heap sort in most of the practical situations.
- DAll of the above.
23Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these number in linear time?
- ANot possible to sort in linear time
- BRadix Sort
- CCounting Sort
- DQuick Sort
24In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
- Aθ (n)
- Bθ (nLogn)
- Cθ (n^2)
- Dθ (n^2 log n)
25Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
- AT(n) <= 2T(n/5) + n
- BT(n) <= T(n/5) + T(4n/5) + n
- CT(n) <= 2T(4n/5) + n
- DT(n) <= 2T(n/2) + n
26Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?
- At1 = 5
- Bt1 < t2
- Ct1 > t2
- Dt1 = t2
27You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
- AO(n^2)
- BO(nLogn)
- Cθ (nLogn)
- DO(n^3)
28In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?
- Aθ (n^2)
- Bθ (n log n)
- Cθ (n^1.5)
- Dθ (n)
29Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?
- AO(n)
- BO(n Log n)
- CO(n^2)
- DO(n!)
30Which of the following changes to typical QuickSort improves its performance on average and are generally done in practice.
1) Randomly picking up to make worst case less likely to occur.
2) Calling insertion sort for small sized arrays to reduce recursive calls.
3) QuickSort is tail recursive, so tail call optimizations can be done.
4) A linear time median searching algorithm is used to pick the median, so that the worst case time reduces to O (nLogn)- A1 and 2
- B2, 3, and 4
- C1, 2 and 3
- D2, 3 and 4
31Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.
- AT(n) = 2T (n/2) + cn
- BT(n) = T(n – 1) + T(0) + cn
- CT(n) = 2T (n – 2) + cn
- DT(n) = T(n/2) + cn
32Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
- A256
- B512
- C1024
- D2048
33The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
- AΘ(n log n), Θ(n log n) and Θ(n^2)
- BΘ(n^2), Θ(n^2) and Θ(n Log n)
- CΘ(n^2), Θ(n log n) and Θ(n log n)
- DΘ(n^2), Θ(n log n) and Θ(n^2)
34Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ?
I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time- AI and II only
- BI and III only
- CII and IV only
- DI and IV only
35Assume that we use Bubble Sort to sort n distinct elements in ascending order. When does the best case of Bubble Sort occur?
- AWhen elements are sorted in ascending order
- BWhen elements are sorted in descending order
- CWhen elements are not sorted by any order
- DThere is no best case for Bubble Sort. It always takes O(n*n) time
36If we use Radix Sort to sort n integers in the range (n^k/2,n^k], for some k>0 which is independent of n, the time taken would be?
- AΘ(n)
- BΘ(nlogn)
- CΘ(kn)
- DΘ(n^2)
37Consider an array of elements arr[5]= {5,4,3,2,1} , what are the steps of insertions done while doing insertion sort in the array.
- A4 5 3 2 1 3 4 5 2 1 2 3 4 5 1 1 2 3 4 5
- B5 4 3 1 2 5 4 1 2 3 5 1 2 3 4 1 2 3 4 5
- C4 3 2 1 5 3 2 1 5 4 2 1 5 4 3 1 5 4 3 2
- D4 5 3 2 1 2 3 4 5 1 3 4 5 2 1 1 2 3 4 5
38Which is the correct order of the following algorithms with respect to their time Complexity in the best case ?
- AMerge sort > Quick sort >Insertion sort > selection sort
- Binsertion sort < Quick sort < Merge sort < selection sort
- CMerge sort > selection sort > quick sort > insertion sort
- DMerge sort > Quick sort > selection sort > insertion sort
39Which of the following statements is correct with respect to insertion sort ?
*Online - can sort a list at runtime
*Stable - doesn't change the relative order of elements with equal keys.- AInsertion sort is stable, online but not suited well for large number of elements.
- BInsertion sort is unstable and online
- CInsertion sort is online and can be applied to more than 100 elements
- DInsertion sort is stable & online and can be applied to more than 100 elements
40Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the insertion sort when element 1 reaches the first position of the array ?
- A50
- B25
- C75
- D100
41The auxiliary space of insertion sort is O(1), what does O(1) mean ?
- AThe memory (space) required to process the data is not constant.
- BIt means the amount of extra memory Insertion Sort consumes doesn't depend on the input. The algorithm should use the same amount of memory for all inputs.
- CIt takes only 1 kb of memory .
- DIt is the speed at which the elements are traversed.
42What is the best sorting algorithm to use for the elements in array are more than 1 million in general?
- AMerge sort.
- BBubble sort.
- CQuick sort.
- DInsertion sort.
43Which of the below given sorting techniques has highest best-case runtime complexity.
- AQuick sort
- BSelection sort
- CInsertion sort
- DBubble sort
44A sorting technique is called stable if:
- AIt takes O(nlog n)time
- BIt maintains the relative order of occurrence of non-distinct elements
- CIt uses divide and conquer paradigm
- DIt takes O(n) space
45If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after the second pass of the algorithm is:
- A8, 9, 15, 20, 47, 4, 12, 17, 30, 40
- B8, 15, 20, 47, 4, 9, 30, 40, 12, 17
- C15, 20, 47, 4, 8, 9, 12, 30, 40, 17
- D4, 8, 9, 15, 20, 47, 12, 17, 30, 40
46Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,
(i) 1, 2, 3,......., n
(ii) n, n-1, n-2,......, 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,- AC1 < C2
- BC1 > C2
- CC1 = C2
- DWe cannot say anything for arbitrary n
47A sorting technique is called stable if
- AIf it takes O(n log n) time
- BIt uses divide and conquer technique
- CRelative order of occurrence of non-distinct elements is maintained
- DIt takes O(n) space
48Quick sort is run on 2 inputs shown below to sort in ascending order
A. 1, 2, 3……n
B. n, n – 1, n – 2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then- AC1 > C2
- BC1 = C2
- CC1 < C2
- DCannot say anything for arbitrary n
49You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences,each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. The lower bound on the number of comparisons needed to solve this variant of the sorting problem is
- AΩ (n)
- BΩ (n/k)
- CΩ (nlogk )
- DΩ (n/klogn/k)
50Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ?
- AInsertion – 0(1), Deletion – 0(1), Maximum – 0(1), Minimum – 0(l)
- BInsertion – 0(1), Deletion – 0(1), Maximum – 0(n), Minimum – 0(n)
- CInsertion – 0(n), Deletion – 0(n), Maximum – 0(1), Minimum – 0(1)
- DInsertion – 0(n), Deletion – 0(n), Maximum – 0(n), Minimum – 0(n)
51Consider the following sorting algorithms.
I. Quicksort
II. Heapsort
III. Mergesort
Which of them perform in least time in the worst case?- AI and II only
- BII and III only
- CIII only
- DI, II and III
52Which of the following algorithms sort n integers, having the range 0 to (n^2 - 1), in ascending order in O(n) time ?
- ASelection sort
- BBubble sort
- CRadix sort
- DInsertion sort
53Which one of the following in place sorting algorithms needs the minimum number of swaps?
- AQuick sort
- BInsertion sort
- CSelection sort
- DHeap sort
54Which of the following algorithm design technique is used in merge sort?
- AGreedy method
- BBacktracking
- CDynamic programming
- DDivide and Conquer
55Selection sort algorithm design technique is an example of
- AGreedy method
- BDivide-and-conquer
- CDynamic Programming
- DBacktracking
56The average case and worst case complexities for Merge sort algorithm are
- AO ( n^2 ), O ( n^2 )
- BO ( n^2 ), O ( n log2n )
- CO ( n log2n ), O ( n^2)
- DO ( n log2n ), O ( n log2n )
57You have to sort a list L, consisting of a sorted list followed by a few ‘random’ elements. Which of the following sorting method would be most suitable for such a task?
- ABubble sort
- BSelection sort
- CQuick sort
- DInsertion sort
Information
- Description
- Hell on Earth Complex Testing [KTA; Master Degree Enrollment Preparation] Quiz on C++ [Sorting Algorithms MCQ | 57 questions], created by Good Guy Beket on 11/08/2019.
- Author
- Good Guy Beket
- Language
- English
- Views
- 75
- Tags
- Rating
- No ratings yet Rate this quiz