GATE CSE 2006 | GATE CSE Year Wise Previous Years Questions

GATE CSE

PREVIOUS NEXT

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the following graph: GATE CSE 2006 Algorithms - Greedy Method Question 29 English

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

$$(a-b),(d-f),(b-f),(d-c),(d-e)$$

$$(a-b),(d-f),(d-c),(b-f),(d-e)$$

$$(d-f),(a-b),(d-c),(b-f),(d-e)$$

$$(d-f),(a-b),(b-f),(d-e),(d-c)$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Queue

Stack

Heap

B-Tree

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i-j|$$. The weight of a minimum spanning tree of G is:

n — 1

2n — 2

$${n \over 2}$$

$$n^2$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

$$\theta \,{\rm{(n)}}$$

$$\theta \,{\rm{(nlogn)}}$$

$$\theta \,{\rm{(n}}{}^2{\rm{)}}$$

$$\theta \,{\rm{(n}}{}^3{\rm{)}}$$

PREVIOUS NEXT

GATE CSE Papers

2024