GATE CS question library

An operating system contains $3$ user processes each requiring $2$ units of resource $R$. The minimum number of units of $R$ such that no deadlocks will ever arise is

Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata? Note: $w^R$ is the string obtained by reversing $'w'$.

Which one of the following is not decidable?

Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?

The number of equivalence relations of the set $\{1,2,3,4\}$ is

Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of connected components in $G$ is

A partial order $≤$ is defined on the set $S=\left \{ x, a_1, a_2, \ldots, a_n, y \right \}$ as $x$ $\leq _{i}$ $a_{i}$ for all $i$ and $a_{i}\leq y$ for all $i$, where $n ≥ 1$. The number of total orders on the set S which contain the partial order $≤$ is

Consider a logic circuit shown in figure below. The functions $f_1, f_2 \text{ and } f$ (in canonical sum of products form in decimal notation) are : $f_1 (w, x, y, z) = \sum 8, 9, 10$ $f_2 (w, x, y, z) = \sum 7, 8, 12, 13, 14, 15$ $f (w, x, y, z) = \sum 8, 9$ The function $f_3$ is

Given $\sqrt{(224)_r} =(13)_r$. The value of the radix $r$ is:

A micro instruction is to be designed to specify: none or one of the three micro operations of one kind and none or upto six micro operations of another kind The minimum number of bits in the micro-instruction is:

Let $f(x, y, z)=\bar{x} + \bar{y}x + xz$ be a switching function. Which one of the following is valid?

The expression $( a * b) * c \; op \dots$ where ‘op’ is one of ‘$+$’, ‘$*$’ and ‘$\uparrow$’ (exponentiation) can be evaluated on a CPU with single register without storing the value of ($a * b$) if

Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$. Which of the following statements is true?

A priority queue $Q$ is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT $(Q, C, K)$ where $K$ is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN$(Q)$. For a sequence of operations, the keys chosen are in

A binary search tree contains the value $1, 2, 3, 4, 5, 6, 7, 8$. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A polynomial $p(x)$ is such that $p(0) = 5, p(1) = 4, p(2) = 9$ and $p(3) = 20$. The minimum degree it should have is

Let $A=(a_{ij})$ be an $n$-rowed square matrix and $I_{12}$ be the matrix obtained by interchanging the first and second rows of the $n$-rowed Identity matrix. Then $AI_{12}$ is such that its first

What is the maximum value of the function $f(x) = 2x^2 - 2x + 6$ in the interval $\left[0,2 \right]$?

Dirty bit for a page in a page table

Thrashing