GATE CSE 2015 Set 2 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2015 Set 2

MCQ (Single Correct Answer)

-0.3

Consider two decision problems $${Q_1},{Q_2}$$ such that $${Q_1}$$ reduces in polynomial time to $$3$$-$$SAT$$ and $$3$$-$$SAT$$ reduces in polynomial time to $${Q_2}.$$ Then which one of the following is consistent with the above statement?

$${Q_1}$$ is $$NP,$$ $${Q_2}$$ is $$NP$$ hard.

$${Q_2}$$ is $$NP,$$ $${Q_1}$$ is $$NP$$ hard.

Both $${Q_1}$$ and $${Q_2}$$ are in $$NP.$$

Both $${Q_1}$$ and $${Q_2}$$ are $$NP$$ hard.

GATE CSE 2015 Set 2

MCQ (Single Correct Answer)

-0.6

Consider the intermediate code given below.

(1)  i = 1
(2)  j = 1
(3)  t1 = 5 ∗ i
(4)  t2 = t1 + j
(5)  t3 = 4 ∗ t2
(6)  t4 = t3
(7)  a[t4] = -1
(8)  j = j + 1
(9)  if j<=5 goto (3)
(10) i=i+1
(11) if i<5 goto (2)

The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are

5 and 7

6 and 7

5 and 5

7 and 8

GATE CSE 2015 Set 2

MCQ (Single Correct Answer)

-0.3

In the context of abstract-syntax-tree $$(AST)$$ and control-flow-graph $$(CFG),$$ which one of the following is TRUE?

In both $$AST$$ and $$CFG,$$ let node $${N_2}$$ be the successor of node $${N_1}.$$ In the input program, the code corresponding to $${N_2}$$ is present after the code corresponding to $${N_1}$$

For any input program, neither $$AST$$ nor $$CFG$$ will contain a cycle

The maximum number of successors of a node in an $$AST$$ and a $$CFG$$ depends on the input program

Each node in $$AST$$ and $$CFG$$ corresponds to at most one statement in the input program

GATE CSE 2015 Set 2

MCQ (Single Correct Answer)

-0.3

Match the following:

GROUP 1	GROUP 2
P. Lexical analysis	1. Graph coloring
Q. Parsing	2. DFA minimization
R. Register allocation	3. Post-order traversal
S. Expression evaluation	4. Production tree

$$P - 2,\,\,Q - 3,\,\,R - 1,\,\,S - 4$$

$$P - 2,\,\,Q - 1,\,\,R - 4,\,\,S - 3$$

$$P - 2,\,\,Q - 4,\,\,R - 1,\,\,S - 3$$

$$P - 2,\,\,Q - 3,\,\,R - 4,\,\,S - 1$$

PREVIOUS NEXT

GATE CSE Papers

2024