GATE CS question library

​​​​​Which one of the following $\text{CIDR}$ prefixes exactly represents the range of $\text{IP}$ addresses $10.12 .2 .0$ to $10.12 .3 .255$?

​​​​​​You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty tree. The tree $T$ follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in …

​​Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$?

​​​​Consider an array $\mathrm{X}$ that contains $\mathrm{n}$ positive integers. A subarray of $\mathrm{X}$ is defined to be a sequence of array locations with consecutive indices. The $\mathrm{C}$ code snippet given below has been written to compute the length of the longest subarray of $\mathrm{X}$ that contains at most two distinct integers. The …

Let $x$ and $y$ be random variables, not necessarily independent, that take real values in the interval $[0,1]$. Let $z=x y$ and let the mean values of $x, y, z$ be $\bar{x}, \bar{y}, \bar{z}$, respectively. Which one of the following statements is TRUE?

​​​​​The relation schema, Person (pid, city), describes the city of residence for every person uniquely identified by pid. The following relational algebra operators are available: selection, projection, cross product, and rename. To find the list of cities where at least $3$ persons reside, using the above operators, the minimum number of cross product …

​​​​​Consider a multi-threaded program with two threads $\mathrm{T} 1$ and $\mathrm{T} 2$. The threads share two semaphores: $s1$ (initialized to $1$) and $s2$ (initialized to $0$). The threads also share a global variable $\mathrm{x}$ (initialized to $0$). The threads execute the code shown below. //code of T 1 wait (s1); x = x+1; print (x); …

​​​​​Let $A$ be an $n \times n$ matrix over the set of all real numbers $\mathbb{R}$. Let $B$ be a matrix obtained from $A$ by swapping two rows. Which of the following statements is/are TRUE?

​​​​​Let $\mathrm{S} 1$ and $\mathrm{S} 2$ be two stacks. $\mathrm{S} 1$ has capacity of $4$ elements. $\mathrm{S} 2$ has capacity of $2$ elements. $\text{S1}$ already has $4$ elements: $100,200,300$, and $400$, whereas $\text{S2}$ is empty, as shown below. …

Which of the following is/are EQUAL to $224$ in radix - $5$ (i.e., base - $5$) notation?

Consider $4$-variable functions $f 1, f 2, f 3, f 4$ expressed in sum-of-minterms form as given below. $$\begin{array}{l} f 1=\sum(0,2,3,5,7,8,11,13) \\ f 2=\sum(1,3,5,7,11,13,15) \\ f 3=\sum(0,1,4,11) \\ f 4=\sum(0,2,6,13) \end{array}$$ With respect to the circuit given above, which of the following options is/are CORRECT?

Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. Which of the following statements is/are TRUE for every such graph $\text{G}$?

​​​​Consider a context-free grammar $\text{G}$ with the following $3$ rules. $$S \rightarrow a S, S \rightarrow a S b S , S \rightarrow c$$ Let $w \in L(G)$. Let $n_{a}(w), n_{b}(w), n_{c}(w)$ denote the number of times $a, b, c$ occur in $w$, respectively. Which of the following statements is/are TRUE?

Consider a disk with the following specifications: rotation speed of $6000$ RPM, average seek time of $5$ milliseconds, $500$ sectors/track, $512$-byte sectors. A file has content stored in $3000$ sectors located randomly on the disk. Assuming average rotational latency, the total time (in seconds, rounded off to $2$ decimal places) to read the …

Consider a $\text{TCP}$ connection operating at a point of time with the congestion window of size $12$ $\text{MSS}$ (Maximum Segment Size), when a timeout occurs due to packet loss. Assuming that all the segments transmitted in the next two $\text{RTTs}$ (Round Trip Time) are acknowledged correctly, the congestion window size (in $MSS$) during the …

Consider an Ethernet segment with a transmission speed of $10^{8} \mathrm{bits} / \mathrm{sec}$ and a maximum segment length of $500$ meters. If the speed of propagation of the signal in the medium is $2 \times 10^{8} \mathrm{~meters} / \mathrm{sec}$, then the minimum frame size (in bits) required for collision detection is ___________.

A functional dependency $F: X \rightarrow Y$ is termed as a useful functional dependency if and only if it satisfies all the following three conditions: $\text{X}$ is not the empty set. $\text{Y}$ is not the empty set. Intersection of $\text{X}$ and $\text{Y}$ is the empty set. For a relation $\text{R}$ with $4$ attributes, the total number of …

A processor with $16$ general purpose registers uses a $32$-bit instruction format. The instruction format consists of an opcode field, an addressing mode field, two register operand fields, and a $16$-bit scalar field. If $8$ addressing modes are to be supported, the maximum number of unique opcodes possible for every addressing mode is ___________.

A non-pipelined instruction execution unit operating at $2 \mathrm{GHz}$ takes an average of $6$ cycles to execute an instruction of a program $\text{P}$. The unit is then redesigned to operate on a $5$ -stage pipeline at $2 \mathrm{GHz}$. Assume that the ideal throughput of the pipelined unit is $1$ instruction per cycle. In the execution of …

The number of distinct minimum-weight spanning trees of the following graph is