GATE CSE 2009 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

Consider a binary max-heap implemented using an array. What is the content of the array {25, 14, 16, 13, 10, 8, 12} after two delete operations?

{14, 13, 12, 10, 8}

{14, 12, 13, 8, 10}

{14, 13, 8, 12, 10}

{14, 13, 12, 8 10}

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