GATE CS question library

Consider a computer system with $\text{DMA}$ support. The $\text{DMA}$ module is transferring one $8$-bit character in one $\text{CPU}$ cycle from a device to memory through cycle stealing at regular intervals. Consider a $\text{2 MHz}$ processor. If $0.5 \%$ processor cycles are used for $\text{DMA}$, the data transfer rate of the device is …

A data file consisting of $1,50,000$ student-records is stored on a hard disk with block size of $4096$ bytes. The data file is sorted on the primary key $\textrm{RollNo}$. The size of a record pointer for this disk is $7$ bytes. Each student-record has a candidate key attribute called $\textrm{ANum}$ of size $12$ bytes. Suppose an index file …

For a given biased coin, the probability that the outcome of a toss is a head is $0.4$. This coin is tossed $1,000$ times. Let $X$ denote the random variable whose value is the number of times that head appeared in these $1,000$ tosses. The standard deviation of $X$ (rounded to $2$ decimal place) is _________

Consider the following $\text{ANSI C}$ function: int SomeFunction (int x, int y) { if ((x==1) || (y==1)) return 1; if (x==y) return x; if (x > y) return SomeFunction(x-y, y); if (y > x) return SomeFunction (x, y-x); } The value returned by $\textrm{SomeFunction(15, 255)}$ is __________

Suppose that $P$ is a $4 \times 5$ matrix such that every solution of the equation $\text{Px=0}$ is a scalar multiple of $\begin{bmatrix} 2 & 5 & 4 &3 & 1 \end{bmatrix}^T$. The rank of $P$ is __________

Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function on the interval $[-3, 3]$ and a differentiable function in the interval $(-3,3)$ such that for every $x$ in the interval, $f’(x) \leq 2$. If $f(-3)=7$, then $f(3)$ is at most __________

​​​​​​Assume a two-level inclusive cache hierarchy, $L1$ and $L2$, where $L2$ is the larger of the two. Consider the following statements. $S_1$: Read misses in a write through $L1$ cache do not result in writebacks of dirty lines to the $L2$ $S_2$: Write allocate policy must be used in conjunction with write through caches and no-write …

Suppose we want to design a synchronous circuit that processes a string of $0$’s and $1$’s. Given a string, it produces another string by replacing the first $1$ in any subsequence of consecutive $1$’s by a $0$. Consider the following example. …

In an examination, a student can choose the order in which two questions ($\textsf{QuesA}$ and $\textsf{QuesB}$) must be attempted. If the first question is answered wrong, the student gets zero marks. If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question. If …

Consider the string $\textrm{abbccddeee}$. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is …

​​​​​​Consider the following $\text{ANSI C}$ code segment: z=x + 3 + y->f1 + y->f2; for (i = 0; i < 200; i = i + 2) { if (z > i) { p = p + x + 3; q = q + y->f1; } else { p = p + y->f2; q = q + x + 3; } } Assume that the variable $y$ points to a $\textsf{struct}$ (allocated on the heap) containing two fields $\textsf{f1}$ and …

The relation scheme given below is used to store information about the employees of a company, where $\textsf{empId}$ is the key and $\textsf{deptId}$ indicates the department to which the employee is assigned. Each employee is assigned to exactly one department. $$\textsf{emp($\underline{\textsf{empId}}$, name, gender, salary, deptId)}$$ Consider the …

Consider the cyclic redundancy check $\text{(CRC)}$ based error detecting scheme having the generator polynomial $X^3+X+1$. Suppose the message $m_4m_3m_2m_1m_0=11000$ is to be transmitted. Check bits $c_2c_1c_0$ are appended at the end of the message by the transmitter using the above $\text{CRC}$ scheme. The transmitted bit string is denoted by …

Consider the following $\text{ANSI C}$ program: #include <stdio.h> #include <stdlib.h> struct Node{ int value; struct Node *next;}; int main( ) { struct Node *boxE, *head, *boxN; int index=0; boxE=head= (struct Node *) malloc(sizeof(struct Node)); head → value = index; for (index =1; index<=3; index++){ boxN = (struct Node *) malloc …

​​​​​Let $S$ be the following schedule of operations of three transactions $T_1$, $T_2$ and $T_3$ in a relational database system: $$R_2(Y), R_1(X), R_3(Z), R_1(Y)W_1(X), R_2(Z), W_2(Y), R_3(X), W_3(Z)$$ Consider the statements $P$ and $Q$ below: $P$: $S$ is conflict-serializable. $Q$: If $T_3$ commits before $T_1$ finishes, then $S$ …

​​​​​​Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct?

For two $n$-dimensional real vectors $P$ and $Q$, the operation $s(P,Q)$ is defined as follows: $$s(P,Q) = \displaystyle \sum_{i=1}^n (P[i] \cdot Q[i])$$ Let $\mathcal{L}$ be a set of $10$-dimensional non-zero real vectors such that for every pair of distinct vectors $P,Q \in \mathcal{L}$, $s(P,Q)=0$. What is the maximum cardinality possible …

For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $$T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$$ Which one of the following options is correct about the recurrence $T(n)$?

Suppose the following functional dependencies hold on a relation $U$ with attributes $P,Q,R,S$, and $T$: $P \rightarrow QR$ $RS \rightarrow T$ Which of the following functional dependencies can be inferred from the above functional dependencies?

For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free?