GATE CS question library

Consider a source computer $(S)$ transmitting a file of size $10^{6}$ bits to a destination computer $(D)$ over a network of two routers $(R_{1}\text{ and }R_{2})$ and three links $(L_{1},L_{2},\text{ and } L_{3})$. $L_{1}$ connects $S$ to $R_{1}$; $L_{2}$ connects $R_{1}$ to $R_{2}$; and $L_{3}$ connects $R_{2}$ to $D$. Let each …

Suppose $R_{1} (\underline{A}, B)$ and $R_{2} (\underline{C}, D)$ are two relation schemas. Let $r_{1}$ and $r_{2}$ be the corresponding relation instances. $B$ is a foreign key that refers to $C$ in $R_{2}$. If data in $r_{1}$ and $r_{2}$ satisfy referential integrity constraints, which of the following is ALWAYS TRUE?

Consider the virtual page reference string $$\text{1, 2, 3, 2, 4, 1, 3, 2, 4, 1}$$ on a demand paged virtual memory system running on a computer system that has main memory size of $3$ page frames which are initially empty. Let $\text{LRU}$, $\text{FIFO}$ and $\text{OPTIMAL}$ denote the number of page faults under the corresponding page replacement …

A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

A file system with $300$ GByte disk uses a file descriptor with $8$ direct block addresses, $1$ indirect block address and $1$ doubly indirect block address. The size of each disk block is $128$ Bytes and the size of each disk block address is $8$ Bytes. The maximum possible file size in this file system is

How many onto (or surjective) functions are there from an $n$-element $(n ≥ 2)$ set to a $2$-element set?

Suppose a circular queue of capacity $(n −1)$ elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using $\textsf{REAR}$ and $\textsf{FRONT}$ as array index variables, respectively. Initially, $\textsf{REAR} = \textsf{FRONT} = 0$. The conditions to detect queue full and queue empty …

An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available with it: $245.248.128.0/20$. The ISP wants to give half of this chunk of addresses to Organization $A$, and a quarter to Organization $B$, while retaining the remaining with itself. Which of the following is a valid allocation of addresses to $A$ and …

Suppose a fair six-sided die is rolled once. If the value on the die is $1, 2,$ or $3,$ the die is rolled a second time. What is the probability that the sum total of values that turn up is at least $6$ ?

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location $X$, increments it by the value $i$, and returns the old value of $X$. It is used in the pseudocode shown below to implement a busy-wait lock. $L$ is an unsigned integer shared variable initialized to $0$. The value of $0$ corresponds to lock …

Consider the $3$ processes, $P1, P2$ and $P3$ shown in the table. $$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Time Units Required} \\ \hline \text{P1} & 0 & 5\\ \hline \text{P2} & 1 & 7 \\ \hline \text{P3} & 3 & 4 \\ \hline \end{array}$$The completion order of the $3$ …

What is the minimal form of the Karnaugh map shown below? Assume that $X$ denotes a don’t care term

The bisection method is applied to compute a zero of the function $f(x) =x ^{4} – x ^{3} – x ^{2} – 4$ in the interval [1,9]. The method converges to a solution after ––––– iterations.

Consider the following transactions with data items $P$ and $Q$ initialized to zero: …

Which of the following graphs is isomorphic to

Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$? $abaabaaabaa$ $aaaabaaaa$ $baaaaabaaaab$ $baaaaabaa$

Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive?

In the IPv4 addressing format, the number of networks allowed under Class $C$ addresses is:

Which of the following transport layer protocols is used to support electronic mail?

Consider a random variable $X$ that takes values $+1$ and $−1$ with probability $0.5$ each. The values of the cumulative distribution function $F(x)$ at $x = −1$ and $+1$ are