## Gate-2002

Question 2 |

The trapezoidal rule for integration gives exact result when the integrand is a polynomial of degree

0 but not 1 | |

1 but not 0 | |

0 or 1 | |

2 |

Question 3 |

^{k}) = 3T(2

^{k-1}) + 1, T(1) = 1 is

^{k})=3T(2

^{k-1})+1

T(1)=1

k=0; T(1)=3T(2

^{-1})+1

k=1; T(2)=3T(2

^{0})+1=3(1)+1=4

k=2; T(4)=3T(2

^{1})+1=3(4)+1=13

k=3; T(8)=3T(2

^{2})+1=3(13)+1=40

k=4; T(16)=3T(2

^{3})+1=3(40)+1=121

Simply go through the options.

Option B:

k=4 ⇒ (3

^{4+1}-1)/2

⇒ (243-1)/2

⇒ 121

Question 4 |

2 | |

3 | |

4 | |

n - 2[n/2] + 2 |

Question 5 |

log n | |

n/2 | |

(log _{2})^{n} - 1 | |

n |

Question 6 |

The set of all rational negative numbers forms a group under multiplication. | |

The set of all non-singular matrices forms a group under multiplication. | |

The set of all matrices forms a group under multiplication. | |

Both B and C are true. |

a. Closure: result of a * b must be in group G.

b. There must be an identity element i.e. e * a = a * e = a

c. There must be an inverse element b for every element a such that a * b = b * a = e

d. Associativity i.e. (a * b) * c = a * (b * c)

Rational negative numbers don't form a group under multiplication, as multiplying two negative numbers results into a positive number, so closure property is not satisfied.

Set of non-singular matrices forms a group under multiplication.

The set of all matrices doesn't form a group under multiplication, since there may not be an inverse for a matrix (in particular, for singular matrices).

Question 7 |

Context free | |

Regular | |

Deterministic Context free | |

Recursive |

Question 8 |

(X∧¬Z)→Y | |

(X∧Y)→¬Z | |

X→(Y∧¬Z) | |

(X→Y)∧¬Z |

⇒ Z ∨ ¬X ∨ Y

⇒ ¬X ∨ Z ∨ Y

Option A:

(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.

Question 9 |

HOLD is active | |

READY is active | |

None of the above |

Question 10 |

Only PCHL instruction | |

Only ADD instructions | |

Only JMP and CALL instructions | |

All instructions |

ADD Instruction: increments the program counter.

JMP & CALL: Change the values of PC.

Question 11 |

Receiver is to be synchronized for byte reception | |

Receiver recovers lost ‘0’s and ‘1’s from these padded bits | |

Padded bits are useful in parity computation | |

None of the above |

Question 13 |

instruction cache | |

instruction register | |

instruction opcode | |

translation look-a-side buffer |

Question 14 |

is equivalent to the binary value 0.1 | |

is equivalent to the binary value 0.01 | |

is equivalent to the binary value 0.00111… | |

cannot be represented precisely in binary |

__:__

**1**^{st}Multiplication iterationMultiply 0.25 by 2.

0.25×2 = 0.50 (product)

Fractional part = 0.50

Carry = 0

__:__

**2**^{nd}Multiplication iterationMultiply 0.50 by 2.

0.50×2 = 1.00 (product)

Fractional part = 0.00

Carry = 1

The fractional part in the 2

^{nd}iteration becomes zero and so we stop the multiplication iteration.

Carry from 1

^{st}multiplication iteration becomes MSB and carry from 2

^{nd}iteration becomes LSB. So the result is 0.01.

Question 15 |

1111 | |

11111 | |

111111 | |

10001 |

-15 = 11111

1's complement = 10000

2's complement = 10001

Question 16 |

floating point multiplication | |

signed 16 bit integer addition | |

arithmetic left shift | |

converting a signed integer from one size to another |

Question 17 |

At most one activation record exists between the current activation record and the activation record for the main | |

The number of activation records between the current activation record and the activation record for the main depends on the actual function calling sequence. | |

The visibility of global variables depends on the actual function calling sequence. | |

Recursion requires the activation record for the recursive function to be saved on a different stack before the recursive fraction can be called. |

Question 18 |

Do not differ | |

Differ in the presence of loops | |

Differ in all cases | |

May differ in the presence of exception |

Question 19 |

Zero | |

More than zero but less than that of an equivalent 3NF decomposition | |

Proportional to the size of F ^{+} | |

Indetermine |

Question 20 |

Relational algebra is more powerful than relational calculus. | |

Relational algebra has the same power as relational calculus. | |

Relational algebra has the same power as safe relational calculus. | |

None of the above. |

A query can be formulated in safe Relational Calculus if and only if it can be formulated in Relational Algebra.

Question 21 |

is flagged whenever there is carry from sign bit addition | |

cannot occur when a positive value is added to a negative value | |

is flagged when the carries from sign bit and previous bit match | |

None of the above |

Question 22 |

Round Robin | |

First-In First-Out | |

Multilevel Queue Scheduling | |

Multilevel Queue Scheduling with Feedback |

Question 23 |

Has not been used for the longest time in the past. | |

Will not be used for the longest time in the future. | |

Has been used least number of times. | |

Has been used most number of times. |

Question 24 |

the operand is inside the instruction | |

the address of the operand is inside the instruction | |

the register containing the address of the operand is specified inside the instruction | |

the location of the operand is implicit |

The operand is inside the instruction --- absolute addressing.

The register containing the address of the operand is specified inside the instruction --- Register addressing.

The location of the operand is implicit --- Implicit addressing.

Question 25 |

Question 26 |

Σ(1,4,5) | |

Σ(6,7) | |

Σ(0,1,3,5) | |

None of the above |

_{1}', (x,y,z) ⋅ f

_{2}'(x,y,z) + f

_{3}'(x,y,z))

= (Σ(0,1,3,5) ⋅ Σ(6,7) + Σ(1,4,5))

[Σ(0,1,3,5) and Σ(6,7) ⇒ No common terms]

= (Σ(1,4,5))

Question 27 |

xyz' | |

xy+z | |

x+y | |

None of the above |

_{0}'10 + A'A

_{0}'11 + A'A

_{0}'12 + A

_{1}A

_{0}13) EN

F = (xyz' + xyz + y'zy + zy')z'

= (xyz' + xyz + y'z(y+1))z'

= (xyz' + xyz + y'z)z'

= (xy(z+z') + y'z)z'

= (xy + y'z)z'

= (xyz' + y'zz')

= (xyz')

Question 28 |

x'+z | |

xyz | |

xy'+z | |

None of the above |

⇒ f(f((x+y), y), z)

⇒ f(((x+y)' + y), z)

⇒ f(((x'⋅y') + y), z)

⇒ f((x'⋅y') + y), z)

⇒ ((x'⋅y') + y)' + z

⇒ (x'⋅y')⋅y' + z

⇒ (x+y)⋅y' + z

⇒ (xy'+yy') + z

⇒ xy' + z

Question 29 |

AC = 0 and CY =0 | |

AC = 1 and CY =1 | |

AC = 1 and CY =0 | |

AC = 0 and CY =1 |

⇒ H = 0101 1101

MOV L, 6BH

⇒ L = 0110 1011

MOV A, H

A = 0101 1101

ADD L ⇒ A+L =

Here, AC=1; CY=0

Question 30 |

Outputs the sum of the present and the previous bits of the input. | |

Outputs 01 whenever the input sequence contains 11 | |

Outputs 00 whenever the input sequence contains 10 | |

None of the above |

(A,1) = (B, 01)

Previous input + Present input = 0+1 = 01

(B,0) = (A, 01)

Previous input + Present input = 1+0 = 01

(A,0) = (A, 00)

Previous input + Present input = 0+0 = 00

(A,1) = (B, 01)

Previous input + Present input = 0+1 = 01

(B,1) = (C, 10)

Previous input + Present input = 1+1 = 10

(C,1) = (C, 10)

Previous input + Present input = 1+1 = 10

Question 31 |

the pipeline stages have different delays | |

consecutive instructions are dependent on each other | |

the pipeline stages share hardware resources | |

All of the above |

If pipeline stages can’t have different delays, no dependency among consecutive instructions and sharing of hardware resources should not be there.

Question 32 |

does not require use of signal decoders | |

results in larger sized microinstructions than vertical microprogramming | |

uses one bit for each control signal | |

all of the above |

Question 33 |

4040 | |

4050 | |

5040 | |

5050 |

= 0 + [40 * 100 * 1] + [50 * 1]

= 4000 + 50

= 4050

Question 34 |

Question 36 |

O(n) | |

O(log n) | |

O(log log n) | |

O(1) |

Let n=2

^{m}

So, T(2

^{m}) = T(2

^{m/2})+1

We substitute T(2

^{m}) = S(m),

So now the equation becomes,

S(m) = S(m/2)+1

Now after applying master's theorem,

S(m) = O(log m)

T(n) = O(log log n)

Question 37 |

No. of nodes in left sub tree = 2 right sub tree

No. of nodes in left sub tree = (n-1/3)

No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log

_{3/2}n

Question 38 |

2 states | |

3 states | |

4 states | |

5 states |

Minimum no. of states that we require is "3".

Question 39 |

The complement of a recursive language is recursive. | |

The complement of a recursively enumerable language is recursively enumerable. | |

The complement of a recursive language is either recursive or recursively enumerable. | |

The complement of a context-free language is context-free. |

Question 41 |

^{2}= 16

Atleast one head = 1/16

Atleast one tail = 1/16

Probability of getting one head and one tail is = 1 - 1/16 - 1/16 = 16-1-1/16 = 14/16 = 7/8

Question 42 |

Neither reflexive nor symmetric | |

Symmetric and reflexive | |

Transitive and reflexive | |

Transitive and symmetric |

A×S = {(ɸ,1), (ɸ,2), (ɸ,3), (1,ɸ), (2,ɸ), (3,ɸ)}

Not reflexive = (1,1), (2,2), (3,3) not there

Symmetric: if (a,b) is present then (b,a) is also present

Transitive: True; if (x,y), (y,z) then (z,x) is also present

Question 43 |

A context free language | |

A context sensitive language | |

A regular language | |

Parsable fully only by a Turing machine |

Question 44 |

One stack is enough | |

Two stacks are needed | |

As many stacks as the height of the expression tree are needed | |

A Turning machine is needed in the general case |

Question 45 |

Security is dynamic | |

The path for searching dynamic libraries is not known till runtime | |

Linking is insecure | |

Cryptographic procedures are not available for dynamic linking |

Question 46 |

A | |

A and B | |

A and C | |

A, B and C |

Question 47 |

the size of the blocks, and the size of the address of the blocks. | |

the number of blocks used for the index, and the size of the blocks. | |

the size of the blocks, the number of blocks used for the index, and the size of the address of the blocks. | |

None of the above |

No. of block addresses available for addressing one file(B) = No. of Maximum blocks we can use for the Index * No. of addressable blocks using one Index block(A)

Size of File = B * Size of Block

Question 48 |

A B^{+}- tree index is to be built on the *Name* attribute of the relation *STUDENT*. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B^{+}-tree?

16 | |

42 | |

43 | |

44 |

Then,

8(P-1) + 4P ≤ 512

12P - 8 ≤ 512

12P ≤ 520

P ≤ 43.33

P = 43

Question 49 |

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 BCNF, the other is definitely 3NF, but it is not known which is which. To make a __quaranteed__ identification, which one of the following tests should be used on the decompositions? (Assume that the closures of F and G are available).

Dependency-preservation | |

Lossless-join | |

BCNF definition | |

3NF definition |

Question 50 |

A functionally determines B and B functionally determines C | |

A functionally determines B and B does not functionally determines C | |

B does not functionally determines C | |

A does not functionally determines B and B does not functionally determines C |

But for the given instance it can be seen that B does not functionally determines C, and it can be concluded for entire relation

Question 52 |

Theory explanation is given below. |

The given relation S is irreflexive because no diagonal elements are present in the relation i.e., (x,x)∉R, ∀x∈A

If a relation is equivalence then it is

Reflexive

Symmetric

Transitive

Given relation S is not Reflexive & Transitive.

Reflexive closure on S = {(1,1), (2,2), (3,3), (1,2), (2,1)}

Transitive closure on S is does not change after performing reflexive closure on S.

S = {(1,1), (2,2), (3,3), (1,2), (2,1)}

(b) Given S = {a,b}

Powerset of S i.e., P(S) = {(ɸ), (a), (b), (a,b)}

__Hasse diagram__:

Question 53 |

Theory Explanation is given below. |

Eigen value of upper/ lower triangular matrix are the diagonal elements of matrix.

(b) (i) A↔(A∨A): This can tells that if A then (A or A)and if (A or A) then A. It represents result as a tautology.

(ii) (A∨B)→B: This is neither tautology nor contradiction.

(iii) A∧(¬(A∨B)): here when A is true then (¬(A∨B)) is false, then it results contradiction.

Question 54 |

Theory Explanation is given below. |

Total 5 binary trees are possible with the preorder C, B, A.

Question 55 |

Theory Explanation is given below. |

Theory Explanation is given below. |

Question 59 |

Theory Explanation is given below. |

move disk from source to dest //Step-2

move (disk-1, aux, dest, source) //Step-3

Recurrence: 2T(n - 1) + 1

T(n) = 2T (n - 1) + 1

= 2[2T(n - 2) + 1] + 1

= 2

^{2}T(n - 2) + 3

⁞

2

^{k}T(n - k) + (2

^{k}- 1)

= 2

^{n-1}T(1) + (2

^{n-1}- 1)

= 2

^{n-1}+ 2

^{n-1}- 1

= 2

^{n}- 1

≅ O(2

^{n})

void move (int n, char A, char B, char C) {

if (n>0)

move(n-1, A, C, B);

printf("Move disk%d from pole%c to pole%c\n", n,A,C);

move(n-1, B, A, C);

}

}

Question 60 |

Theory Explanation is given below. |

{ for j = 1 ... n

{ if a[i,j] = 0 then P[i,j] =

__infinite__;

else P[i,j] =

__a[i,j]__;

}

}

(b) ALGORITHM: For i = 1 ... n

{ for j = 1 ... n;

{ for k = 1 ... n

{

P[

__i__,

__j__] = min (

__P[i,j]__,

__P[i,k]+P[k,j]__)

}

}

}

(c) Actual graph:

MST: There are 2 possible MST's