Algorithm GATE Questions

A highly popular method used to prepare for the GATE Exam is to sincerely practise all the previous years’ GATE Questions to gain perfection. Candidates can practise, analyse and understand concepts while solving them. It will also help you strengthen your time management skills. We have attempted to compile, here in this article, a collection of GATE Questions on Algorithm.

Candidates are urged to practise these Algorithm GATE previous years’ questions to get the best results. Algorithm is an important topic in the GATE CSE question paper, and solving these questions will help the candidates to prepare more proficiently for the GATE exams. Therefore, candidates can find the GATE Questions for Algorithm in this article to solve and practise well before the exams. They can also refer to these GATE previous year question papers and start preparing for the exams.

GATE Questions on Algorithm

1. There are n unsorted arrays: A₁, A₂, …, A_n. Assume that n is odd. Each of A₁, A₂, …, A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁, A₂, …, A_n is ________.

(GATE CSE 2019)

1. O(n)
2. O(nlogn)
3. O(n²logn)
4. O(n²)

Answer (d)

2. 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 ________.

(GATE CSE 2019)

1. 0.08
2. 0.1
3. 1
4. 0

Answer (a)

3. 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 Θ(n2) time

II. Bubblesort runs in Θ(n2) time

III. Mergesort runs in Θ(n) time

IV. Insertion sort runs in Θ(n) time

(GATE CSE 2016 Set 2)

1. I and II only
2. I and III only
3. II and IV only
4. I and IV only

Answer (d)

4. Consider the following array of elements.

〈89,19,50,17,12,15,2,5,7,11,6,9,100〉

The minimum number of interchanges needed to convert it into a max-heap is _______.

(GATE CSE 2015 Set 3)

1. 4
2. 5
3. 2
4. 3

Answer (d)

5. Which one of the following is the recurrence equation for the worst-case time complexity of the Quicksort algorithm for sorting n (≥2) numbers? In the recurrence equations given in the options below, c is a constant.

(GATE CSE 2015 Set 1)

1. T(n) = 2T(n/2) + cn
2. T(n) = T(n-1) + T(1) + cn
3. T(n) = 2T(n-1) + cn
4. T(n) = T(n/2) + cn

Answer (b)

6. A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is _________.

(GATE CSE 2014 Set 2)

1. 10, 8, 7, 3, 2, 1, 5
2. 10, 8, 7, 2, 3, 1, 5
3. 10, 8, 7, 1, 2, 3, 5
4. 10, 8, 7, 5, 3, 2, 1

Answer (a)

7. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is _________.

(GATE CSE 2015 Set 2)

1. Θ(nlogn)
2. Θ(n)
3. Θ(logn)
4. Θ(1)

Answer (d)

8. You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst-case performance is ________.

(GATE CSE 2014 Set 3)

1. Θ(n²)
2. Θ(nlogn)
3. Θ(n)
4. None of the above

Answer (a)

9. Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t₁ and t₂ 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?

(GATE CSE 2014 Set 1)

1. t₁ = 5
2. t₁ < t₂
3. t₁ > t₂
4. t₁ = t₂

Answer (c)

10. Which of the following statement(s) is/are correct regarding the Bellman-Ford shortest path algorithm?

P: Always finds a negative weighted cycle, if one exists.

Q: Finds whether any negative weighted cycle is reachable from the source.

(GATE CSE 2009)

1. P only
2. Q only
3. Both P and Q
4. Neither P nor Q

Answer (b)

11. The usual Θ(n²) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If instead, we use binary search to identify the position, the worst-case running time will __________.

(GATE CSE 2003)

1. Remain Θ(n²)
2. Become Θ(n(logn)²)
3. Become Θ(nlogn)
4. Become Θ(n)

Answer (a)

12. Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst-case complexity of sorting n numbers using randomized quicksort?

(GATE CSE 2001)

1. O(n)
2. O(nlogn)
3. O(n²)
4. O(n!)

Answer (c)

13. If one uses a straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17, then the order of these elements after the second pass of the algorithm is _________.

(GATE CSE 1999)

1. 8, 9, 15, 20, 47, 4, 12, 17, 30, 40
2. 8, 15, 20, 47, 4, 9, 30, 40, 12, 17
3. 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
4. 4, 8, 9, 15, 20, 47, 12, 17, 30, 40

Answer (b)

14. A sorting technique is called stable if __________.

(GATE CSE 1999)

1. It takes O(nlogn) time
2. It maintains the relative order of occurrence of non-distinct elements
3. It uses divide and conquer paradigm
4. It takes O(n) space

Answer (b)

15. For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of _________.

(GATE CSE 1995)

1. O(m)
2. O(n)
3. O(m+n)
4. O(logm + logn)

Answer (c)