# GATE CSE 2021 SET-1

 Question 1
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is NOT necessarily context-free?
 A $L_1\cap L_2$ B $L_1\cdot L_2$ C $L_1 - L_2$ D $L_1\cup L_2$
Theory of Computation   Context Free Language
Question 1 Explanation:
 Question 2
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?
 A $t \gt 2n-2$ B $t \gt 3\lceil \frac{n}{2}\rceil \text{ and } t\leq 2n-2$ C $t \gt n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$ D $t \gt \lceil \log_2(n)\rceil \text{ and } t\leq n$
Data Structure   Array
Question 2 Explanation:
 Question 3
Consider the following three functions.

$f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}}$

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
 A $f_3, f_2, f_1$ B $f_2, f_1, f_3$ C $f_1, f_2, f_3$ D $f_2, f_3, f_1$
Algorithm   Asymptotic Notation
Question 3 Explanation:
 Question 4
Consider the following statements.

S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?
 A S1 is true and S2 is false B S1 is false and S2 is true C S1 is true and S2 is true D S1 is false and S2 is false
Compiler Design   Runtime Environment
Question 4 Explanation:
 Question 5
Consider the following statements.

S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S2: For any context-free grammar, there is a parser that takes at most $O(n^3)$ time to parse a string of length n.

Which one of the following options is correct?
 A S1 is true and S2 is false B S1 is false and S2 is true C S1 is true and S2 is true D S1 is false and S2 is false
Compiler Design   Parsing
Question 5 Explanation:
 Question 6
Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
 A 15 B 21 C D2 D 528
Digital Logic   Number System
Question 6 Explanation:
 Question 7
Let p and q be two propositions. Consider the following two formulae in propositional logic.

$S1: (\neg p\wedge(p\vee q))\rightarrow q$
$S2: q\rightarrow(\neg p\wedge(p\vee q))$

Which one of the following choices is correct?
 A Both S1 and S2 are tautologies. B S1 is a tautology but S2 is not a tautology C S1 is not a tautology but S2 is a tautology D Niether S1 nor S2 is a tautology
Discrete Mathematics   Propositional Logic
Question 7 Explanation:
 Question 8
Consider the following two statements.

Which one of the following choices is correct?
 A Both S1 and S2 are true B S1 is true and S2 is false C S1 is false and S2 is true D Both S1 and S2 are false
Question 8 Explanation:
 Question 9
Consider the following array.

$\begin{array}{|l|l|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline \end{array}$

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
 A Selection sort B Mergesort C Insertion sort D Quicksort using the last element as pivot
Algorithm   Sorting
Question 9 Explanation:
 Question 10
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
 A $\Theta(n\log n)$ B $\Theta(n)$ C $\Theta(\log n)$ D $\Theta(1)$
Data Structure   Binary Search Tree
Question 10 Explanation:
There are 10 questions to complete.