GATE CS question library

Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices?

Consider the following well-formed formulae: $\neg \forall x(P(x))$ $\neg \exists x(P(x))$ $\neg \exists x(\neg P(x))$ $\exists x(\neg P(x))$ Which of the above are equivalent?

The binary operation $\Box$ is defined as follows $$\begin{array}{|c|c|c|} \hline \textbf{P} & \textbf{Q} & \textbf{P} \Box \textbf{Q}\\ \hline \text{T} & \text{T}& \text{T}\\ \hline \text{T} & \text{F}& \text{T} \\ \hline \text{F} & \text{T}& \text{F}\\ \hline \text{F} & \text{F}& \text{T} \\ \hline \end{array}$$ …

Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: $G(x): x$ is a gold ornament $S(x): x$ is a silver ornament $P(x): x$ is precious

For the composition table of a cyclic group shown below: …

An unbalanced dice (with $6$ faces, numbered from $1$ to $6$) is thrown. The probability that the face value is odd is $90\%$ of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than $3$ is $0.75$, which one of the …

Consider the binary relation $R = \left\{(x,y), (x,z), (z,x), (z,y)\right\}$ on the set $\{x,y,z\}$. Which one of the following is TRUE?

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$.

Which one of the following is NOT necessarily a property of a Group?

Consider the following $\text{ER}$ diagram The minimum number of tables needed to represent $M$, $N$, $P$, $R1$, $R2$ is Which of the following is a correct attribute set for one of the tables for the minimum number of tables needed to represent $M$, $N$, $P$, $R1$, $R2$?

Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int i, j, k; i= 0; j = 9; do { k = (i + j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if(Y[k] == x) printf(" x is in the array ") ; else printf(" x is …

Consider a machine with a $2$-way set associative data cache of size $64$ Kbytes and block size $16$ bytes. The cache is managed using $32$ bit virtual addresses and the page size is $4$ Kbytes. A program to be run on this machine begins as follows: double ARR[1024][1024]; int i, j; /*Initialize array ARR to 0.0 */ for(i = 0; i < 1024; i++) …

Consider a machine with a $2$-way set associative data cache of size $64$ Kbytes and block size $16$ bytes. The cache is managed using $32$ bit virtual addresses and the page size is $4$ Kbytes. A program to be run on this machine begins as follows: double ARR[1024][1024]; int i, j; /*Initialize array ARR to 0.0 */ for(i = 0; i < 1024; i++) …

Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ X[i] = Y[i-1] + Z[i-2]; Y[i] = 2 * X[i]; Z[i] = 3 * X[i]; } return X[n]; } $f1(8)$ and $f2(8)$ return …

Delayed branching can help in the handling of control hazards The following code is to run on a pipelined processor with one branch delay slot: I1: ADD $R2 \leftarrow R7 + R8$ I2: Sub $R4 \leftarrow R5 – R6$ I3: ADD $R1 \leftarrow R2 + R3$ I4: STORE Memory $[R4] \leftarrow R1$ BRANCH to Label if $R1 == 0$ Which of the instructions I1, I2, I3 or I4 …

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s. The value of $x_5$ is

The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$, with $n$ rows and $W+1$ columns. …

The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$, with $n$ rows and $W+1$ columns. …

$G$ is a graph on $n$ vertices and $2n-2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$?