GATE 2000 CSE & IT

Let $$S = \left\{ {0,1,2,3,4,5,6,7} \right\}$$ and $$ \otimes $$ denote multiplication modulo $$8$$, that is, $$x \otimes y = \left( {xy} \right)$$ mod $$8$$ (a) Prove that $$\left...

Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverse the order of elements in s between positions i and j (both inclusive). What does the followin...

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

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

An $$n\,\, \times \,\,n$$ array v is defined as follows v[i, j] = i - j for all i, j, $$1\,\, \le \,\,i\,\, \le \,\,n,\,1\,\, \le \,\,j\,\, \le \,\,n$$ The sum of elements of the a...

The simultaneous equations on the Boolean variables $$x, y, z$$ and $$w,$$ $$$x+y+z=1$$$ $$$xy=0$$$ $$$xz+w=1$$$ $$$xy + \overline z \overline w = 0$$$ have the following for $$x,...

Consider the following C declaration struct { short s[5]; union { float y; long z; } u; }t; Assume that objects of the type short, float and long occupy 2 bytes, 4 bytes and 8 byte...

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

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

An n $$\times$$ n array v is defined as follows V [i, j] = i - j for all i, j, $$1 \le i \le n,\,1 \le j \le n$$ The sum of the elements of the array v is

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

The determinant of the matrix $$$\left[ {\matrix{ 2 & 0 & 0 & 0 \cr 8 & 1 & 7 & 2 \cr 2 & 0 & 2 & 0 \cr 9 & 0 & 6 & 1 \cr } } \right]\,\,is$$$

B + -trees are preferred to binary trees in databases because

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

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 (unvisite...

Given the relations employee (name, salary, deptno) , and department (deptno, deptname, address) Which of the following queries cannot be expressed using the basic relational algeb...

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

Let m[0] ..m[4] be mutexes (binary semaphores) and P[0] ...P[4] be processes. Suppose each process P[i] executes the following: wait (m[i]); wait (m(m[(i+1) mod 4]))0; ....... rele...

A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset is the number of elements in it counting repetitions. (a) wha...

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

Given the following relation instance $$\eqalign{ & X\,\,\,\,\,Y\,\,\,\,\,Z \cr & \,\,1\,\,\,\,\,\,4\,\,\,\,\,\,2 \cr & \,\,1\,\,\,\,\,\,5\,\,\,\,\,\,3 \cr & \,\,1\,\,\,\,\,\,6\,\,...

The number $$43$$ in $$2's$$ complement representation 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 o...

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

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements...

The most appropriate matching for the following pairs $$X:$$ Indirect addressing $$Y:$$ Immediate addressing $$Z:$$ Auto decrement addressing is $$1:$$ Loops $$2:$$ Pointers $$3.$$...

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, o...

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

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

Let $$a, b, c, d$$ be propositions. Assume that the equivalences $$a \leftrightarrow \left( {b \vee \neg b} \right)$$ and $$b \leftrightarrow c$$ hold. Then the truth value of the...

An instruction pipeline has five stages where each stage takes $$2$$ nanoseconds and all instructions use all five stages. Branch instructions are not overlapped, i.e., the instruc...

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

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

The most appropriate matching for the following pairs X: m=malloc(5); m= NULL; Y: free(n); n->value = 5; Z: char *p; *p='a'; 1: using dangling 2: using uninitialized pointers 3. lo...

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

$${{E_1}}$$ and $${{E_2}}$$ are events in a probability space satisfying the following constraints: $$ \bullet $$ $$\Pr \,\,({E_1}) = \Pr \,({E_2})$$ $$ \bullet $$ $$\Pr \,\,({E_1}...

The solution to the recurrence equation $$T\left( {{2^k}} \right)$$ $$ = 3T\left( {{2^{k - 1}}} \right) + 1$$, $$T\left( 1 \right) = 1$$ is:

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

Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is true?

Consider the following decision problems : $${P_1}$$ Does a given finite state machine accept a given string $${P_2}$$ Does a given context free grammar generate an infinite number...

Let $$S$$ and $$T$$ be languages over $$\sum { = \left\{ {a,b} \right\}} $$ represented by the regular expressions $${\left( {a + {b^ * }} \right)^ * }$$ and $$\,{\left( {a + b} \r...