GATE CS question library

For positive real numbers $S$ and $K$, the function $H_{K}(S)$ is defined as: $H_{K}(S)=\max (S-K, 0)$. The max function is defined as: $$\max (a, b)=\left\{\begin{array}{ll} a, & \text{ when } a>b \\ b, & \text{ when } a \leq b \end{array}\right.$$ The graph below shows the plot of a function $N(S)$ versus $S$. $N(S)$ can be …

An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put back in the urn. The probability that there are equal number of red and blue balls after two steps is

For $n>1$, the maximum multiplicity of any eigenvalue of an $n \times n$ matrix with elements from $\mathbb{R}$ is

Match each addressing mode in $\textbf{List I}$ with a data element or an element of a data structure (in a high-level language) in $\textbf{List II}$: …

Consider a processor $\text{P}$ whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand. Which one of the following sequences of instructions corresponds to the high-level language statement $\mathrm{Z}=\mathrm{X}+\mathrm{Y}$ ? Note: X, Y, and Z …

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

Consider the following recurrence relations: For all $n>1$, $$\begin{array}{c} T_{1}(n)=4 T_{1}\left(\frac{n}{2}\right)+T_{2}(n) \\ T_{2}(n)=5 T_{2}\left(\frac{n}{4}\right)+\Theta\left(\log _{2} n\right) \end{array}$$ Assume that for all $n \leq 1, T_{1}(n)=1$ and $T_{2}(n)=1$. Which one of the following options is correct?

An unbiased six-faced dice whose faces are marked with numbers $1,2,3,4,5$, and $6$ is rolled twice in succession and the number on the top face is recorded each time. The probability that the number appearing in the second roll is an integer multiple of the number appearing in the first roll is $\_\_\_\_$

With respect to a TCP connection between a client and a server, which one of the following statements is true?

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP $1.1$?

Let $n>1$. Consider an $n \times n$ matrix $M$ with its elements from $\mathbb{R}$. Let the vector $(0,1,0,0, \ldots, 0) \in \mathbb{R}^{n}$ be in the null space of $M$. Which of the following options is/are always correct?

Consider the $8$ -bit signed integers $X, Y$ and $Z$ represented using the sign-magnitude form. The binary representations of $X$ and $Y$ are as follows: $$X: 10110100 \quad Y: 01001100$$ Which of the following operations to compute $Z$ result(s) in an arithmetic overflow?

Let $n$ be an odd number greater than $100$. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from $1$. Which of the following indices of $P$ do/does NOT correspond to any leaf node of the minheap?

Consider a hash table $P[0,1, \ldots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x)=(x+7) \bmod 11$. Consider the following sequence of insertions performed on $P$ : $$\text{ 1,13, 22, 15, 11, } 24$$ Which of the following positions in the hash table is/are empty …

Consider the following Boolean expression of a function $F$ : $$F(P, Q)=(\bar{P}+Q) \oplus(\bar{P} Q)$$ Which of the following expressions is/are equivalent to $F$ ?

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$S \rightarrow a S b S \text{ | } b S \text{ | } \epsilon$$ Which of the following statements is/are true?

Let $M$ be a nondeterministic finite automaton (NFA) with $6$ states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?

Consider the following C statements: char *str1 = "Hello; /* Statement S1 */ char *str2 = "Hello;"; /* Statement S2 */ int *str3 = "Hello"; /* Statement S3 */ Which of the following options is/are correct?

Which of the following statements is/are true?

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?