GATE CS question library

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

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

A processor uses a $32$-bit instruction format and supports byte-addressable memory access. The $\text{ISA}$ of the processor has $150$ distinct instructions. The instructions are equally divided into two types, namely $\text{R}$-type and $\text{I}$-type, whose formats are shown below. R - type Instruction Format: \begin{array}{|l|l|l|l|l|} \hline …

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.

Let $Z_{n}$ be the group of integers $\{0,1,2, \ldots, n-1\}$ with addition modulo $n$ as the group operation. The number of elements in the group $Z_{2} \times Z_{3} \times Z_{4}$ that are their own inverses is ___________.

Consider a $32$-bit system with $4 \mathrm{~KB}$ page size and page table entries of size $4$ bytes each. Assume $1 \mathrm{~KB}=2^{10}$ bytes. The OS uses a $2$-level page table for memory management, with the page table containing an outer page directory and an inner page table. The $\text{OS}$ allocates a page for the outer page directory upon …

Consider the following augmented grammar, which is to be parsed with a $\text{SLR}$ parser. The set of terminals is $\{a, b, c, d, \#, @\}$ $$\begin{array}{l} S^{\prime} \rightarrow S \\ S \rightarrow S S|A a| b A c|B c| b B a \\ A \rightarrow d \# \\ B \rightarrow @ \end{array}$$ Let …

Consider the following statements regarding the front-end and back-end of a compiler. S1: The front-end includes phases that are independent of the target hardware. S2: The back-end includes phases that are specific to the target hardware. S3: The back-end includes phases that are specific to the programming language used in the source code. Identify the …

Which one of the following sequences when stored in an array at locations $A[1], \ldots, A[10]$ forms a max-heap?

Let $\textsf{SLLdel}$ be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let $\textsf{DLLdel}$ be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let $n$ denote the number of nodes in each …