GATE CS question library

Which of the following fields is/are modified in the $\text{IP}$ header of a packet going out of a network address translation $\text{(NAT)}$ device from an internal network to an external network?

Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions $\text{(i)}$ from $A$ to $B$ and $\text{(ii)}$ from $A \times A$ to $A \cup B$. The number of possible values of $\text{|A|}$ is ___________.

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below. …

The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.

Consider the following two relations, $R(A, B)$ and $S(A, C)$: …

Consider a network path $\mathrm{P}-\mathrm{Q}-\mathrm{R}$ between nodes $\mathrm{P}$ and $\mathrm{R}$ via router $\mathrm{Q}$. Node $\mathrm{P}$ sends a file of size $10^6$ bytes to $\text{R}$ via this path by splitting the file into chunks of $10^3$ bytes each. Node $\text{P}$ sends these chunks one after the other without any wait time …

​Consider the following syntax-directed definition $\text{(SDD)}$. …

Consider the following pseudo-code. L 1: t1 = -1 L 2: t2 = 0 L 3: t3 = 0 L 4: t4 = 4 * t3 L 5: t5 = 4 * t2 L 6: t6 = t5 * M L 7: t7 = t4 + t6 L 8: t8 = a[t7] L 9: if t8 <= max goto L11 L 10: t1 = t8 L 11: t3 = t3 + 1 L 12: if t3 < M goto L4 L 13: t2 = t2 + 1 L 14: if t2 < N goto L3 L 15: max = t1 Which one of the following options CORRECTLY …

​​​Consider the following two threads $\mathrm{T} 1$ and $\mathrm{T} 2$ that update two shared variables $\mathrm{a}$ and $\mathrm{b}$. Assume that initially $\mathrm{a}=\mathrm{b}=1$. Though context switching between threads can happen at any time, each statement of $\mathrm{T} 1$ or $\mathrm{T} 2$ is executed atomically without interruption. …

​​​​​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?

Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text{ for } n \geq 1, \\ 1 \quad \text{ for } n=1\end{array}\right.$ Which one of the following options is CORRECT?

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

​The symbol $\rightarrow$ indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

​​​​Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following statements is/are TRUE for every such graph $G$ and tree $T$?

​​​​Consider the following read-write schedule $\text{S}$ over three transactions $T_{1}, T_{2}$, 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 …

Consider a Boolean expression given by $\text{F(X, Y, Z)}=\sum(3,5,6,7)$. Which of the following statements is/are CORRECT?

​​Consider the following $\mathrm{C}$ function definition. int f (int x, int y){ for (int i=0 ; i<y ; i++ ) { x= x + x + y; } return x; } 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 the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. Which of the following statements is/are FALSE?

​​​The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?