GATE CS question library

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

Consider the following functions: $f(n) = 2^n$ $g(n) = n!$ $h(n) = n^{\log n}$ Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and $h(n)$ is true?

In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is:

Which of the following are NOT true in a pipelined processor? Bypassing can handle all RAW hazards Register renaming can eliminate all register carried WAR hazards Control hazard penalties can be eliminated by dynamic branch prediction

The use of multiple register windows with overlap causes a reduction in the number of memory accesses for: Function locals and parameters Register saves and restores Instruction fetches

For inclusion to hold between two cache levels $L_1$ and $L_2$ in a multi-level cache hierarchy, which of the following are necessary? $L_1$ must be write-through cache $L_2$ must be a write-through cache The associativity of $L_2$ must be greater than that of $L_1$ The $L_2$ cache must be at least as large as the $L_1$ cache

Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor? It must be a trap instruction It must be a privileged instruction An exception cannot be allowed to occur during execution of an RFE instruction

Which of the following is/are true of the auto-increment addressing mode? It is useful in creating self-relocating code If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation The amount of increment depends on the size of the data item accessed

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to

$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent? $P ∨ \neg Q$ $\neg(\neg P ∧ Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$

Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ be another predicate such that $\text{equivalent} (a,b)$ means $a$ and $b$ are equivalent. Which of the following first order logic …

Let $X$ be a random variable following normal distribution with mean $+1$ and variance $4$. Let $Y$ be another normal variable with mean $-1$ and variance unknown. If $P (X \leq -1) = P (Y \geq 2)$ , the standard deviation of $Y$ is

How many of the following matrices have an eigenvalue 1? $\left[\begin{array}{cc}1 & 0 \\0 & 0 \end{array} \right]\left[\begin{array}{cc}0 & 1 \\0 & 0 \end{array} \right] \left[\begin{array}{cc}1 & -1 \\1 & 1 \end{array} \right]$ and $\left[\begin{array}{cc}-1 & 0 \\1 & -1 \end{array} \right]$

Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is $0.6$. If she studies mathematics on a day, then the probability that she studies computer science the next day is $0.4$. Given that Aishwarya studies computer science on Monday, …

If $P, Q, R$ are Boolean variables, then $(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$ simplifies to

A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve $3x^4-16x^3+24x^2+37$ is

Which of the following statements is true for every planar graph on $n$ vertices?

Let $P =\sum \limits_ {i\;\text{odd}}^{1\le i \le 2k} i$ and $Q = \sum\limits_{i\;\text{even}}^{1 \le i \le 2k} i$, where $k$ is a positive integer. Then

The Newton-Raphson iteration $x_{n+1} = \frac{1}{2}\left(x_n+\frac{R}{x_n}\right)$ can be used to compute the

The minimum number of equal length subintervals needed to approximate $\int_1^2 xe^x\,dx$ to an accuracy of at least $\frac{1}{3}\times10^{-6}$ using the trapezoidal rule is