List of top Questions asked in GATE CS

Consider the 5-state DFA \( M \) accepting the language \( L(M) \subseteq (0+1)^* \) shown below. For any string \( w \in (0+1)^* \), let \( n_0(w) \) be the number of \( 0 \)'s in \( w \) and \( n_1(w) \) be the number of \( 1 \)'s in \( w \). \begin{center} \includegraphics[width = 6cm]{50.png} \end{center} Which of the following statements is/are FALSE?
Consider the following C function definition: \begin{verbatim} int f(int x, int y) { for (int i = 0; i<y; i++) { x = x + x + y; } return x; } \end{verbatim} Which of the following statements is/are TRUE about the above function?
Let \( A \) be any \( n \times m \) matrix, where \( m>n \). Which of the following statements is/are TRUE about the system of linear equations \( Ax = 0 \)?
Consider a binary min-heap containing 105 distinct elements. Let \( k \) be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of \( k \) is:
Let \( G \) be a directed graph and \( T \) a depth first search (DFS) spanning tree in \( G \) that is rooted at a vertex \( v \). Suppose \( T \) is also a breadth first search (BFS) tree in \( G \), rooted at \( v \). Which of the following statements is/are TRUE for every such graph \( G \) and tree \( T \)?
The symbol \( \rightarrow \) indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?
Consider a Boolean expression given by \( F(X, Y, Z) = \Sigma(3, 5, 6, 7) \). Which of the following statements is/are CORRECT?
Consider the following read-write schedule \( S \) over three transactions \( T_1, T_2, \text{and } T_3 \), where the subscripts in the schedule indicate transaction IDs: \[ S: r_1(z); w_1(z); r_2(x); r_3(y); w_3(y); r_2(y); w_2(x); w_2(y); \]
Which of the following transaction schedules is/are conflict equivalent to \( S \)?
Consider the following recurrence relation: \[ T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1,
1 & \text{for } n = 1. \end{cases} \] Which one of the following options is CORRECT?
An array \( [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] \) is heapified. Which one of the following options represents the first three elements in the heapified array?
Which of the following fields is/are modified in the IP header of a packet going out of a network address translation (NAT) device from an internal network to an external network?
Consider the circuit shown below where the gates may have propagation delays. Assume that all signal transitions occur instantaneously and that wires have no delays. Which of the following statements about the circuit is/are CORRECT? \begin{center} \includegraphics[width=8cm]{28.png} \end{center}
Consider a 5-stage pipelined processor with Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Register Writeback (WB) stages. Which of the following statements about forwarding is/are CORRECT?
Let \( A \) and \( B \) be two events in a probability space with \( P(A) = 0.3 \), \( P(B) = 0.5 \), and \( P(A \cap B) = 0.1 \). Which of the following statements is/are TRUE?
TCP client \( P \) successfully establishes a connection to TCP server \( Q \). Let \( N_P \) denote the sequence number in the SYN sent from \( P \) to \( Q \). Let \( N_Q \) denote the acknowledgement number in the SYN ACK from \( Q \) to \( P \). Which of the following statements is/are CORRECT?
In a B+ tree, the requirement of at least half-full (50\%) node occupancy is relaxed for which one of the following cases?
Let \( L_1, L_2 \) be two regular languages and \( L_3 \) a language which is not regular. Which of the following statements is/are always TRUE?
Which of the following statements about threads is/are TRUE?
Which of the following statements about a relation \( R \) in first normal form (1NF) is/are TRUE?
Which of the following process state transitions is/are NOT possible?
Which of the following is/are Bottom-Up Parser(s)?
Consider a permutation sampled uniformly at random from the set of all permutations of \( \{1, 2, 3, \dots, n\} \) for some \( n \geq 4 \). Let \( X \) be the event that 1 occurs before 2 in the permutation, and \( Y \) the event that 3 occurs before 4. Which one of the following statements is TRUE?
A user starts browsing a webpage hosted at a remote server. The browser opens a single TCP connection to fetch the entire webpage from the server. The webpage consists of a top-level index page with multiple embedded image objects. Assume that all caches (e.g., DNS cache, browser cache) are all initially empty. The following packets leave the user’s computer in some order: HTTP GET request for the index page DNS request to resolve the web server’s name to its IP address HTTP GET request for an image object TCP SYN to open a connection to the web server Which one of the following is the CORRECT chronological order (earliest in time to latest) of the packets leaving the computer?
Given an integer array of size \( N \), we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is:
Consider the following C program: \begin{verbatim} #include stdio.h int main(){ int a = 6; int b = 0; while(a<10) { a = a / 12 + 1; a += b; } printf("%d", a); return 0; } \end{verbatim} Which one of the following statements is CORRECT?