List of top Questions asked in GATE CS

Consider the following two statements with respect to the matrices $A_{m \times n}$, $B_{n \times m}$, $C_{n \times n}$ and $D_{n \times n}$.

Statement 1: $tr(AB) = tr(BA)$
Statement 2: $tr(CD) = tr(DC)$

where $tr()$ represents the trace of a matrix. Which one of the following holds?

Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below.

What is the number of subnets inside the enterprise network?

Which of the following statements is/are TRUE?

Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

Consider the following three relations in a relational database.

Employee($eId$, Name), Brand($bId$, bName), Own($eId$, $bId$)

Which of the following relational algebra expressions return the set of $eId$'s who own all the brands?

Which of the following statements is/are TRUE with respect to deadlocks?

Which of the following statements is/are TRUE for a group $ G $?

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index $\underline{\hspace{1cm}}$.

Consider the augmented grammar with $\{+,* , (, ), id\}$ as the set of terminals. \[ S' \rightarrow S \] \[ S \rightarrow S + R \mid R \] \[ R \rightarrow R^{\,*} P \mid P \] \[ P \rightarrow (S) \mid id \] If $I_0$ is the set of two LR(0) items $\{[S' \rightarrow S.], [S \rightarrow S. + R]\}$, then $goto(\text{closure}(I_0), +)$ contains exactly $\underline{\hspace{1cm}}$ items.

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is

Consider a relation $R(A, B, C, D, E)$ with the following three functional dependencies: \[ AB \rightarrow C, BC \rightarrow D, C \rightarrow E \] The number of superkeys in the relation is

The number of arrangements of six identical balls in three identical bins is

A cache memory that has a hit rate of 0.8 has an access latency of 10 ns and a miss penalty of 100 ns. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is $\underline{\hspace{1cm}}$.

The value of the following limit is $\underline{\hspace{1cm}}$. \[ \lim_{x \to 0^+} \frac{\sqrt{x}}{1 - e^{2\sqrt{x}}} \]

Consider the resolution of the domain name www.gate.org.in by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that the iterative query mechanism is used in the resolution. The number of DNS query-response pairs involved in completely resolving the domain name is $\underline{\hspace{1cm}}$.

Which one of the following is the closed form for the generating function of the sequence $ \{ a_n \}_{n \geq 0} $ defined below?
\[ a_n = \begin{cases} n+1, & \text{if } n \text{ is odd} \\ 1, & \text{otherwise} \end{cases} \]

Consider a simple undirected unweighted graph with at least three vertices. If $ A $ is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

Which one of the following statements is FALSE?

Let $R(z)$ and $W(z)$ denote read and write operations on a data element $z$ by a transaction $T_i$, respectively. Consider the schedule $S$ with four transactions.
\[ S: R_1(x) R_2(x) R_3(y) W_1(y) W_2(x) W_3(y) R_4(y) \] Which one of the following serial schedules is conflict equivalent to $S$?

Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time $t = 0$. There is exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

What is printed by the following ANSI C program?

#include<stdio.h>
int main(int argc, char argv[])
{
	int a[3][3][3] = {
		{1, 2, 3, 4, 5, 6, 7, 8, 9},
		{10, 11, 12, 13, 14, 15, 16, 17, 18},
		{19, 20, 21, 22, 23, 24, 25, 26, 27}};
	int i = 0, j = 0, k = 0;
	for( i = 0; i < 3; i++){
		for(k = 0; k < 3; k++)
			printf("%d ", a[i][j][k]);
		printf("\n");
	}
	return 0;
}

What is printed by the following ANSI C program?

#include<stdio.h>
int main(int argc, char argv[])
{
	char a = 'P';
	char b = 'x';
	char c = (a & b) + '';
	char d = (a | b) - '-';
	char e = (a ^ b) + '+';
	printf("%c %c %c\n", c, d, e);
	return 0;
}

ASCII encoding for relevant characters is given below

Consider solving the following system of simultaneous equations using LU decomposition. \[ x_1 + x_2 - 2x_3 = 4 \\ x_1 + 3x_2 - x_3 = 7 \\ 2x_1 + x_2 - 5x_3 = 7 \] where $ L $ and $ U $ are denoted as \[ L = \begin{pmatrix} L_{11} & 0 & 0 \\ L_{21} & L_{22} & 0 \\ L_{31} & L_{32} & L_{33} \end{pmatrix}, U = \begin{pmatrix} U_{11} & U_{12} & U_{13} \\ 0 & U_{22} & U_{23} \\ 0 & 0 & U_{33} \end{pmatrix} \] Which one of the following is the correct combination of values for $ L_{32}, U_{33}, $ and $ x_1 $?

Which of the following is/are undecidable?

Consider the following languages: \[ L_1 = \{a^n w a^n | w \in \{a, b\}^*\} \] \[ L_2 = \{ w x w^R | w, x \in \{a, b\}^*, |w|, |x| > 0 \} \] Note that $ w^R $ is the reversal of the string $ w $. Which of the following is/are TRUE?