GATE CS question library

Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statement is TRUE?

Consider the following statements about process state transitions for a system using preemptive scheduling. A running process can move to ready state. A ready process can move to running state. A blocked process can move to running state. A blocked process can move to ready state. Which of the above statements are TRUE?

Consider a relational database containing the following schemas. …

Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?

What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Let $\mathcal{R}$ be the set of all binary relations on the set $\{1,2,3\}$. Suppose a relation is chosen from $\mathcal{R}$ at random. The probability that the chosen relation is reflexive (round off to $3$ decimal places) is ______.

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