List of top Questions asked in GATE CS

Consider the pushdown automaton (PDA) $P$ over input alphabet $\{a,b\}$ and stack alphabet $\{\perp, A\}$ with start state $s$ and acceptance by empty stack.
The transition sketch shows:
- In $s$ on each $a$ it pushes one $A$ (i.e., $a/\perp \to A\perp$ and $a/A \to AA$).
- On the first $b$ it goes to $p$ with $b/A \to \epsilon$ and stays in $p$ popping one $A$ per $b$ ($b/A \to \epsilon$).
- From $p$ it may go to $q$ by $\epsilon/A \to \epsilon$, and in $q$ it can keep popping $A$’s and finally pop $\perp$ by $\epsilon/\perp \to \epsilon$.
Question: Which option describes $L(P)$? IMAGE8

Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?

Consider the following program:

int main() {
    f1();
    f2(2);
    f3();
    return(0);
}

int f1() {
    f1();
    return(1);
}

int f2(int X) {
    f3();
    if (X==1)
        return f1();
    else
        return (X * f2(X-1));
}

int f3() {
    return(5);
}

Which one of the following options represents the activation tree corresponding to the main function?

Let $A$ be the adjacency matrix of the given graph with vertices $\{1,2,3,4,5\}$.

Let $\lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5$ be the eigenvalues of $A$ (not necessarily distinct). Find: \[ \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 \;=\; \_\_\_\_\_\_ . \]

The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure. Match the functional equivalence of this circuit to one of the following options.

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: \[ \text{letter} \;\;\rightarrow\;\; [A\!-\!Za\!-\!z] \] \[ \text{digit} \;\;\rightarrow\;\; [0\!-\!9] \] \[ \text{id} \;\;\rightarrow\;\; \text{letter (letter | digit)}^* \] Which one of the following Non-deterministic Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state).

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet $\{0, 1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state.

Which one of the following regular expressions correctly describes the language accepted by A?

Which one of the options best describes the transformation of the 2-dimensional figure P to Q, and then to R, as shown?

Let $U = \{1,2,\ldots,n\}$ with $n > 1000$. Let $k < n$ be a positive integer. Let $A,B \subseteq U$ with $|A| = |B| = k$ and $A \cap B = \varnothing$. A permutation of $U$ separates $A$ from $B$ if either all members of $A$ appear before any member of $B$, or all members of $B$ appear before any member of $A$.

How many permutations of $U$ separate $A$ from $B$?

An 8-way set associative cache of size 64 KB (1 KB = 1024 bytes) is used in a system with a 32-bit address. The address is sub-divided into TAG, INDEX, and BLOCK OFFSET. Find the number of bits in the TAG.

Let $U = \{1,2,3\}$. Let $2^U$ denote the power set of $U$. Consider an undirected graph $G$ whose vertex set is $2^U$. For any $A,B \in 2^U$, $(A,B)$ is an edge in $G$ iff (i) $A \neq B$, and (ii) either $A \subset B$ or $B \subset A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a BFS starting from $A$ is denoted by $\mathcal{B}(A)$. If $\varnothing$ denotes the empty set, find $|\mathcal{B}(\varnothing)|$.

Consider the two-dimensional array D[128][128] in C, stored in row-major order. Each physical page frame holds 512 elements of D. There are 30 physical page frames. The following code executes:

for (int i = 0; i<128; i++)
    for (int j = 0; j<128; j++)
        D[j][i] *= 10;

The number of page faults generated during this execution is:

A computer uses 57-bit virtual addresses with multi-level tree-structured page tables (L levels). Page size = 4 KB and each page-table entry (PTE) = 8 bytes. Find $L$.

Consider a sequence $a$ of elements $a_0=1,\,a_1=5,\,a_2=7,\,a_3=8,\,a_4=9,\,a_5=2$. The following operations are performed on a stack $S$ and a queue $Q$, both initially empty. [I:] push the elements of $a$ from $a_0$ to $a_5$ (in that order) into $S$.
[II:] enqueue the elements of $a$ from $a_0$ to $a_5$ (in that order) into $Q$.
[III:] pop an element from $S$.
[IV:] dequeue an element from $Q$.
[V:] pop an element from $S$.
[VI:] dequeue an element from $Q$.
[VII:] dequeue an element from $Q$ and push the same element into $S$.
[VIII:] Repeat operation VII three times.
[IX:] pop an element from $S$.
[X:] pop an element from $S$.

Consider the table Student with attributes (rollNum, name, gender, marks). The primary key is rollNum. The SQL query is:

SELECT *
FROM Student
WHERE gender = 'F' AND marks > 65;

The number of rows returned by this query is:

A new reliable byte-stream protocol (myTCP) runs over a 100 Mbps network with RTT = 150 ms and maximum segment lifetime (MSL) = 2 minutes. Which of the following are valid sequence number field lengths?

Let $X$ be a set and $2^{X}$ denote the power set of $X$. Define a binary operation $\,\Delta\,$ on $2^{X}$ by $A \Delta B = (A-B)\cup(B-A)$ (symmetric difference). Let $H=(2^{X},\Delta)$. Which of the following statements about $H$ is/are correct?

Suppose in a web browser you click on www.gate-2023.in. The browser cache is empty. The DNS address is not cached, so an iterative DNS lookup across 3 tiers is required. Let RTT denote the round trip time between your host and either a DNS server or the web server. RTT between local host and web server is also equal to RTT. The HTML page is very small and references 10 small objects from the same server. Neglect transmission and rendering time. Which of the following statements is/are CORRECT about the minimum elapsed time between clicking the URL and full rendering?

Consider a random experiment where two fair coins are tossed. Let $A$ be the event that denotes HEAD on both throws, $B$ the event that denotes HEAD on the first throw, and $C$ the event that denotes HEAD on the second throw. Which of the following statements is/are TRUE?

Consider functions Function_1 and Function_2 as follows. Let $f_1(n)$ and $f_2(n)$ be the number of times the statement $x = x + 1$ executes in Function_1 and Function_2, respectively. Which statements are TRUE?

Function_1                          Function_2
while n>1 do                      for i = 1 to 100 * n do
  for i = 1 to n do                   x = x + 1;
    x = x + 1;                      end for
  end for
  n = floor(n/2);
end while

Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2,\ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1, \ldots, n$, \[ \text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \ \text{no neighbour of } v_i \text{ is colored } j\}. \] Which of the following statements is/are TRUE?

Let $f:A\to B$ be an onto (surjective) function, where $A$ and $B$ are nonempty sets. Define an equivalence relation $\sim$ on $A$ by $a_1\sim a_2$ iff $f(a_1)=f(a_2)$. Let $\mathcal{E=\{[x]:x\in A\}$ be the set of all equivalence classes under $\sim$. Define $F:\mathcal{E}\to B$ by $F([x])=f(x)$ for all classes $[x]\in\mathcal{E}$. Which of the following statements is/are TRUE?}

Consider the IEEE-754 single precision floating point numbers $P=0xC1800000$ and $Q=0x3F5C2EF4$. Which one of the following corresponds to the product $P \times Q$, represented in IEEE-754 single precision format?

Consider the two functions incr and decr below. Five threads each call incr once and three threads each call decr once on the same shared variable $X$ (initially $10$). There are two semaphore implementations:

I-1: $s$ is a binary semaphore initialized to $1$.
I-2: $s$ is a counting semaphore initialized to $2$.

Let $V_1, V_2$ be the values of $X$ at the end of all threads for I-1 and I-2, respectively. Which choice gives the minimum possible values of $V_1, V_2$?

incr(){              
  wait(s);           
  X = X + 1;         
  signal(s);         
}

decr(){
  wait(s);
  X = X - 1;
  signal(s);
}

Consider the context-free grammar $G$ below: \[ S \;\to\; aSb \;|\; X \] \[ X \;\to\; aX \;|\; Xb \;|\; a \;|\; b \] where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non-terminal is $S$. Which one of the following statements is CORRECT?