GATE CSE 2008 | GATE CSE Year Wise Previous Years Questions

GATE CSE

PREVIOUS NEXT

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

GATE CSE 2008 Algorithms - Greedy Method Question 25 English

Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

only vertex a

only vertices a,e,f,g,h

only vertices a,b,c,d

all the vertices

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

$${\rm{T(n) < = 2T(n/5) + n}}$$

$$T\left( n \right){\rm{ }} < = {\rm{ }}T\left( {n/5} \right){\rm{ }} + {\rm{ }}T\left( {4n/5} \right){\rm{ }} + {\rm{ }}n$$

$$T\left( n \right){\rm{ }} < = {\rm{ }}2T\left( {4n/5} \right){\rm{ }} + {\rm{ }}n$$

$$T\left( n \right){\rm{ }} < = {\rm{ }}2T\left( {n/2} \right){\rm{ }} + {\rm{ }}n$$

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

$$\Theta(\log n)$$

$$\Theta(n)$$

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

$$\Theta(n^2)$$

GATE CSE 2008

MCQ (Single Correct Answer)

-0.3

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is GATE CSE 2008 Algorithms - Searching and Sorting Question 36 English

GATE CSE 2008 Algorithms - Searching and Sorting Question 36 English

MNOPQR

NQMPOR

QMNPRO

QMNPOR

PREVIOUS NEXT

GATE CSE Papers

2024