# GATE CSE 2021 SET-2

 Question 1
Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

Which one of the following options 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
Algorithm   Minimum Spanning Tree
Question 1 Explanation:
 Question 2
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
 A $\Theta (1)$ B $\Theta (\log n)$ C $\Theta ( n)$ D $\Theta (n \log n)$
Data Structure   Heap Tree
Question 2 Explanation:
 Question 3
Consider the following ANSI C program:
int main () {
Integer x;
return 0;
} 
Which one of the following phases in a seven-phase C compiler will throw an error?
 A Lexical analyzer B Syntax analyzer C Semantic analyzer D Machine dependent optimizer
Compiler Design   Syntax-directed Translation
Question 3 Explanation:
 Question 4
The format of the single-precision floating point representation of a real number as per the IEEE 754 standard is as follows:

$\begin{array}{|c|c|c|} \hline \text{sign} & \text{exponent} & \text{mantissa} \\ \hline \end{array}$

Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?
 A exponent = 00000000 and mantissa = 0000000000000000000000000 B exponent = 00000000 and mantissa = 0000000000000000000000001 C exponent = 00000001 and mantissa = 0000000000000000000000000 D exponent = 00000001 and mantissa = 0000000000000000000000001
Digital Logic   Number System
Question 4 Explanation:
 Question 5
Which one of the following circuits implements the Boolean function given below?

$f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6$

where $m_i$ is the $i^{th}$ minterm. A A B B C C D D
Digital Logic   Combinational Circuit
Question 5 Explanation:
 Question 6
Consider the following statements S1 and S2 about the relational data model:

S1: A relation scheme can have at most one foreign key.
S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R.

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
Database Management System   Relational Schema
Question 6 Explanation:
 Question 7
Consider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by P and Q respectively. Suppose P sends a TCP connection request message to Q with a TCP segment having SYN bit =1, SEQ number =X, and ACK bit =0. Suppose Q accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by Q to P?
 A SYN bit =1, SEQ number =X+1, ACK bit =0, ACK number =Y, FIN bit =0 B SYN bit =0, SEQ number =X+1, ACK bit =0, ACK number =Y, FIN bit =1 C SYN bit =1, SEQ number =Y, ACK bit =1, ACK number =X+1, FIN bit =0 D SYN bit =1, SEQ number =Y, ACK bit =1, ACK number =X, FIN bit =0
Computer Network   Transport Layer Protocol
Question 7 Explanation:
 Question 8
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
 A $\Theta (\sqrt{n})$ B $\Theta ( \log _2 (n))$ C $\Theta ( n^2)$ D $\Theta ( n)$
Data Structure   Array
Question 8 Explanation:
 Question 9
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?
 A $L - \{01\}$ B $L \cup \{01\}$ C $\{0,1\}^* -L$ D $L \cdot L$
Theory of Computation   Regular Language
Question 9 Explanation:
 Question 10
Consider the following ANSI C program.
 #include < stdio.h >
int main( )
{
int arr;
int  i, j;
for (i=0; i < 4; i++)
{
for (j=0; j < 5; j++)
{
arr[i][j] = 10 * i + j;
}
}
printf("%d", *(arr+9));
return 0;
}
What is the output of the above program?
 A 14 B 20 C 24 D 30
C Programming   Array and Pointer
Question 10 Explanation:
There are 10 questions to complete. 