GATE CS question library

The atomic fetch-and-set $x, y$ instruction unconditionally sets the memory location $x$ to $1$ and fetches the old value of $x$ in $y$ without allowing any intervening access to the memory location $x$. Consider the following implementation of $P$ and $V$ functions on a binary semaphore $S$. void P (binary_semaphore *s) { unsigned y; …

Consider the following C code segment. for (i = 0, i < n; i++) { for (j = 0; j < n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } Which one of the following is false?

Consider the following translation scheme. $S\rightarrow ER$ $R\rightarrow *E\left \{ \text{print}(\text{‘}*\text{’}); \right \} R\mid \varepsilon$ $E\rightarrow F+E\left \{ \text{print}(\text{‘}+\text{’}); \right \}\mid F$ $F\rightarrow (S)\mid id \left \{ \text{print}(id.value); \right \}$ Here $id$ is a token that represents an integer and …

Consider these two functions and two statements S1 and S2 about them. int work1(int *a, int i, int j) { int x = a[i+2]; a[j] = x+1; return a[i+2] - 3; } int work2(int *a, int i, int j) { int t1 = i+2; int t2 = a[t1]; a[j] = t2+1; return t2 - 3; } S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will …

Consider the following code written in a pass-by-reference language like FORTRAN and these statements about the code. subroutine swap(ix,iy) it = ix L1 : ix = iy L2 : iy = it end ia = 3 ib = 8 call swap (ia, ib+5) print *, ia, ib end S1: The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the …

Consider this C code to swap two integers and these five statements: the code void swap (int *px, int *py) { *px = *px - *py; *py = *px + *py; *px = *py - *px; } S1: will generate a compilation error S2: may generate a segmentation fault at runtime depending on the arguments passed S3: correctly implements the swap procedure for all input pointers referring …

Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or report that there is not such span,

Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array, void xyz(int a[], int b [], int c []){ int i,j,k; i=j=k=0; while ((i<n) && (j<m)) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } Which of the following condition(s) hold(s) after the termination …

The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

Consider the following recurrence: $T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true?

A set $X$ can be represented by an array $x[n]$ as follows: $x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise} \end{cases}$ Consider the following algorithm in which $x$, $y$, and $z$ are Boolean arrays of size $n$: algorithm zzz(x[], y[], z[]) { int i; for(i=0; i<n; ++i) z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] …

An implementation of a queue $Q$, using two stacks $S1$ and $S2$, is given below: void insert (Q, x) { push (S1, x); } void delete (Q) { if (stack-empty(S2)) then if (stack-empty(S1)) then { print(“Q is empty”); return; } else while (!(stack-empty(S1))){ x=pop(S1); push(S2,x); } x=pop(S2); } Let $n$ insert and $m(\leq n)$ delete operations be …

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of the following statements is true?

Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

Station $A$ needs to send a message consisting of $9$ packets to Station $B$ using a sliding window (window size $3$) and go-back-$n$ error control strategy. All packets are ready and immediately available for transmission. If every $5$th packet that $A$ transmits gets lost (but no acks from $B$ ever get lost), then what is the number of …

Station $A$ uses $32\; \text{byte}$ packets to transmit messages to Station $B$ using a sliding window protocol. The round trip delay between A and $B$ is $80\; \text{milliseconds}$ and the bottleneck bandwidth on the path between $A$ and $B$ is $128\; \text{kbps}$ . What is the optimal window size that $A$ should use?

Two computers $C1$ and $C2$ are configured as follows. $C1$ has IP address $203.197.2.53$ and netmask $255.255.128.0$. $C2$ has IP address $203.197.75.201$ and netmask $255.255.192.0$. Which one of the following statements is true?

Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg is one. A register is $32$ -bits wide and the bits are numbered $0$ to $31,$ bit in position $0$ being the least significant. Consider the following emulation of this instruction on a …

A CPU has a five-stage pipeline and runs at $1$ GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is …

A CPU has a cache with block size $64$ bytes. The main memory has $k$ banks, each bank being $c$ bytes wide. Consecutive $c$ − byte chunks are mapped on consecutive banks with wrap-around. All the $k$ banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of …