Sorting Interview Questions Part 2

25.Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic.
Ans:C
26. Which of the following is applicable for any constant ‘c’
a.c*log n=O(1)
b.c*log n =O(logn)
c.c*log n =O(nlogn)
d.c*log n =O(n)
Ans:b
27.Which of the following is applicable for any constants‘c,k’
a.c*(n^k)=O(n^k)
b.c*(n^k) =O(logn)
c.c*(n^k) =O(nlogn)
d.c*(n^k) =O(1)
Ans:a
28.The process of combining two or more sorted files into a third sorted file is _____
Ans:merging


29.Which Sort Algorithm has same time complexity as Heap sort in all cases?
a.Merge sort
b.Bubble sort
c.Selection sort
d.none of these
Ans:a


30.Selection sort is faster than bubble sort(T/F)
Ans:True
Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.

31.The worst-case time complexity of heap sort is same as the average-case time complexity of quick sort.
a. True
b. False
Ans. b

32.Which of the following statements is FALSE?
a. Merge Sort is an unstable sort
b. Worst case time complexity of Merge Sort is O(NlogN)
c. Merge Sort takes more space than Quick Sort
d. Average case time complexity of Merge Sort is O(NlogN)
Ans. c

33.Both merge sort and quick sort are in-place sorts.
a. True
b. False
Ans. b

34.Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion

Ans:d
Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.

35.What are the methods available in storing sequential files ?
a.Straight merging,
b.Natural merging,
c.Polyphase sort,
d. all the above
Ans: d

36.An algorithm is made up of 2 modules M1 and M2.If order of M1 is f(n) and M2 is g(n) then the order of the algorithm is
a.max(f(n),g(n))
b.min(f(n),g(n))
c.f(n)+g(n)
d.f(n)*g(n)
Ans:a
By definition of order,there exists constants c1,c2,n1,n2 such that
T(n)<=c1*f(n),for all n>=n1
T(n)<=c2*g(n),for all n>=n2
Let N=max(n1,n2) and C=max(c1,c2),so
T(n)<=c*f(n),for all n>=N
T(n)<=c*g(n),for all n>=N
Adding
T(n)<=c/2 (f(n)+g(n))
Let max(f(n),g(n))=f(n)
T(n)<=c/2 (f(n)+f(n))<=c*f(n)
So order is f(n) which is max(f(n),g(n)) by the assumption.


37.The concept of order (Big O) is important because
a.It can be used to decide the best algorithm that solves a given problem
b.It determines the maximum size of a problem that can be solved in a given system in a given amount of time.
c.it is the lower bound of the growth rate of the algorithm
d. a and b
Ans: d

38.The running time T(n) where n is the input size of a recursive algorithm is
T(n)=c+T(n-1),if n>1
d,if n<=1
The order of the algorithm is
a.n*n b.n c.n^3 d.n^n
Ans:b

By recursively applying the relation we can arrive at
T(n-1)=c(n-1)+d
So,order is n


39.There are four different algorithms A1,A2,A3 and A4 to solve a given problem with the order log(n),loglog(n),nlog(n),n/log(n) respectively.Which is the best algorithm?
a. A1 b.A2 c.A3 d.A4
Ans. b


40.The time complexity of an algorithm T(n),where n is the input size is given by
T(n)=T(n-1)+1/n,if n>1
= 1,otherwise
The order of this algorithm is
a. log n b. n c. n^2 d. n^n
Ans. a