GATE CS question library

A program $P$ reads and processes $1000$ consecutive records from a sequential file $F$ stored on device $D$ without using any file system facilities. Given the following Size of each record $= 3200$ bytes Access time of $D = 10$ msecs Data transfer rate of $D = 800 \times 10^3$ bytes/second CPU time to process each record $= 3$ msecs What is …

Let $f=(\bar{w} + y)(\bar{x} +y)(w+\bar{x}+z)(\bar{w}+z)(\bar{x}+z)$ Express $f$ as the minimal sum of products. Write only the answer. If the output line is stuck at $0$, for how many input combinations will the value of $f$ be correct?

Let $R (a, b, c)$ and $S(d, e, f)$ be two relations in which $d$ is the foreign key of $S$ that refers to the primary key of $R$. Consider the following four operations $R$ and $S$ Insert into $R$ Insert into $S$ Delete from $R$ Delete from $S$ Which of the following can cause violation of the referential integrity constraint above?

For a database relation $R(a, b, c, d)$, where the domains $a, b, c, d$ include only atomic values, only the following functional dependencies and those that can be inferred from them hold $a \rightarrow c$ $b \rightarrow d$ This relation is

Each Process $P_i, i = 1\ldots 9$ is coded as follows repeat P(mutex) {Critical section} V(mutex) forever The code for $P_{10}$ is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

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?