GATE CS question library

Let $G$ be a group of $35$ elements. Then the largest possible size of a subgroup of $G$ other than $G$ itself is _______.

A multiplexer is placed between a group of $32$ registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The number of select lines needed for the multiplexer is ______.

Consider the following statements about the functionality of an $\textsf{IP}$ based router. A router does not modify the $\textsf{IP}$ packets during forwarding. It is not necessary for a router to implement any routing protocol. A router should reassemble $\textsf{IP}$ fragments if the $\textsf{MTU}$ of the outgoing link is larger than the size of …

If there are $m$ input lines and $n$ output lines for a decoder that is used to uniquely address a byte addressable $1$ KB RAM, then the minimum value of $m+n$ is ________ .

A direct mapped cache memory of $1$ MB has a block size of $256$ bytes. The cache has an access time of $3$ ns and a hit rate of $94 \%$. During a cache miss, it takes $2$0 ns to bring the first word of a block from the main memory, while each subsequent word takes $5$ ns. The word size is $64$ bits. The average memory access time in ns (round …

Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ …

Consider the following grammar. $S \rightarrow aSB \mid d$ $B \rightarrow b$ The number of reduction steps taken by a bottom-up parser while accepting the string $aaadbbb$ is ___________.

Consider the following C program. #include <stdio.h> int main () { int a[4] [5] = {{1, 2, 3, 4, 5}, {6, 7,8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17,18, 19, 20}}; printf(“%d\n”, *(*(a+**a+2)+3)); return(0); } The output of the program is _______.

Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send $\textsf{HTTP}$ requests in non-persistent mode. The web page contains text and five very small images.The minimum number of $\textsf{TCP}$ connections required to display the web …

Consider the Boolean function $z(a,b,c)$. Which one of the following minterm lists represents the circuit given above?

Consider three registers $R1$, $R2$, and $R3$ that store numbers in $\textsf{IEEE-754}$ single precision floating point format. Assume that $R1$ and $R2$ contain the values (in hexadecimal notation) $\textsf{0x42200000}$ and $\textsf{0xC1200000},$ respectively. If $R3=\frac{R1}{R2}$, what is the value stored in $R3$?

Let $A$ and $B$ be two $n \times n$ matrices over real numbers. Let rank($M$) and $\text{det}(M)$ denote the rank and determinant of a matrix $M$, respectively. Consider the following statements. $\text{rank}(AB) = \text{rank }(A) \text{rank }(B)$ $\text{det}(AB) = \text{det}(A) \text{det}(B)$ …

A computer system with a word length of $32$ bits has a $16$ MB byte- addressable main memory and a $64$ KB, $4$-way set associative cache memory with a block size of $256$ bytes. Consider the following four physical addresses represented in hexadecimal notation. $A1= \textsf{0x42C8A4}$, $A2= \textsf{0x546888}$, $A3= \textsf{0x6A289C}$, …

Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

Consider the following languages. $$\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$$ Which one of the following is TRUE?

Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to $1$ and $0$, respectively. Assume that $\text{count}$ is a shared variable initialized to $0$ and not used in CODE SECTION P. $\begin{array}{|c|} \hline \textbf{CODE SECTION P} \\ \hline \end{array}$ wait(a); count=count+1; if (count==n) …

Consider the productions $A \rightarrow PQ$ and $A \rightarrow XY$. Each of the five non-terminals $A, P, Q, X,$ and $Y$ has two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. Consider the following rules. Rule $1: P . i = A.i + 2, \: Q.i = P. i + A.i,$ and $A.s = P.s +Q. s$ Rule $2: X.i = A.i + Y.s$ and …

Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. $(P, 155), (Q,85), (R,110),(S, 30), (T,115)$ Assume the head is positioned at cylinder $100$. The scheduler follows Shortest Seek Time First scheduling to service the requests. Which one of the following …

Consider a relational table $R$ that is in $3NF$, but not in BCNF. Which one of the following statements is TRUE?

Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$.