GATE CS question library

A processor uses $2-level$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $32$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $10$ most significant bits of the virtual address are used as index into …

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable. Which of the following CANNOT be true?

Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\}$ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ …

The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is represented by binary notation) is

If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

From the following instance of a relation schema $R(A,B,C)$, we can conclude that: $$\begin{array}{|l|l|}\hline \textbf{A} & \textbf{B} & \textbf{C} \\ \hline \text{1} & \text{1} & \text{1} \\ \text{1} & \text{1} & \text{0} \\ \text{2} & \text{3} & \text{2} \\ \text{2} & \text{3} & \text{2} \\ \hline \end{array}$$

Relation $R$ is decomposed using a set of functional dependencies, $F$, and relation $S$ is decomposed using another set of functional dependencies, $G$. One decomposition is definitely $\text{BCNF}$, the other is definitely $3NF$, but it is not known which is which. To make a guaranteed identification, which one of the following tests should be …

A $B^+$ - tree index is to be built on the Name attribute of the relation STUDENT. Assume that all the student names are of length $8$ bytes, disk blocks are of size $512$ bytes, and index pointers are of size $4$ bytes. Given the scenario, what would be the best choice of the degree (i.e. number of pointers per node) of the $B^+$ - tree?

In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on

Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? More than one program may be loaded into main memory at the same time for execution If a program waits for certain events such as I/O, another program is immediately scheduled for execution If the execution of a program terminates, another program is …

Dynamic linking can cause security concerns because

To evaluate an expression without any embedded function calls

The C language is:

The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is

Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is

The smallest finite automaton which accepts the language $\{x \mid$ length of $x$ is divisible by $3\}$ has

Which of the following is true?

The running time of the following algorithm Procedure $A(n)$ If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$; is best described by

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

The number of leaf nodes in a rooted tree of n nodes, with each node having $0$ or $3$ children is: