GATE CS question library

Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP v4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D? TTL Checksum Fragment Offset

A bit-stuffing based framing protocol uses an $\text{8-bit}$ delimiter pattern of $01111110.$ If the output bit-string after stuffing is $01111100101,$ then the input bit-string is:

In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

A prime attribute of a relation scheme $R$ is an attribute that appears

What is the optimized version of the relation algebra expression $\pi_{A1}(\pi_{A2}(\sigma_{F1}(\sigma_{F2}(r))))$, where $A1, A2$ are sets of attributes in $r$ with $A1 \subset A2$ and $F1,F2$ are Boolean expressions based on the attributes in $r$?

A system uses $3$ page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? $\text{4, 7, 6, 1, 7, 6, 1, 2, 7, 2}$

In the context of modular software design, which one of the following combinations is desirable?

One of the purposes of using intermediate code in compilers is to

Which of the following statements are CORRECT? Static allocation of all data areas by a compiler makes it impossible to implement recursion. Automatic garbage collection is essential to implement recursion. Dynamic allocation of activation records is essential to implement recursion. Both heap and stack are essential to implement recursion.

Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$. Which one of the following is TRUE?

The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______. $$a^*b^*(ba)^*a^*$$

You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

Consider the following rooted tree with the vertex labeled $P$ as the root: The order in which the nodes are visited during an in-order traversal of the tree is

The minimum number of arithmetic operations required to evaluate the polynomial $P(X) = X^5+4X^3+6X+5$ for a given value of $X$, using only one temporary variable is ______.

Let $A$ be the square matrix of size $n \times n$. Consider the following pseudocode. What is the expected output? C=100; for i=1 to n do for j=1 to n do { Temp = A[i][j]+C; A[i][j] = A[j][i]; A[j][i] = Temp -C; } for i=1 to n do for j=1 to n do output (A[i][j]);

Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency. $\text{P1:}$ Four-stage pipeline with stage latencies $\text{1 ns, 2 ns, 2 ns, 1 ns}$. $\text{P2:}$ Four-stage pipeline with stage latencies $\text{1 ns, 1.5 ns, 1.5 ns, 1.5 ns}$. $\text{P3:}$ Five-stage pipeline with stage latencies …

Consider the following combinational function block involving four Boolean variables $x,\:y,\:a,\:b$ where $x,\:a,\:b$ are inputs and $y$ is the output. f(x, a, b, y) { if(x is 1) y = a; else y = b; } Which one of the following digital logic blocks is the most suitable for implementing this function?

Consider the following minterm expression for $F$: $$F(P,Q,R,S) = \sum 0,2,5,7,8,10,13,15$$ The minterms $2$, $7$, $8$ and $13$ are 'do not care' terms. The minimal sum-of-products form for $F$ is

If $\int \limits_0^{2 \pi} |x \: \sin x| dx=k\pi$, then the value of $k$ is equal to ______.