## Gate-2000

Question 1 |

3 | |

8 | |

9 | |

12 |

No. of suits = 4(P)

Apply pigeon hole principal.

Then number of pigeons= n

floor [(n-1)/P] + 1 = 3

floor [(n-1)/P] = 2

floor [(n-1)] =8

floor (n) = 8 + 1

n ≥ 9

Minimum no. of cards, n = 9

Question 2 |

0 | |

n -1 | |

n ^{2} - 3n + 2 | |

Add i

^{th}row and j

^{th}column if we zero, apply to all row and their corresponding column the total becomes zero.

Question 3 |

4 | |

0 | |

15 | |

20 |

Question 4 |

S ⊂ T | |

T ⊂ S | |

S = T | |

S ∩ T = ɸ |

Question 5 |

L = 0 ^{+} | |

L is regular but not 0 ^{+} | |

L is context free but not regular | |

L is not context free |

^{+}.

Question 6 |

01010101 | |

11010101 | |

00101011 | |

10101011 |

Question 7 |

lower the HOLD input | |

lower the READY input | |

raise the HOLD input | |

raise the READY input |

Question 8 |

T1 ≤ T2 | |

T1 ≥ T2 | |

T1 < T2 | |

T1 is T2 plus the time taken for one instruction fetch cycle |

__PIPELINING SYSTEM__:

Pipelining is an implementation technique where multiple instructions are overlapped in execution. It has a high throughput (amount of instructions executed per unit time). In pipelining, many instructions are executed at the same time and execution is completed in fewer cycles. The pipeline is filled by the CPU scheduler from a pool of work which is waiting to occur. Each execution unit has a pipeline associated with it, so as to have work pre-planned. The efficiency of pipelining system depends upon the effectiveness of CPU scheduler.

__NON- PIPELINING SYSTEM__:

All the actions (fetching, decoding, executing of instructions and writing the results into the memory) are grouped into a single step. It has a low throughput.

Only one instruction is executed per unit time and execution process requires more number of cycles. The CPU scheduler in the case of non-pipelining system merely chooses from the pool of waiting work when an execution unit gives a signal that it is free. It is not dependent on CPU scheduler.

Question 9 |

as soon as the TRAP pin becomes ‘high’ | |

by checking the TRAP pin for ‘high’ status at the end of each instruction each | |

by checking the TRAP pin for ‘high’ status at the end of the execution of each instruction | |

by checking the TRAP pin for ‘high’ status at regular intervals |

Question 10 |

X – 3 Y – 2 Z - 1 | |

X – 1 Y – 3 Z - 2 | |

X – 2 Y – 3 Z - 1 | |

X – 3 Y – 1 Z - 2 |

__Indirect addressing__:

Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.

__Immediate addressing__:

Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.

Auto increment or decrements can be one by using loops.

Question 11 |

An array, each element of which is a pointer to a structure of type node | |

A structure of 2 fields, each field being a pointer to an array of 10 elements | |

A structure of 3 fields: an integer, a float, and an array of 10 elements | |

An array, each element of which is a structure of type node |

Question 12 |

X – 1 Y – 3 Z – 2 | |

X – 2 Y – 1 Z – 3 | |

X – 3 Y – 2 Z – 1 | |

X – 3 Y – 1 Z – 2 |

Y → n is pointer to invalid memory, a making it as a dangling pointer.

Z → p is not initialized.

p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.

Question 13 |

X – 1 Y – 2 Z – 3 | |

X – 3 Y – 1 Z – 2 | |

X – 3 Y – 2 Z – 1 | |

X – 2 Y – 3 Z – 1 |

Queus is used in Queue.

Heap is used in heap.

Question 14 |

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, or further nested. Which of the following represents a valid binary tree?

(1 2 (4 5 6 7)) | |

(1 (2 3 4) 5 6) 7) | |

(1 (2 3 4) (5 6 7)) | |

(1 (2 3 NULL) (4 5)) |

(Proper Representation)

Question 15 |

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 statements is true?

t(n) is O(1) | |

n ≤ t(n) ≤ n log _{2} n | |

Question 16 |

multiple variables having the same memory location | |

multiple variables having the same value | |

multiple variables having the same identifier | |

multiple uses of the same variable |

Question 17 |

22 bytes | |

14 bytes | |

18 bytes | |

10 bytes |

max[float, long] = max [4, 8] = 8

Total = short[5] + max[float,long] = 10 + 8 = 18

Question 18 |

3 | |

26 | |

10 | |

21 |

(i) Keyword

(ii) Identifier

(iii) Constant

(iv) Variable

(v) String

(vi) Operator

Print = Token 1

( = Token 2

"i=%d%x" = Token 3 [Anything inside " " is one Token]

, = Token 4

i = Token 5

, = Token 6

& = Token 7

i = Token 8

) = Token 9

; = Token 10

Here, totally 10 Tokens are present in the equation.

Question 19 |

Leftmost derivation | |

Leftmost derivation traced out in reverse | |

Rightmost derivation | |

Rightmost derivation traced out in reverse |

Bottom-Up parser - Reverse of rightmost derivation

Question 20 |

General purpose registers | |

Translation look-aside buffer | |

Program counter | |

All of the above |

Question 21 |

Thrashing | |

Deadlock | |

Starvation, but not deadlock | |

None of the above |

Question 22 |

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

Disk capacities are greater than memory capacities | |

Disk access is much slower than memory access | |

Disk data transfer rates are much less than memory data transfer rates | |

Disks are more reliable than memory |

^{+}trees it is easy to reduce the number of last level access from the disk when the disk size is too large.

Question 23 |

Department address of every employee | |

Employees whose name is the same as their department name | |

The sum of all employees’ salaries | |

All employees of a given department |

Question 24 |

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?

k must be 1 | |

k must be 0 | |

k can take any value between 0 and 1 | |

None of the above |

Question 25 |

0 | |

1 |

_{1}) = Pr(E

_{2}) = a(say)

Pr(E

_{1}∪ E

_{2}) = 1

E

_{1}and E

_{2}are Independent.

P(E

_{1}∪ E

_{2}) = Pr(E

_{1}) + Pr(E

_{2}) - Pr(E

_{1}∩ E

_{2})

1 = a + a - Pr(E

_{1})⋅Pr(E

_{2})

1 = a + a - a⋅a

2a - a

^{2}= 1

a

^{2}- 2a + 1 = 0

(a - 1)

^{2}= 0

a = 1 Pr(E

_{1}) = 1

Answer: Option (D)

Question 26 |

S > T | |

S = T | |

S < T and 2S > T | |

2S ≤ T |

Question 27 |

1 | |

2 | |

3 | |

4 |

Minimum degree of P(x) = 4

Maximum degree of P(x) = 5

Question 28 |

R is not an equivalence relation | |

R is an equivalence relation having 1 equivalence class | |

R is an equivalence relation having 2 equivalence classes | |

R is an equivalence relation having 3 equivalence classes |

It is symmetric R(x+y) is even ⇒ R(x+y) is even then R(y+x) is also v.

It is transitive R(x+y) is even ⇒ R((x+y)+z)) is even then R(x+(y+z)) is also even.

This given relation is equivalence.

Sum of two even numbers are even. Same sum of two odd numbers are even but one even, one odd is odd. It can have two equivalent classes.

Question 29 |

P(P(S)) = P(S) | |

P(S) ∩ P(P(S)) = {ɸ} | |

P(S) ∩ S = P(S) | |

S ∉ P(S) |

S={1}

P(S)=[{ }, {1}]

P(P(S)) = [{ }, {1}, {{ }, 1}, {1, { }}]

Option A: P(P(S)) ≠ P(S) (wrong)

Option B: P(S) ∩ P(P(S)) ≠ ɸ (wrong)

Option C: P(S) ∩ S ≠ P(S) (wrong)

Option D: S ∈ P(S) (wrong)

None of the given is correct.

Question 30 |

True | |

False | |

Same as the truth-value of b | |

Same as the truth-value of d |

Given ⇒ (a∧b) → (a∧c) ∨d

⇒ (a∧b) → (a∧c) ∨d (b⇔c)

⇒ T∨d

⇒ T

Question 31 |

L must be {a ^{n} |n is odd} | |

L must be {a ^{n} |n is even} | |

L must be {a ^{n}|≥0} | |

Either L must be {a ^{n} |n is odd}, or L must be {a^{n} | n is even} |

Question 32 |

Both (P1) and (P2) are decidable | |

Neither (P1) nor (P2) are decidable | |

Only (P1) is decidable | |

Only (P2) is decidable |

For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.

Question 33 |

0 1 0 0 | |

1 1 0 1 | |

1 0 1 1 | |

1 0 0 0 |

Question 34 |

None of the above |

⇒ wy + wz + xy

Question 35 |

1, 0 | |

1, 1 | |

0, 0 | |

0, 1 |

When 11 is applied to Jk flip flop it toggles the value of P so op at P will be 1.

Input to D flip flop will be 0(initial value of P) so op at Q will be 0

Question 36 |

1600 × 400 resolution with 256 colours on a 17 inch monitor | |

1600 × 400 resolution with 16 million colours on a 14 inch monitor | |

800 × 400 resolution with 16 million colours on a 17 inch monitor | |

800 × 800 resolution with 256 colours on a 14 inch monitor |

Option A:

1600×400 = 64000 = 640 KB

256 colours 8 bits = 1 Byte

⇒ 640×1 = 640KB (we have 1MB)

Option B:

1600×400 = 640KB

16 million = 24 bits = 3 bytes

⇒ 640×3 = 1920KB (Not enough)

Option C:

800×400 = 320 KB

16 millions = 3 bytes ⇒ 320×3 = 960 KB (we have 1MB)

Option D:

800×400 = 320 KB

256 colours = 1 Byte ⇒ 320×1 = 320 (we have 1MB)

Question 37 |

X = 1.0, Y = 1.0 | |

X = 1.0, Y = 0.0 | |

X = 0.0, Y = 1.0 | |

X = 0.0, Y = 0.0 |

A = 2.0 * 10

^{30}, C = 1.0

So, A + C should make the 31

^{st}digit to 1, which is surely outside the precision level of A (it is 31

^{st}digit and not 31

^{st}bit). So, this addition will just return the value of A which will be assigned to Y.

So, Y + B will return 0.0 while X + C will return 1.0.

Question 38 |

Rotates s left by k positions | |

Leaves s unchanged | |

Reverses all elements of s | |

None of the above |

Question 39 |

LASTIN = LASTPOST | |

LASTIN = LASTPRE | |

LASTPRE = LASTPOST | |

None of the above |

But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.

Question 40 |

h(n) is O (f(n)) | |

h(n) is O (g(n)) | |

g(n) is not O (f(n)) | |

f(n) is O(g(n)) |

^{10}

Then

f(n) = 3(n

^{32})=3*(2

^{10})

^{32}= 3*2

^{320}

g(n) = 2

^{320}

h(n) = 1024!

So relation between the functions can be:

f(n) and g(n) are of same order, so f(n) is O(g(n)) and g(n)=O(f(n)). Option C is wrong.

h(n) is n! Which is of higher order than f(n) and g(n). So options A and B are wrong.

Question 41 |

_{max}be the edge with maximum weight and e

_{min}the edge with minimum weight. Which of the following statements is false?

Every minimum spanning tree of G must contain e _{min} | |

If e _{max} is in a minimum spanning tree, then its removal must disconnect G | |

No minimum spanning tree contains e _{max} | |

G has a unique minimum spanning tree |

Minimum Spanning Tree:

Question 42 |

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 ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

{u, v} must be an edge in G, and u is a descendant of v in T | |

{u, v} must be an edge in G, and v is a descendant of u in T | |

If {u, v} is not an edge in G then u is a leaf in T | |

If {u, v} is not an edge in G then u and v must have the same parent in T |

In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.

Question 43 |

10 | |

4 | |

6 | |

7 |

i=1; count=1

i=2; count=3

i=3; count=6

i=4; count=10

It return count value is 10.

Question 44 |

* has higher precedence than + | |

- has higher precedence than * | |

+ and – have same precedence | |

+ has higher precedence than * |

Order of precedence is *, +, -.

Here * and + have equal preference, '-' can have higher precedence than + and *.

Question 45 |

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

1.9999 milliseconds | |

1 millisecond | |

9.999 microseconds | |

1.9999 microseconds |

_{1}) + [(1-P)t

_{2}]

= (0.9999*1) + [(1-0.9999) *10000]

= (0.9999) + (0.0001 * 10000)

= 0.9999 + 1

= 1.9999 microseconds

Question 46 |

Release all resources before requesting a new resource | |

Number the resources uniquely and never request a lower numbered resource than the last one requested | |

Never request a resource after releasing any resource | |

Request and all required resources be allocated before execution |

Question 47 |

XY → Z and Z → Y | |

YZ → X and Y → Z | |

YZ → X and X → Z | |

XZ → Y and Y → X |

If for t1[A] = t2[A] then t1[Y] = t2[Y].

Question 48 |

r has no duplicates and s is non-empty | |

r and s have no duplicates | |

s has no duplicates and r is non-empty | |

r and s have the same number of tuples |

Question 49 |

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?

x = 5 not AND (not (x = 5) | |

x = 5 AND x > 4 and x < 6, where x is an integer | |

x ≠ 5 AND not (x = 5) | |

None of the above |

Question 51 |

Theory Explanation is given below. |

A1 is the identity element here. Inverse is does not exist for zero then it is not a group.

Question 52 |

Theory Explanation is given below. |

= multiset of size 4 with exactly one element occurs exactly twice + multiset of size 4 with exactly two element occurs exactly twice.

(b) Infinite, because size of multiset is not given.

Question 54 |

Theory Explanation is given below. |

L = (0+1)* - (0+1)* (00+11) (0+1)*

(b) i≤j as S→aSAb

There will be always for one a in left and minimum one b in right and A→bA|X can generate any no. of b's including Null, if A is X then i=j and if A is generate any b then j>i. So the condition i≤j is true.

Question 55 |

Theory Explanation is given below. |

(b)

Question 57 |

Theory Explanation is given below. |

Question 58 |

Theory Explanation is given below. |

Question 59 |

Theory Explanation is given below. |

So total execution time

= (0.2×5 + 0.8×1) × 2ns

= 3.6 ns

(b) Total branch instructions are 20% as given in previous part. In which 80% are conditional and in which 50% of the conditional branch is taken. So total conditional branch instruction which is taken is

50% of 80% of 20%

0.5×0.8×0.2 = 0.08

And 20% of total branch instruction are not conditional means for that branch is necessarily taken. So total unconditional branch instruction is,

0.2×0.2 = 0.04

Hence, total branch instruction which is taken is,

0.08+0.04 = 0.12

Now lets calculate total execution time,

= (0.12×5 + 0.88×1) × 2ns

= 2.96 ns

Question 60 |

Theory Explanation is given below. |

Dequeue → reverse, pop, reverse

(b) (i) After evaluating 5 2 * 3 4 +

Sol:

7(3+4) 10(5*2)

(ii) After evaluating 5 2 * 3 4 + 5 2

Sol:

25(5*5) 7(3+4) 10(5*2)

(iii) At the end of evaluation

Sol: 80

Question 62 |

Theory Explanation is given below. |

then q[1] = 7; p[7] = 1

At set(3) ⇒ count = 2

then q[2] = 3; p[3] = 2

At set[9] ⇒ count = 3

then q[3] = 9; p[9] = 3;

(b) "The first count elements of

__array q__contains value i such that set (i) has been called".

(c) If set(i) has not been celled for some i, then regardless of what p[i] contains, when we call is set(i) then

if (q[p[i]] ≠ i)

return false;

Will always execute, because if set(i) is not called then p[i]≠count(any) and for then same count q[count]≠i.

So if statement will be true and will return false.

Question 63 |

Theory Explanation is given below. |

(2) f[n-2];

(3) f[n-2] = +;

(b) The time complexity of the resulting program when computing fib(n) is Θ(n).

Question 64 |

Theory Explanation is given below. |

In Bubble sort maximum no. of swap is done when the elements are in non-increasing order, i.e.,

{2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0}

Pass 1 - 9 swaps

Pass 2 - 9 swaps

Pass 3 - 9 swaps

Pass 4 - 4 swaps

Pass 5 - 4 swaps

Pass 6 - 4 swaps

Pass 7 - 4 swaps

Pass 8 - 4 swaps

Pass 9 - 0 swaps

Pass 10 - 0 swaps

Pass 11 - 0 swaps

Total swaps = 47

(b) Same as part (a)

(a)

While traversing the tree we will get value,

E.val = 12

(b) While traversing the parse tree we will get 10 Reductions.

Question 65 |

Theory Explanation is given below. |

Question 67 |

Theory Explanation is given below. |

(ii) Signal (mutex)

(iii) R ⇒ 1 (or) W == 1

(b) In CS, atleast one of the reader is always present. That means writer can't be enter into the critical section.

This leads to readers-writers problem may occur in the queue.

Question 68 |

Theory Explanation is given below. |

(i)

(ii)

(b)