1
GATE CSE 2005
+2
-0.6
Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor$$ elements each. The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)
A
$$O(n \log \log n)$$
B
$$\Theta(n \log n)$$
C
$$\Omega(n \log n)$$
D
$$\Omega\left(n^{3/2}\right)$$
2
GATE CSE 2005
+2
-0.6
Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:
A
$$O\left( {{{\left| V \right|}^2}} \right)$$
B
$$O\left(|E|+|V|\log |V|\right)$$
C
$$O\left(|V|\log|V|\right)$$
D
$$O\left(\left(|E|+|V|\right)\log|V|\right)$$
3
GATE CSE 2004
+2
-0.6
The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a max Heap. The resultant max Heap is
A B C D 4
GATE CSE 1999
+2
-0.6
If T1 = O(1), give the correct matching for the following pairs:

List - I

(M) Tn = Tn - 1 + n
(N) Tn = Tn/2 + n
(O) Tn = Tn/2 + nlog n
(P) Tn = Tn - 1 + log n

List - II

(U) Tn= O(n)
(V) Tn = O(nlogn)
(W) Tn = O(n2)
(X) Tn = O(log2n)
A
M – W N – V O – U P – X
B
M – W N – U O – X P – V
C
M – V N – W O – X P – U
D
M – W N – U O – V P – X
GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination