GATE CSE 2009 | GATE CSE Year Wise Previous Years Questions

PREVIOUS NEXT

GATE CSE 2009

MCQ (Single Correct Answer)

-0.3

What is the number of swaps required to sort n elements using selection sort, in the worst case?

$$\Theta(n)$$

$$\Theta(n \log n)$$

$$\Theta(n^2)$$

$$\Theta(n^2 \log n)$$

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

The running time of an algorithm is represented by the following recurrence relation:
$$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$
Which one of the following represents the time complexity of the algorithm?

$$\Theta(n)$$

$$\Theta(n \log n)$$

$$\Theta(n^2)$$

$$\Theta(n^2 \log n)$$

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

$$\Theta(n)$$

$$\Theta(n \log n)$$

$$\Theta(n^2)$$

$$\Theta(n^2 \log n)$$

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

Consider the following graph: GATE CSE 2009 Algorithms - Greedy Method Question 24 English

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)

(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)

(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)

(b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

PREVIOUS NEXT

GATE CSE Papers

2024