GATE CS question library

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive?

Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct?

Which of the following standard $C$ library functions will always invoke a system call when executed from a single-threaded process in a $\text{UNIX/Linux}$ operating system?

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory $\textsf{foo}$. Which of the following operations will necessarily require a full scan of $\textsf{foo}$ …

In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.

Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.

There are $6$ jobs with distinct difficulty levels, and $3$ computers with distinct processing speeds. Each job is assigned to a computer such that: The fastest computer gets the toughest job and the slowest computer gets the easiest job. Every computer gets at least one job. The number of ways in which this can be done is ___________.

The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter $2$. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to $2$ decimal places) is ____________.

Consider the following expression.$$\displaystyle \lim_{x\rightarrow-3}\frac{\sqrt{2x+22}-4}{x+3}$$The value of the above expression (rounded to 2 decimal places) is ___________.

Consider the following sequence of operations on an empty stack.$$\textsf{push}(54);\textsf{push}(52);\textsf{pop}();\textsf{push}(55);\textsf{push}(62);\textsf{s}=\textsf{pop}();$$Consider the following sequence of operations on an empty queue. …

Consider a computer system with a byte-addressable primary memory of size $2^{32}$ bytes. Assume the computer system has a direct-mapped cache of size $\text{32 KB}$ ($\text{1 KB}$ = $2^{10}$ bytes), and each cache block is of size $64$ bytes. The size of the tag field is __________ bits.

A relation $r(A, B)$ in a relational database has $1200$ tuples. The attribute $A$ has integer values ranging from $6$ to $20$, and the attribute $B$ has integer values ranging from $1$ to $20$. Assume that the attributes $A$ and $B$ are independently distributed. The estimated number of tuples in the output of …

Consider the following representation of a number in $\text{IEEE 754}$ single-precision floating point format with a bias of $127$.$$S: 1\quad\quad E:\; 10000001\quad\quad F:\;11110000000000000000000$$ Here $S, \;E$ and $F$ denote the sign, exponent, and fraction components of the floating point representation. The decimal value corresponding to the …

Three processes arrive at time zero with $\text{CPU}$ bursts of $16,\;20$ and $10$ milliseconds. If the scheduler has prior knowledge about the length of the $\text{CPU}$ bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.

​​​Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation $\text{(SDT)}$ actions, given as pseudo-code …

The following relation records the age of $500$ employees of a company, where $empNo$ (indicating the employee number) is the key: $$empAge(\underline{empNo},age)$$ Consider the following relational algebra expression: $$\Pi_{empNo}(empAge \Join_{(age>age1)} \rho_{empNo1,age1}(empAge))$$ What does the above expression generate?

Consider a $3$-bit counter, designed using $T$ flip-flops, as shown below: Assuming the initial state of the counter given by $\text{PQR}$ as $000$, what are the next three states?

Assume that a $12$-bit Hamming codeword consisting of $8$-bit data and $4$ check bits is $d_8d_7d_6d_5c_8d_4d_ 4d_3d_2c_4d_1c_2c_1$, where the data bits and the check bits are given in the following tables: …

Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. …

Consider the following recurrence relation. $$T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$$ Which one of the following options is correct?