GATE CS question library

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exists. Q: Finds whether any negative weighted cycle is reachable from the source.

$$S \to aSa \mid bSb\mid a\mid b$$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:

What is the number of swaps required to sort $n$ elements using selection sort, in the worst case?

The essential content(s) in each entry of a page table is / are

In which one of the following page replacement policies, Belady's anomaly may occur?

A CPU generally handles an interrupt by executing an interrupt service routine:

How many $32K \times 1$ RAM chips are needed to provide a memory capacity of $256K$ bytes?

What is the minimum number of gates required to implement the Boolean function $\text{(AB+C)}$ if we have to use only $2\text{-input NOR}$ gates?

$(1217)_8$ is equivalent to

Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices?

Consider the following well-formed formulae: $\neg \forall x(P(x))$ $\neg \exists x(P(x))$ $\neg \exists x(\neg P(x))$ $\exists x(\neg P(x))$ Which of the above are equivalent?

The binary operation $\Box$ is defined as follows $$\begin{array}{|c|c|c|} \hline \textbf{P} & \textbf{Q} & \textbf{P} \Box \textbf{Q}\\ \hline \text{T} & \text{T}& \text{T}\\ \hline \text{T} & \text{F}& \text{T} \\ \hline \text{F} & \text{T}& \text{F}\\ \hline \text{F} & \text{F}& \text{T} \\ \hline \end{array}$$ …

Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: $G(x): x$ is a gold ornament $S(x): x$ is a silver ornament $P(x): x$ is precious

For the composition table of a cyclic group shown below: …

An unbalanced dice (with $6$ faces, numbered from $1$ to $6$) is thrown. The probability that the face value is odd is $90\%$ of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than $3$ is $0.75$, which one of the …

Consider the binary relation $R = \left\{(x,y), (x,z), (z,x), (z,y)\right\}$ on the set $\{x,y,z\}$. Which one of the following is TRUE?

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$.

Which one of the following is NOT necessarily a property of a Group?