GATE CS question library

A device with data transfer rate $10$ KB/sec is connected to a CPU. Data is transferred byte-wise. Let the interrupt overhead be $4\mu$sec. The byte transfer time between the device interface register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under …

Consider a disk drive with the following specifications: $16$ surfaces, $512$ tracks/surface, $512$ sectors/track, $1$ KB/sector, rotation speed $3000$ rpm. The disk is operated in cycle stealing mode whereby whenever one $4$ byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a $4$ byte word from the …

A $5$ stage pipelined CPU has the following sequence of stages: IF – instruction fetch from instruction memory RD – Instruction decode and register read EX – Execute: ALU operation for data and address computation MA – Data memory access – for write access, the register read at RD state is used. WB – Register write back Consider the following sequence of …

Consider a direct mapped cache of size $32$ $KB$ with block size $32$ $bytes$. The $CPU$ generates $32$ $bit$ addresses. The number of bits needed for cache indexing and the number of tag bits are respectively,

Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side. …

Consider a three word machine instruction $\text{ADD} A[R_0], @B$ The first operand (destination) $“A[R_0]”$ uses indexed addressing mode with $R_0$ as the index register. The second operand (source) $“@B”$ uses indirect addressing mode. $A$ and $B$ are memory addresses residing at the second and third words, respectively. The first word of the …

Consider the following circuit: The flip-flops are positive edge triggered $D$ $\textsf{FF}$s. Each state is designated as a two-bit string $Q_0Q_1$. Let the initial state be $00.$ The state transition sequence is

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the following is TRUE?

Consider the grammar: $$S \rightarrow (S) \mid a$$ Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be $n_1, n_2$ and $n_3$ respectively. The following relationship holds good:

Consider the grammar: $$E \rightarrow E + n \mid E \times n \mid n$$ For a sentence $n + n \times n$, the handles in the right-sentential form of the reduction are:

Consider the following two problems on undirected graphs: $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size |V| - $4$? $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$? Which one of the following is TRUE?

Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{\#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{\#}$ is a special symbol $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$ Which one of the following is TRUE?

Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Consider the languages: $L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$ Which one of the following statements is FALSE?

Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE?

Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE?

Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$ Which one of the following is FALSE?

In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is:

How many distinct binary search trees can be created out of $4$ distinct keys?