GATE CS question library

Consider the following statements. $S_1:$ Every $\text{SLR(1)}$ grammar is unambiguous but there are certain unambiguous grammars that are not $\text{SLR(1)}$. $S_2:$ For any context-free grammar, there is a parser that takes at most $O(n^3)$ time to parse a string of length $n$. Which one of the following options is correct?

Let the representation of a number in base $3$ be $210$. What is the hexadecimal representation of the number?

Consider the following two statements. $S_1$: Destination $\text{MAC}$ address of an $\text{ARP}$ reply is a broadcast address. $S_2$: Destination $\text{MAC}$ address of an $\text{ARP}$ request is a broadcast address. Which one of the following choices is correct?

Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic. $S_1: (\neg p\wedge(p\vee q))\rightarrow q$ $S_2: q\rightarrow(\neg p\wedge(p\vee q))$ Which one of the following choices is correct?

Consider the following array.$$\begin{array}{|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array}$$ Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$?

In the context of operating systems, which of the following statements is/are correct with respect to paging?

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 …