Solution for NPTEL, Introduction to Algorithm and Analysis Week 4 MCQs

1.The i^th order statistic of n elements is

A). The i^th smallest element

B). The ith largest element

C). The sum of all elements of the input

D).None

 Ans: A). The  ith  smallest element

2.The naive approach of solving the selection problem using any comparison sorting algorithm (assume that the input is not initially sorted) has a best case time complexity of

A). O(n3)

B). O(log n)

C). O(n.log n)

D). O(n2)

Ans: C). O(n.log n)

3.The worst case run time for RANDOMIZED-SELECT algorithm is

A). Θ(n)

B). Θ(log n)

C). Θ(n. log n)

D). Θ(n2)

Ans: D). Θ(n2)

4.The order of numbers after last three digits of 1256,1134,2331,1970,2901,4526
are sorted using Radix Sort is:

A). 2901,4526,2331,1134,1256,1970

B). 1970,1134,2901,2331,1256,4526

C). 1134,1256,2331,4526,2901,1970

D). None of these

Ans: C). 1134,1256,2331,4526,2901,1970

5. If the input array in counting sort is A=[4 1 3 4 3], then the auxiliary storage C after just two for loops will contain

A). 1 1 2 2

B). 1 0 2 2

C). 1 0 2 0

D). 0 1 2 1

Ans: B). 1 0 2 2

6.Which of the following is true about counting sort?

A). It is stable

B). It is a comparison sort

C). Both of the above

D). None of the above

Ans:  A). It is stable

7.The average case running time for bucket sort , if the input is drawn from uniform distribution, is
A). Θ(log n)

B). Θ(nlog n)

C). Θ(n)

D). Θ(n2)

Ans:C). Θ(n)

8.If the input array in counting sort is A=[5 2 5 4 2 3 1 4], then the auxiliary storage C just after second for loop will contain

A). 1 2 2 1 2

B). 1 2 1 2 2

C). 1 2 2 2 2

D). 1 1 2 2 2

Ans:  B). 1 2 1 2 2

9.Consider Radix sort on the numbers 125,322,534,900,623. After the last digit is sorted, what will be the new order of the numbers?

A). 125,322,534,623,900

B). 322,125,534,623,900

C). 900,322,534,623,125

D). 900,322,623,534,125

Ans: D). 900,322,623,534,125

10.Consider Radix sort on the numbers 325,425,113,223,197,290. After the last two digits are sorted , what will be the new order of the numbers?

B). 113,325,223,425,290,197

C). 223,113,425,290,197,325

D). 113,223,425,325,290,197

Ans:A). 113,223,325,425,290,197

Stay Hackademic , Be Hackademic(Subcribe Hackademic)