GATE CSE 2000 PYQ

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

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 stat

Consider the following functions Which of the following is true?

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 af

Given the following expression grammar: Which of the following is true?

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

The 8085 microprocessor responds to the presence of an interrupt

To put the 8085 microprocessor in the wait state

The most appropriate matching for the following pairs is:

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

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

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.

-trees are preferred to binary trees in databases because

Given the following relation instance. Which of the following functional dependencies are satisfied by the instance?

Which functions does NOT implement the Karnaugh map given below?

Consider the values of , 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

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

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),

The number 43 in 2's complement representation is

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

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is

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 af

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

Let a, b, c, d be propositions. Assume that the equivalence hold. Then the truth-value of the formula is always

Let , and Which of the following statements is true?

The determinant of the matrix

Let P(S) denotes the power set of set S. Which of the following is always 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

The most appropriate matching for the following pairs is:

and are events in a probability space satisfying the following constraints: and are independent The value of Pr ( E_{1} ), the probability of the event E_{1}, is

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

Let be mutexes (binary semaphores) and 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

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

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, wh

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 = in

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

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?

The most appropriate matching for the following pairs is:

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. Whic

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

Aliasing in the context of programming languages refers to

An array is defined as follows: for all The sum of the elements of the array is

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

Let L denote the languages generated by the grammar . Which of the following is TRUE?

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 fo

Let S and T be languages over represented by the regular expressions , respectively. Which of the following is true?