GATE CS question library

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:

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates?

Consider the following declaration of a two-dimensional array in C: char $a[100][100]$; Assuming that the main memory is byte-addressable and that the array is stored starting from memory address $0$, the address of $a [40][50]$ is:

Horizontal microprogramming:

The performance of a pipelined processor suffers if:

The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output