Previously Asked Problems of Searching and Sorting on GATE

Question 1. [GATE-CS-2019]
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ___.

Answer: 0.08

Question 2. [GATE-CS-2016]
Assume 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 Θ(n²) time
II. Bubble sort runs in Θ(n²) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

(A) I and II only
(B) I and III only
(C) II and IV only
(D) I and IV only

Answer: (D) I and IV only

Question 3. [GATE-CS-2015]
Assume 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?

(A) 256
(B) 512
(C) 1024
(D) 2048

Answer: (B) 512

Question 4. [GATE-CS-1996]
The average number of key comparisons done in a successful sequential search in a list of length n is

(A) log n
(B) (n-1)/2
(C) n/2
(D) (n+1)/2

Answer: (D) (n+1)/2

Question 5. [GATE-CS-2006]
Which one of the following in place sorting algorithms needs the minimum number of swaps?

(A) Quick Sort
(B) Insertion Sort
(C) Selection Sort
(D) Heap Sort

Answer: (C) Selection Sort

Question 6. [GATE-CS-1994]
The recurrence relation that can arise in relation to the complexity of the binary search algorithm is:

(A) T(n) = 2T(n/2) + c, where c is constant.
(B) T(n) = T(n/2) + c, where c is constant.
(C) T(n) = T(n/2) + log n.
(D) T(n) = T(n/2) + n.

Answer: (B) T(n) = T(n/2) + c, where c is constant.

Question 7. [GATE-CS-2013]
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)

Answer: (C) O(n)

Question 8. [GATE-CS-2013]
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H, and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on time to compute the sum is 0(na logbn + mc logdn), the value of a + 10b + 100c + 1000d is __.

Answer: 110

Question 9. [GATE-CS-2009]
What is the number of swaps required to sort n elements using selection sort, in the worst case?

(A) O(n)
(B) O(nlogn)
(C) O(n²)
(D) O(n²logn)

Answer: (A) O(n)

Question 10. [GATE-CS-2007]
Which of the following sorting algorithms has the lowest worst-case complexity?

(A) Merge Sort
(B) Bubble Sort
(C) Quick Sort
(D) Selection Sort

Answer: (A) Merge Sort

As you gear up for the GATE Exam 2024, it’s time to dive into the world of searching and sorting algorithms. Think of these algorithms as the super-smart tools that help computers find stuff quickly and organize data neatly. These notes are here to guide you through the ins and outs of these algorithms, breaking down how they work, when to use them, and why they’re essential for acing the GATE exam.