1
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
Consider the following recurrence:
$$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$
Which one of the following is true?
A
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(loglogn)}}$$
B
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(logn)}}$$
C
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}\sqrt n {\rm{)}}$$
D
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}n {\rm{)}}$$
2
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-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?
A
$$\theta \,{\rm{(n)}}$$
B
$$\theta \,{\rm{(nlogn)}}$$
C
$$\theta \,{\rm{(n}}{}^2{\rm{)}}$$
D
$$\theta \,{\rm{(n}}{}^3{\rm{)}}$$
3
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-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:
A
n — 1
B
2n — 2
C
$${n \over 2}$$
D
$$n^2$$
4
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-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:
A
Queue
B
Stack
C
Heap
D
B-Tree
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12