1
GATE CSE 2015 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C function.
int fun1 (int n) { 
     int i, j, k, p, q = 0; 
     for (i = 1; i < n; ++i) 
     {
        p = 0; 
       for (j = n; j > 1; j = j/2) 
           ++p;  
       for (k = 1; k < p; k = k * 2) 
           ++q;
     } 
     return q;
}
Which one of the following most closely approximates the return value of the function fun1?
A
$$n^3$$
B
$$n{\left( {\log n} \right)^2}$$
C
$$n\log n$$
D
$$n\log \left( {\log n} \right)$$
2
GATE CSE 2015 Set 1
Numerical
+2
-0
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ___________. GATE CSE 2015 Set 1 Algorithms - Greedy Method Question 17 English
Your input ____
3
GATE CSE 2015 Set 1
MCQ (Single Correct Answer)
+1
-0.3
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equations given in the options below, c is a constant.
A
T(n) = 2T(n/2) + cn
B
T(n) = T(n - 1) + T(1) + cn
C
T(n) = 2T(n - 1) + cn
D
T(n) = T(n/2) + cn
4
GATE CSE 2015 Set 1
MCQ (Single Correct Answer)
+1
-0.3
Match the following:

List 1

(P) Prim’s algorithm for minimum spanning tree
(Q) Floyd-Warshall algorithm for all pairs shortest paths
(R) Mergesort
(S) Hamiltonian circuit

List 2

(i) Backtracking
(ii) Greedy method
(iii) Dynamic programming
(iv) Divide and conquer
A
P - iii, Q - ii, R - iv, S - i
B
P - i, Q - ii, R - iv, S - iii
C
P - ii, Q - iii, R - iv, S - i
D
P - ii, Q - i, R - iii, S - iv
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12