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

1.In Quicksort of the following numbers, if the pivot is chosen as the first element,what will be the order of the numbers after the use of partition function? Assume we are sorting in increasing order.
11 15 9 13 17 7 5 12 6 18

A) 6 7 9 5 11 15 13 12 17 18

B) 6 9 7 5 11 15 13 17 12 18

C) 6 9 7 5 11 15 13 12 17 18

D) 6 5 9 7 11 15 13 12 17 18

 Ans: C) 6 9 7 5 11 15 13 12 17 18

2.What is the max heap property?

A) Value of left child > Value of right child

B) Value of children > Value of parents

C) Value of parent > Value of children

D) Value of right child > Value of left child

Ans: C) Value of parent > Value of children

3.While sorting the following numbers using Quicksort, the last number is chosen as pivot, what will be the permutation of the numbers after the partition function has been applied?
70 48 76 58 43 47 78 53

A) 48 43 47 53 70 76 78 58

B) 43 47 48 53 58 70 76 78

C) 48 47 43 53 70 78 76 58

D) 47 48 43 53 78 76 70 58

Ans: A) 48 43 47 53 70 76 78 58

4.Build the max heap from the following numbers and find the correct order after max heap has been built. Start from node ⌊n2⌋, use the siftdown method
6 2 8 3 14 11 13 9 15

A) 15 9 14 13 6 8 3 11 2

B) 15 14 13 9 6 11 8 2 3

C) 15 14 13 9 8 3 6 11 2

D) 15 14 9 13 6 11 3 8 2

Ans: B) 15 14 13 9 6 11 8 2 3

5. What is the best case time complexity of Quicksort?

A) Θ(n.log n).

B) Θ(n²)

C) Θ(n)

D) Θ(1)

Ans: A) Θ(n.log n).

6.What is the height of a binary heap?

A) O(n)

B) O(n.log n)

C) O( log n)

D) O(n²)

Ans: C) O( log n)

7.What is the recurrence relation of the best case in Quicksort?

A) T(n)=T(n-1)+Θ(n)

B) T(n)=2T(n/2)+ Θ(n)

C) T(n)= T(n/2)+ Θ(n2)

D) T(n)= 2T(n/2)+ Θ(n²)

Ans: B) T(n)=2T(n/2)+ Θ(n)

8.Max heap is built using the following numbers, what will be the new position of 12 and 6,respectively. Assume that the root has position number 1. Start from node⌊n2⌋ , use the siftdown method
12 1 4 8 6 13 9 3

A) 3,5

B) 3,4

C) 3,6

D) 2,6

Ans: A) 3,5

9.Which of the following algorithms is better when dealing with reverse sorted numbers?

A) Quicksort

B) Heapsort

C) Insertion Sort

D) All are equally good

Ans: B) Heapsort

10. ______________ element of an input array is used as pivot in Randomized Quick sort

A) The first

B) The last

C) The median

D) A randomly selected

Ans: D) A randomly selected