GATE CS question library

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? $2$-phase locking Time-stamp ordering

A relational schema for a train reservation database is given below. passenger(pid, pname, age) reservation(pid, class, tid) …

Consider a $B^+$-tree in which the maximum number of keys in a node is $5$. What is the minimum number of keys in any non-root node?

Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Which one of the following is not a client-server application?

Which languages necessarily need heap allocation in the runtime environment?

Which data structure in a compiler is used for managing information about variables and their attributes?

Two alternative packages $A$ and $B$ are available for processing a database having $10^k$ records. Package $A$ requires $0.0001 n^2$ time units and package $B$ requires $10n\log_{10} n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$?

What does the following program print? #include<stdio.h> void f(int *p, int *q) { p=q; *p=2; } int i=0, j=1; int main() { f(&i, &j); printf("%d %d\n", i,j); return 0; }

In a binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

The Boolean expression of the output $f$ of the multiplexer shown below is

$P$ is a $16$-bit signed integer. The $2$'s complement representation of $P$ is $(F87B)_{16}$. The $2$'s complement representation of $8\times P$ is

The main memory unit with a capacity of $4$ $\text{megabytes}$ is built using $1\text{M} \times \text{1-bit}$ DRAM chips. Each DRAM chip has $1\text{K}$ rows of cells with $1\text{K}$ cells in each row. The time taken for a single refresh operation is $100\; \text{nanoseconds}$. The time required to perform one refresh operation on all the cells …

The minterm expansion of $f(P,Q,R) = PQ +Q \bar{R}+P\bar{R}$ is

Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$. Which one of the statements below expresses best the meaning of the formula, $\qquad∀x∃y∃t(¬F(x,y,t))$

Consider the following matrix $$A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$$ If the eigenvalues of A are $4$ and $8$, then

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$

What is the probability that divisor of $10^{99}$ is a multiple of $10^{96}$?

Consider a company that assembles computers. The probability of a faulty assembly of any computer is $p$. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of $q$. What is the probability of a computer being declared faulty?

What is the value of $\displaystyle\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$ ?