1
GATE CSE 2013
MCQ (Single Correct Answer)
+2
-0.6
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}
What is the worst case time complexity of a sequence of n operations on an initially empty queue?
A
$$\Theta (n)$$
B
$$Θ(n + k)$$
C
$$Θ(nk)$$
D
$$Θ(n^2)$$
2
GATE CSE 2013
MCQ (Single Correct Answer)
+2
-0.6
Consider the following function:
int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }
The return value of the function is
A
$$\Theta ({n^2})$$
B
$$\Theta(n^2\log n)$$
C
$$\Theta(n^3)$$
D
$$\Theta(n^3\log n)$$
3
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
Which of the following statements are TRUE?

1. The problem of determining whether there exists a cycle in an undirected graph is in P.

2. The problem of determining whether there exists a cycle in an undirected graph is in NP.

3. If a problem A is NP−Complete, there exists a non-deterministic polynomial time algorithm to solve A.

A
1 , 2 and 3
B
1 and 2 only
C
2 and 3 only
D
1 and 3 only
4
GATE CSE 2013
MCQ (Single Correct Answer)
+1
-0.3
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production ( i.e., of type $$A \to \varepsilon $$ and $$A \to a$$ ) to parse a string with n tokens?
A
$${n \over 2}$$
B
$$n - 1$$
C
$$2n - 1$$
D
$${2^n}$$
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12