GATE CS question library

Which of the following is NOT a superkey in a relational schema with attributes $V,W,X,Y,Z$ and primary key $V\;Y$?

Let $a_n$ be the number of $n$-bit strings that do NOT contain two consecutive $1's$. Which one of the following is the recurrence relation for $a_n$?

Two eigenvalues of a $3 \times 3$ real matrix $P$ are $(2+\sqrt {-1})$ and $3$. The determinant of $P$ is _______

A processor can support a maximum memory of $4\;\textsf{GB}$, where the memory is word-addressable (a word consists of two bytes). The size of address bus of the processor is at least _________bits.

Consider the Boolean operator # with the following properties : $x \# 0 = x, x \# 1=\overline{x}, x \# x = 0$ and $x \# \overline{x} = 1.$ Then $x\#y$ is equivalent to

Which of the following is/are example(s) of stateful application layer protocol? $\textsf{HTTP}$ $\textsf{FTP}$ $\textsf{TCP}$ $\textsf{POP3}$

Suppose the functions $F$ and $G$ can be computed in $5$ and $3$ nanoseconds by functional units $U_{F}$ and $U_{G}$, respectively. Given two instances of $U_{F}$ and two instances of $U_{G}$, it is required to implement the computation $F(G(X_{i}))$ for $1 \leq i \leq 10$. Ignoring all other delays, the minimum time required to complete …

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first. …

The width of the physical address on a machine is $40$ bits. The width of the tag field in a $512$ KB $8$-way set associative cache is ________ bits.

Which one of the following well-formed formulae in predicate calculus is NOT valid ?

In an adjacency list representation of an undirected simple graph $G=(V, E)$, each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$, and $[u]$ in the adjacency list of $v$. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If $|E|=m$ and $|V|=n$, and the …

Consider the following database table named water_schemes: …

Consider the following languages: $L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$ $L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$ Which one of the following is TRUE?

A binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ is defined as follows: $(a, b) R(c, d)$ if $a \leq c$ or $b \leq d$. Consider the following propositions: $P:$ $R$ is reflexive. $Q:$ $R$ is transitive. Which one of the following statements is TRUE?

Consider the following program: int f (int * p, int n) { if (n <= 1) return 0; else return max (f (p+1, n-1), p[0] - p[1]); } int main () { int a[] = {3, 5, 2, 6, 4}; printf(" %d", f(a, 5)); } Note: $\max (x, y)$ returns the maximum of $x$ and $y$. The value printed by this program is ________.

Consider a processor with $64$ registers and an instruction set of size twelve. Each instruction has five distinct fields, namely, opcode, two source register identifiers, one destination register identifier, and twelve-bit immediate value. Each instruction must be stored in memory in a byte-aligned fashion. If a program has $100$ instructions, the …

Consider the following two-process synchronization solution. …

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[10] [3]; The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num. …

Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right subtree using New-order; Visit the left subtree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by: