GATE CS question library

Let $P(S)$ denotes the power set of set $S.$ Which of the following is always true?

A relation $R$ is defined on the set of integers as $xRy$ iff $(x + y)$ is even. Which of the following statements is true?

A polynomial $p(x)$ satisfies the following: $p(1) = p(3) = p(5) = 1$ $p(2) = p(4) = -1$ The minimum degree of such a polynomial is

Let $S = \sum_{i=3}^{100} i \log_{2} i$, and $T = \int_{2}^{100} x \log_{2}x dx$. Which of the following statements is true?

X, Y and Z are closed intervals of unit length on the real line. The overlap of X and Y is half a unit. The overlap of Y and Z is also half a unit. Let the overlap of X and Z be k units. Which of the following is true?

Given the relations employee (name, salary, dept-no), and department (dept-no, dept-name,address), Which of the following queries cannot be expressed using the basic relational algebra operations $\left(\sigma, \pi,\times ,\Join, \cup, \cap,-\right)$?

B$^{+}$-trees are preferred to binary trees in databases because

Let $m[0]\ldots m[4]$ be mutexes (binary semaphores) and $P[0]\ldots P[4]$ be processes. Suppose each process $P[i]$ executes the following: wait (m[i]); wait (m(i+1) mod 4]); ........... release (m[i]); release (m(i+1) mod 4]); This could cause

Which of the following derivations does a top-down parser use while parsing an input string? The input is scanned from left to right.

Which of the following need not necessarily be saved on a context switch between processes?

The number of tokens in the following C statement is printf("i=%d, &i=%x", i, &i);

Aliasing in the context of programming languages refers to

Consider the following C declaration: struct { short x[5]; union { float y; long z; } u; )t; Assume that the objects of the type short, float and long occupy $2$ bytes, $4$ bytes and $8$ bytes, respectively. The memory requirement for variable $t$, ignoring alignment consideration, is:

Let $S$ be a sorted array of $n$ integers. Let $T(n)$ denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than $1000$ in $S$. Which of the following statement is true?

Consider the following nested representation of binary trees: $(X \ Y \ Z)$ indicates $Y$ and $Z$ are the left and right subtrees, respectively, of node $X$. Note that $Y$ and $Z$ may be $NULL$, or further nested. Which of the following represents a valid binary tree?

The most appropriate matching for the following pairs $$\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\ \hline \text{Y: breadth first search} & \text{2: queue} \\ \hline \text{Z: sorting} & \text{3: stack} \\ \hline \end{array}$$ is:

The most appropriate matching for the following pairs …

The most appropriate matching for the following pairs$$\begin{array}{ll} \text{X: Indirect addressing} & \text{1: Loops } \\ \text{Y: Immediate addressing } & \text{2: Pointers} \\ \text{Z: Auto decrement addressing } & \text{3: Constants } \\ \end{array}$$ is

The following C declarations: struct node { int i: float j; }; struct node *s[10]; define s to be:

Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-pipelined but identical CPU, we can say that