GATE CS question library

Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is always true?

In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent?

Given relations r(w, x) and s(y, z) the result of select distinct w, x from r, s is guaranteed to be same as r, provided.

Given the following relation instance. $$\begin{array}{|l|l|}\hline \text{X} & \text{Y} & \text{Z} \\ \hline \text{1} & \text{4} & \text{2} \\ \text{1} & \text{5} & \text{3} \\ \text{1} & \text{6} & \text{3} \\ \text{3} & \text{2} & \text{2} \\ \hline \end{array}$$ Which of the following functional dependencies are …

Which of the following is not a valid deadlock prevention scheme?

Suppose the time to service a page fault is on the average $10$ milliseconds, while a memory access takes $1$ microsecond. Then a $99.99\%$ hit ratio results in average memory access time of

Given the following expression grammar: $$\begin{align} E &\to E * F \mid F + E \mid F \\[1em] F &\to F - F \mid id \end{align}$$ Which of the following is true?

The value of $j$ at the end of the execution of the following C program: int incr (int i) { static int count = 0; count = count + i; return (count); } main () { int i, j; for (i = 0; i <= 4; i++) j = incr (i); } is:

Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of the following statements is false?

Consider the following functions $f(n) = 3n^{\sqrt{n}}$ $g(n) = 2^{\sqrt{n}{\log_{2}n}}$ $h(n) = n!$ Which of the following is true?

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the following is always true?

Suppose you are given an array $s[1....n]$ and a procedure reverse $(s, i, j)$ which reverses the order of elements in $s$ between positions $i$ and $j$ (both inclusive). What does the following sequence do, where $1 \leqslant k \leqslant n$: reverse (s, 1, k); reverse (s, k+1, n); reverse (s, 1, n);

Consider the values of $A = 2.0 \times 10^{30}, B = -2.0 \times 10^{30}, C = 1.0,$ and the sequence X:= A + B Y:= A + C X:= X + C Y:= Y + B executed on a computer where floating point numbers are represented with $32$ bits. The values for $X$ and $Y$ will be

A graphics card has on board memory of $1$ MB. Which of the following modes can the card not support?

The following arrangement of master-slave flip flops has the initial state of $P, Q$ as $0, 1$ (respectively). After three clock cycles the output state $P, Q$ is (respectively),

Which functions does NOT implement the Karnaugh map given below?

The simultaneous equations on the Boolean variables $x, y, z$ and $w$, $x + y + z = 1$ $xy = 0$ $xz + w = 1$ $xy + \bar{z}\bar{w} = 0$ have the following solution for $x, y, z$ and $w,$ respectively:

Consider the following decision problems: $(P1):$ Does a given finite state machine accept a given string? $(P2):$ Does a given context free grammar generate an infinite number of strings? Which of the following statements is true?

Let $a, b, c, d$ be propositions. Assume that the equivalence $a ⇔ ( b \vee \neg b)$ and $b ⇔c$ hold. Then the truth-value of the formula $(a ∧ b) → (a ∧ c) ∨ d$ is always

What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states?