GATE CS question library

A computer system has a three-level memory hierarchy, with access time and hit ratios as shown below: …

A hard disk is connected to a $50$ MHz processor through a DMA controller. Assume that the initial set-up of a DMA transfer takes $1000$ clock cycles for the processor, and assume that the handling of the interrupt at DMA completion requires $500$ clock cycles for the processor. The hard disk has a transfer rate of $2000$ Kbytes/sec and average block …

A micro program control unit is required to generate a total of $25$ control signals. Assume that during any micro instruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be:

What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in Fig

Consider the following state table for a sequential machine. The number of states in the minimized machine will be …

Consider the circuit in figure. $f$ implements

Consider the circuit in below figure which has a four bit binary number $b_3b_2b_1b_0$ as input and a five bit binary number, $d_4d_3d_2d_1d_0$ as output.

Four jobs to be executed on a single processor system arrive at time $0$ in the order $A, B, C, D$. Their burst CPU time requirements are $4, 1, 8, 1$ time units respectively. The completion time of $A$ under round robin scheduling with time slice of one time unit is

A solution to the Dining Philosophers Problem which avoids deadlock is to

A $1000$ $\text{Kbyte}$ memory is managed using variable partitions but no compaction. It currently has two partitions of sizes $200$ $\text{Kbyte}$ and $260$ $\text{Kbyte}$ respectively. The smallest allocation request in $\text{Kbyte}$ that could be denied is for

The correct matching for the following pairs is …

Which of the following macros can put a macro assembler into an infinite loop? .MACRO M1, X .IF EQ, X ;if X=0 then M1 X + 1 .ENDC .IF NE, X ;if X ≠ O then .WORD X ;address (X) is stored here .ENDC .ENDM .MACRO M2, X .IF EQ, X M2 X .ENDC .IF NE, X .WORD X + 1 .ENDC .ENDM

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot $1, 2, 3, \dots n$ $n, n-1, n-2, \dots, 2, 1$ Let $C_1$ and $C_2$ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

The average number of key comparisons required for a successful search for sequential search on $n$ items is

A binary search tree is generated by inserting in order the following integers: $$50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$$ The number of nodes in the left subtree and right subtree of the root respectively is

The recurrence relation $T(1) = 2$ $T(n) = 3T (\frac{n}{4}) +n$ has the solution $T(n)$ equal to

The minimum number of interchanges needed to convert the array into a max-heap is $89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70$

The grammar whose productions are $\langle\text{stmt}\rangle \to\text{ if id then } \langle\text{stmt}\rangle$ $\langle\text{stmt}\rangle\to\text{ if id then } \langle\text{stmt}\rangle\text{ else } \langle\text{stmt}\rangle$ $\langle\text{stmt}\rangle \to\text{ id }:=\text{ id}$ is ambiguous because if a then if b then c:= d has more than two parse …

If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one?

The probability that top and bottom cards of a randomly shuffled deck are both aces is