GATE CS question library

The inclusion of which of the following sets into $S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3, 4, 5\right\} \right\}$ is necessary and sufficient to make $S$ a complete lattice under the partial order defined by set containment?

The following is the incomplete operation table of a $4-$element group. …

How many solutions does the following system of linear equations have? $-x + 5y = -1$ $x - y = 2$ $x + 3y = 3$

A 4-stage pipeline has the stage delays as $150$, $120$, $160$ and $140$ $nanoseconds$, respectively. Registers that are used between the stages have a delay of $5$ $nanoseconds$ each. Assuming constant clocking rate, the total time taken to process $1000$ data items on this pipeline will be:

The following propositional statement is $\left(P \implies \left(Q \vee R\right)\right) \implies \left(\left(P \wedge Q \right)\implies R\right)$

A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is $20$ Kbytes, what is the percentage of processor time consumed for the transfer …

The microinstructions stored in the control memory of a processor have a width of $26$ bits. Each microinstruction is divided into three fields: a micro-operation field of $13$ bits, a next address field $(X),$ and a MUX select field $(Y).$ There are $8$ status bits in the input of the MUX. How many bits are there in the $X$ and $Y$ fields, and …

Let $A = 1111 1010$ and $B = 0000 1010$ be two $8-bit$ $2’s$ complement numbers. Their product in $2’s$ complement is

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is: $8, 12, 0, 12, 8$.

Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$ …

A 4-bit carry look ahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using …

Consider the partial implementation of a $2-bit$ counter using $T$ flip-flops following the sequence $0-2-3-1-0,$ as shown below. To complete the circuit, the input $X$ should be

Consider a multiplexer with $X$ and $Y$ as data inputs and $Z$ the as the control input. $Z=0$ selects input $X$, and $Z=1$ selects input $Y$. What are the connections required to realize the 2-variable Boolean function $f=T+R$, without using any additional hardware?

Which are the essential prime implicants of the following Boolean function? $f(a, b, c)= a' c+ ac'+b' c$

A circuit outputs a digit in the form of $4$ bits. $0$ is represented by $0000, 1$ by $0001, \ldots, 9$ by $1001$. A combinational circuit is to be designed which takes these $4$ bits as input and outputs $1$ if the digit $\geq$ $5$, and $0$ otherwise. If only $\textsf{AND}, \textsf{OR}$ and $\textsf{NOT}$ gates may be used, what is …

The routing table of a router is shown below: …

Consider three IP networks $A, B$ and $C$. Host $H_A$ in network $A$ sends messages each containing $180$ bytes of application data to a host $H_C$ in network $C$. The $\text{TCP}$ layer prefixes $20$ byte header to the message. This passes through an intermediate network $B$.The maximum packet size, including $20$ byte IP header, in …

$A$ and $B$ are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both $A$ and $B$ attempt to transmit a frame, collide, and $A$ wins the first backoff race. At the end of this successful transmission by $A$, both $A$ and $B$ attempt to transmit and collide. The probability that $A$ wins the second backoff …

The employee information in a company is stored in the relation Employee (name, sex, salary, deptName) Consider the following SQL query Select deptName From Employee Where sex = ‘M’ Group by deptName Having avg(salary) > (select avg (salary) from Employee) It returns the names of the department in which

The order of an internal node in a $B+$ tree index is the maximum number of children it can have. Suppose that a child pointer takes $6$ bytes, the search field value takes $14$ bytes, and the block size is $512$ bytes. What is the order of the internal node?