DAA_C_MCQ_2

Given two sorted list of size m and n respectively. The number of comparisons needed the worst case by the merge sort algorithm will be

• m X n

• maximum of m and n

• minimum of m and n

• m + n - 1

Let P be a quick sort program to sort numbers in ascending order using the first element as a 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?

• 
  

  t1 = 5

• t1 < t2

• t1 > t2

• t1 = t2

The following code snippet is an example of quick sort. What do the 'low' and 'high' parameters represent in this code?

• The number of comparisons performed

• The range of elements to sort within the array

• The value of the pivot element

• The number of swaps made during sorting

Which of the following is an example of a problem that cannot be solved using the divide and conquer approach?

• Computing the nth Fibonacci number

• Finding the median of two sorted arrays

• Sorting a linked list

• Finding the shortest path between two nodes in a graph

What is the result of the recurrences which fall under the first case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?

• T(n) = O(n^logba)

• T(n) = O(nc log n)

• T(n) = O(f(n))

• T(n) = O(n2)

In Merge Sort, if the input array is already sorted in ascending order, how many times will the Merge function be called during the sorting process?

• n-1

• n

• log n

• 0

When does Heap Sort perform at its worst?

• When the input array is already sorted in ascending order.

• When the input array elements are required to be sorted in reverse order.

• When all elements of the input array are the same.

• When the input array has no duplicate values.

Suppose 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 the root of the heap?

• 1

• 2

• 3 or 4

• 5 or 6

Name:

Roll No: