List of top Questions asked in GATE CS

Consider the following context-free grammar where the start symbol is \(S\) and the set of terminals is \(\{a, b, c, d\}\): \[ S \to AaAb \, | \, BbBa \quad \quad A \to cS \, | \, \epsilon \quad \quad B \to dS \, | \, \epsilon \] The following is a partially-filled LL(1) parsing table. \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline & \(a\) & \(b\) & \(c\) & \(d\) & \(\$\)
\hline \(S\) & \(S \to AaAb\) & \(S \to BbBa\) & (1) & (2) &
\hline \(A\) & \(A \to \epsilon\) & (3) & \(A \to cS\) & &
\hline \(B\) & (4) & \(B \to \epsilon\) & & \(B \to dS\) &
\hline \end{tabular} \end{center} Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table? Note: In the options, "blank" denotes that the corresponding cell is empty.}

Let \(M\) be the 5-state NFA with \(\epsilon\)-transitions shown in the diagram below. \begin{center} \includegraphics[width=0.2\textwidth]{41.png} \end{center} Which one of the following regular expressions represents the language accepted by \(M\)?

Consider an array \(X\) that contains \(n\) positive integers. A subarray of \(X\) is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of \(X\) that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((Q)\). \begin{verbatim} int first=0, second=0, len1=0, len2=0, maxlen=0; for (int i=0; i<n; i++) { if (X[i] == first) { len2++; len1++; } else if (X[i] == second) { len2++; len1 = (P); second = first; } else { len2 = (Q); len1 = 1; second = first; } if (len2>maxlen) { maxlen = len2; } first = X[i]; } \end{verbatim} Which one of the following options gives the CORRECT missing expressions?

Which of the following fields of an IP header is/are always modified by any router before it forwards the IP packet?}

Consider the following C function definition. \begin{verbatim} int fX(char *a){ char *b = a; while(*b) b++; return b - a; } \end{verbatim} Which of the following statements is/are TRUE?

What is the output of the following C program? \begin{verbatim} #include stdio.h int main() { double a[2] = {20.0, 25.0}, *p, *q; p = a; q = p + 1; printf("%d,%d", (int)(q - p), (int)(*q - *p)); return 0; } \end{verbatim}

Which of the following statements is/are FALSE?}

For a Boolean variable \(x\), which of the following statements is/are FALSE?}

An instruction format has the following structure: \begin{center} Instruction Number: Opcode destination reg, source reg-1, source reg-2} \end{center} Consider the following sequence of instructions to be executed in a pipelined processor: I\(_1\): DIV R3, R1, R2
I\(_2\): SUB R5, R3, R4
I\(_3\): ADD R3, R5, R6
I\(_4\): MUL R7, R3, R8 Which of the following statements is/are TRUE?

Consider a process \(P\) running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process \(P\) moving to a non-running state (e.g., ready, blocked)?}

Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?}

Consider the following two sets: \begin{center} \begin{tabular}{|c|l|c|l|} \hline Set X & & Set Y &
\hline P. & Lexical Analyzer & 1. & Abstract Syntax Tree
Q. & Syntax Analyzer & 2. & Token
R. & Intermediate Code Generator & 3. & Parse Tree
S. & Code Optimizer & 4. & Constant Folding
\hline \end{tabular} \end{center} Which one of the following options is the CORRECT match from Set X to Set Y?

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? \begin{center} \includegraphics[width=6cm]{22.png} \end{center}

Node X has a TCP connection open to node Y. The packets from X to Y go through an intermediate IP router R. Ethernet switch S is the first switch on the network path between X and R. Consider a packet sent from X to Y over this connection. Which of the following statements is/are TRUE about the destination IP and MAC addresses on this packet at the time it leaves X?

Consider the following C program. Assume parameters to a function are evaluated from right to left.} \begin{verbatim} #include stdio.h int g(int p) { printf("%d", p); return p; } int h(int q) { printf("%d", q); return q; } void f(int x, int y) { g(x); h(y); } int main() { f(g(10), h(20)); } \end{verbatim} Which one of the following options is the CORRECT output of the above C program?

The format of a single-precision floating-point number as per the IEEE 754 standard is:} \begin{center} \begin{tabular}{|c|c|c|} \hline Sign (1 bit) & Exponent (8 bits) & Mantissa (23 bits)
\hline \end{tabular} \end{center} Choose the largest floating-point number among the following options:

Let \( T(n) \) be the recurrence relation defined as follows: \[ T(0) = 1, \quad T(1) = 2, \quad T(n) = 5T(n-1) - 6T(n-2) \quad \text{for } n \geq 2 \] Which one of the following statements is TRUE?