GATE CS question library

The message $11001001$ is to be transmitted using the CRC polynomial $x^3 +1$ to protect it from errors. The message that should be transmitted is:

The address of a class $\text{B}$ host is to be split into subnets with a $6\;\text{-bit}$ subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?

In a token ring network the transmission speed is $10^7$ bps and the propagation speed is $200\;\text{meters}/\mu \text{s}.$ The $1$-bit delay in this network is equivalent to:

There are $n$ stations in slotted LAN. Each station attempts to transmit with a probability $p$ in each time slot. What is the probability that ONLY one station transmits in a given time slot?

Consider the following schedules involving two transactions. Which one of the following statements is TRUE? $S_1 :r_1(X); r_1(Y); r_2(X); r_2(Y); w_2(Y); w_1(X)$ $S_2 :r_1(X); r_2(X); r_2(Y); w_2(Y); r_1(Y); w_1(X)$

The order of a leaf node in a $B^+$ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is $1K\;\text{bytes}$, data record pointer is $7\;\text{bytes}$ long, the value field is $9\;\text{bytes}$ long and a block pointer is $6 \;\text{bytes}$ long, what is the order of the leaf node?

Which one of the following statements is $\text{FALSE}$?

Consider the table employee(empId, name, department, salary) and the two queries $Q_1, \, Q_2$ below. Assuming that department $5$ has more than one employee, and we want to find the employees who get higher salary than anyone in the department $5,$ which one of the statements is TRUE for any arbitrary employee table? $Q_1:$ Select e.empId From …

Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce? …

Two processes, $P1$ and $P2$, need to access a critical section of code. Consider the following synchronization construct used by the processes: /* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical Section */ wants1 = false; } /* Remainder section */ /* P2 */ while (true) { wants2 = true; while (wants1 == true); /* Critical Section …

A single processor system has three resource types $X, Y$ and $Z$, which are shared by three processes. There are $5$ units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type …

A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements: P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate. Q: Some programs do not exhibit locality of reference. Which one of the following is …

An operating system used Shortest Remaining System Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes: …

In a simplified computer the instructions are: …

Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE?

Consider the grammar with non-terminals $N=\left\{S,C,S_1\right\}$, terminals $T=\left\{a, b, i, t, e\right\}$, with $S$ as the start symbol, and the following set of rules: $S \rightarrow iCtSS_1 \mid a$ $S_1 \rightarrow eS \mid \epsilon$ $C \rightarrow b$ The grammar is NOT LL(1) because:

Consider the following C program segment: int IsPrime (n) { int i, n; for (i=2; i<=sqrt(n);i++) if(n%i == 0) {printf("Not Prime \n"); return 0;} return 1; } Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$. Which of the following is TRUE?

An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE?

Which of the following is TRUE about formulae in Conjunctive Normal Form?