GATE CS question library

The n-bit fixed-point representation of an unsigned real number $X$ uses $f$ bits for the fraction part. Let $i = n-f$. The range of decimal values for $X$ in this representation is

Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are: Note: The height of a tree with a single node is $0$.

Let $c_{1}.....c_{n}$ be scalars, not all zero, such that $\sum_{i=1}^{n}c_{i}a_{i}$ = 0 where $a_{i}$ are column vectors in $R^{n}$. Consider the set of linear equations $Ax = b$ where $A=\left [ a_{1}.....a_{n} \right ]$ and $b=\sum_{i=1}^{n}a_{i}$. The set of equations has

Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segment is sent to the TCP server. Server-side TCP responds by sending an ACK, which is received by the client-side TCP. As per the TCP connection state diagram $\text{(RFC 793)}$, in …

Consider the recurrence function $$T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}$$ Then $T(n)$ in terms of $\Theta$ notation is

Two transactions $T_1$ and $T_2$ are given as $T_1:r_1(X)w_1(X)r_1(Y)w_1(Y)$ $T_2:r_2(Y)w_2(Y)r_2(Z)w_2(Z)$ where $r_i(V)$ denotes a $\textit{read}$ operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a $\textit{write}$ operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable …

If the characteristic polynomial of a $3 \times 3$ matrix $M$ over $\mathbb{R}$ (the set of real numbers) is $\lambda^3 – 4 \lambda^2 + a \lambda +30, \quad a \in \mathbb{R}$, and one eigenvalue of $M$ is $2,$ then the largest among the absolute values of the eigenvalues of $M$ is _______

Consider a machine with a byte addressable main memory of $2^{32}$ bytes divided into blocks of size $32$ bytes. Assume that a direct mapped cache having $512$ cache lines is used with this machine. The size of the tag field in bits is _______

Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted by a Turing machine $M$. Which of the following decision problems are undecidable? Given a regular expression $R$ and a string $w$, is $w \in L(R)$? Given a context-free …

Consider the following languages. $L_1 = \{a^p \mid p \text{ is a prime number} \}$ $L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \}$ $L_3 = \{a^n b^n c^{2n} \mid n \geq 0 \}$ $L_4 = \{ a^n b^n \mid n \geq 1\}$ Which of the following are CORRECT? $L_1$ is context free but not regular $L_2$ is not context free $L_3$ is not context free but …

The read access times and the hit ratios for different caches in a memory hierarchy are as given below: …

$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: …

In a $B^+$ Tree , if the search-key value is $8$ bytes long , the block size is $512$ bytes and the pointer size is $2\;\text{B}$ , then the maximum order of the $B^+$ Tree is ____

Consider the set of process with arrival time (in milliseonds), CPU burst time (in millisecods) and priority ($0$ is the highest priority) shown below. None of the process have I/O burst time …

The next state table of a $2-$bit saturating up-counter is given below. $\begin{array}{cc|cc} Q_1 & Q_0 & Q_1^+ & Q_0^+ \\ \hline 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array}$ The counter is built as a synchronous sequential circuit using $T$ flip-flops. The …

Consider two hosts $X$ and $Y$, connected by a single direct link of rate $10^6\; \text{bits/sec}$. The distance between the two hosts is $10,000\;\text{km}$ and the propagation speed along the link is $2 \times 10^8 \;\text{m/sec}$. Host $X$ sends a file of $50,000\;\text{bytes}$ as one large message to host $Y$ continuously. Let the …

If a random variable $X$ has a Poisson distribution with mean $5$, then the expectation $E\left [ \left ( x+2 \right )^{2} \right ]$ equals ___.

If $w, x, y, z$ are Boolean variables, then which one of the following is INCORRECT?

In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed? Contiguous Linked Indexed