# GATE CSE 2022

 Question 1
Which one of the following statements is TRUE for all positive functions $f(n)$?
 A $f(n^2)=\theta (f(n)^2)$, where $f(n)$ is a polynomial B $f(n^2)=o (f(n)^2)$ C $f(n^2)=O (f(n)^2)$, where $f(n)$ is an exponential function D $f(n^2)=\Omega (f(n)^2)$
Algorithm   Asymptotic Notation
Question 1 Explanation:
 Question 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below?

 A ab*bab* + ba*aba* B (ab*b)*ab* + (ba*a)*ba* C (ab*b + ba*a)*(a* + b*) D (ba*a + ab*b)*(ab* + ba*)
Theory of Computation   Finite Automata
Question 2 Explanation:

 Question 3
Which one of the following statements is TRUE?
 A The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict. B Symbol table is accessed only during the lexical analysis phase. C Data flow analysis is necessary for run-time memory management. D LR(1) parsing is sufficient for deterministic context-free languages.
Compiler Design   Parsing
Question 3 Explanation:
 Question 4
In a relational data model, which one of the following statements is TRUE?
 A A relation with only two attributes is always in BCNF. B If all attributes of a relation are prime attributes, then the relation is in BCNF. C Every relation has at least one non-prime attribute. D BCNF decompositions preserve functional dependencies.
Database Management System   Normal Form
Question 4 Explanation:
 Question 5
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
 A The best algorithm for the problem takes $\theta(n)$ time in the worst case. B The best algorithm for the problem takes $\theta(n \log n)$ time in the worst case. C The best algorithm for the problem takes $\theta(n^2)$ time in the worst case. D It is not possible to reverse a singly linked list in O(1) space.