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

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ Quicksort runs in $$\Theta \left( {{n^2}} \right)$$ time
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ Bubblesort runs in $$\Theta \left( {{n^2}} \right)$$ time
$$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ Mergesort runs in $$\Theta \left( n \right)$$ time
$$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$$ Insertion sort runs in $$\Theta \left( n \right)$$ time

$${\rm I}$$ and $${\rm II}$$ only

$${\rm I}$$ and $${\rm III}$$ only

$${\rm II}$$ and $${\rm IV}$$ only

$${\rm I}$$ and $${\rm IV}$$ only

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

Match the following:

GROUP - 1	GROUP - 2
(P) Lexical analysis	(i) Leftmost derivation
(Q) Top down parsing	(ii) Type checking
(R) Semantic analysis	(iii) Regular expressions
(S) Runtime environments	(iv) Activation records

$$P \leftrightarrow i,\,\,Q \leftrightarrow ii,\,\,R \leftrightarrow iv,\,\,S \leftrightarrow iii$$

$$P \leftrightarrow iii,\,\,Q \leftrightarrow i,\,\,R \leftrightarrow ii,\,\,S \leftrightarrow iv$$

$$P \leftrightarrow ii,\,\,Q \leftrightarrow iii,\,\,R \leftrightarrow i,\,\,S \leftrightarrow iv$$

$$P \leftrightarrow iv,\,\,Q \leftrightarrow i,\,\,R \leftrightarrow ii,\,\,S \leftrightarrow iii$$

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.6

Which one of the following grammars is free from $$left$$ $$recursion$$?

$$\eqalign{ & S\,\, \to \,\,AB \cr & A\,\, \to \,\,Aa\,\,|\,\,b \cr & B \to c \cr} $$

$$\eqalign{ & S\,\, \to \,\,AB\,\,|\,\,Bb\,\,|\,\,c \cr & A\,\, \to \,\,Bd\,\,|\,\,\varepsilon \cr & B \to e \cr} $$

$$\eqalign{ & S\,\, \to \,\,Aa\,\,|\,\,B\,\,|\,\, \cr & A\,\, \to \,\,Bd\,\,|\,\,Sc\,\,|\,\,\varepsilon \cr & B \to d \cr} $$

$$\eqalign{ & S\,\, \to \,\,Aa\,\,|\,\,Bb\,\,|\,\,c \cr & A\,\, \to \,\,Bd\,\,|\,\,\varepsilon \cr & B \to Ae\,\,|\,\,\varepsilon \cr} $$

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.6

A student wrote two context-free grammars G1 and G2 for generating a single $$C$$-like array declaration. The dimension of the array is at least one. For example, $$${\mathop{\rm int}} \,\,\,\,\,\,\,a[10]\,\,[3];$$$

The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.

Grammar G1	Grammar G2
D → intL;	D → intL;
L → id[E	L → idE
E → num	E → E[num]
E → num][E	E → [num]

Which of the grammars correctly generate the declaration mentioned above?

Both G1 and G2

Only G1

Only G2

Neither G1 nor G2

PREVIOUS NEXT

GATE CSE Papers

2025