GATE CS question library

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?

​​​​​​Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes $P_1$ and $P_2$, and each of the processes spawns two threads $T_1$ and $T_2$: int x = 0; // global Lock L1; // global main () { create a thread to execute foo(); // Thread T1 create a thread to execute foo(); // Thread T2 wait for the …

Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock $(L)$. The following scheme is used to own a resource instance: function OWNRESOURCE(Resource R) Acquire lock L // a global lock if R …

If the numerical value of a $2$-byte unsigned integer on a little endian computer is $255$ more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?

Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is shown below. The objective is to find the shortest-cost path from the router $R$ to routers $P$ and $Q$. Assume that $R$ does not initially know the shortest routes to $P$ and $Q$. Assume that $R$ has three …

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.

Consider the following directed graph: Which of the following is/are correct about the graph?

Consider a three-level page table to translate a $39-$bit virtual address to a physical address as shown below: The page size is $\text{4 KB} \;(1\text{KB}=2^{10}$ bytes$)$ and page table entry size at every level is $8$ bytes. A process $P$ is currently using $2\text{GB}\;(1 \text{GB}=2^{30}$ bytes$)$ virtual memory which is mapped to …