## Gate 2014 Set -02

Question 1 |

It was a former British colony | |

Indian Information Technology professionals have colonized the world | |

India does not follow any colonial practices | |

India has helped other countries gain freedom |

Question 1 Explanation:

India is a post-colonial (or) existing after the end of cononial rule.

India is a post-colonial country because "It was a former British colony" that means if a country is called post colonial then it came into existence after the colonies rules and it can become a independent.

India is a post-colonial country because "It was a former British colony" that means if a country is called post colonial then it came into existence after the colonies rules and it can become a independent.

Question 2 |

Who ___________ was coming to see us this evening?

you said | |

did you say | |

did you say that | |

had you said |

Question 2 Explanation:

From the given options, option B is make the sentence to be fullfilled.

Question 3 |

1 : S, 2 : P, 3 : Q, 4 : R | |

1 : P, 2 : Q, 3 : R, 4 : S | |

1 : Q, 2 : R, 3 : S, 4 : P | |

1 : S, 2 : P, 3 : R, 4 : Q |

Question 3 Explanation:

Eradicate = destroy utterly

Distort = misrepresent

Saturate = Soak completely

Utilize = use

Distort = misrepresent

Saturate = Soak completely

Utilize = use

Question 4 |

What is the average of all multiples of 10 from 2 to 198?

90 | |

100 | |

110 | |

120 |

Question 4 Explanation:

Average of 10, 20, 30, ..., 180, 190

Average = 10+20+30+...+180+190 / 19 = (19/2 [10+190]) / 19 = 100

Average = 10+20+30+...+180+190 / 19 = (19/2 [10+190]) / 19 = 100

Question 5 |

3.464 | |

3.932 | |

4.000 | |

4.444 |

Question 5 Explanation:

Let,

Squaring on both sides,

x

x

(x-4) (x+3) = 0

∴ x = 4 (x ≠ -3)

Squaring on both sides,

x

^{2}= 12+xx

^{2}- x - 12 = 0(x-4) (x+3) = 0

∴ x = 4 (x ≠ -3)

Question 6 |

The old city of Koenigsberg, which had a German majority population before World War 2, is now called Kaliningrad. After the events of the war, Kaliningrad is now a Russian territory and has a predominantly Russian population. It is bordered by the Baltic Sea on the north and the countries of Poland to the south and west and Lithuania to the east respectively. Which of the statements below can be inferred from this passage?

Kaliningrad was historically Russian in its ethnic make up | |

Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia | |

Koenigsberg was renamed Kaliningrad, as that was its original Russian name | |

Poland and Lithuania are on the route from Kaliningrad to the rest of Russia |

Question 6 Explanation:

Kaliningrad is a part of Russia despite it not being contiguous with rest of Russia because it is surrounded by countries of Poland in the south and west, Lithuania in the east and Baltic sea on north, and it has a predominantly Russian population.

Question 7 |

A high proportion of the affected population has returned from neighbouring countries where dengue is prevalent | |

More cases of dengue are now reported because of an increase in the Municipal Office’s administrative efficiency | |

Many more cases of dengue are being diagnosed this year since the introduction of a new and effective diagnostic test | |

The number of people with malarial fever (also contracted from mosquito bites) has increased this year |

Question 7 Explanation:

Malarial fever and dengue fever both are contracted from mosquito bites. So as the mosquito population has increased then the number of people suffering from dengue and malarial fever also increased.

Question 8 |

If x is real and |x

^{2}- 2x + 3| = 11, then possible values of |- x^{3}+ x^{2}- x| include2, 4 | |

2, 14 | |

4, 52 | |

14, 52 |

Question 8 Explanation:

Given,

|x

x

x

(x-4)(x+2) = 0

x = 4, -2

x

x

x is not real in this case.

|-x

when x=-2

⇒ |-(-2)

= |(-(8) + (4) + 2| = 14

x=4

⇒ |-(4)

= |-64 + 16 -4|

= 52

Possible values of |-x

|x

^{2}- 2x + 3| = 11, x is realx

^{2}-2x+3 = 11x

^{2}-2x+8 = 0(x-4)(x+2) = 0

x = 4, -2

x

^{2}-2x+3 = -11x

^{2}-2x+14 = 0x is not real in this case.

|-x

^{3}+x^{2}-x|when x=-2

⇒ |-(-2)

^{3}+(-2)^{2}-(-2)|= |(-(8) + (4) + 2| = 14

x=4

⇒ |-(4)

^{3}+(4)^{2}-(4)|= |-64 + 16 -4|

= 52

Possible values of |-x

^{3}+x^{2}-x| include 14, 52.Question 9 |

140 | |

141 | |

142 | |

143 |

Question 9 Explanation:

Number of male in 2008 = x

Number of female in 2008 = y

Number of female in 2009 = 2y

Given,

x/y = 2.5 ⇒ y = 2x/5

Let, number of male in 2009 = M

Given, M/2y = 3

M/2(2x/5) = 3 ⇒ M = 12x/5

Percentage increase = M-x/x × 100

= 12x/5-x/ x × 100

= 7/5 × 100

= 140%

Number of female in 2008 = y

Number of female in 2009 = 2y

Given,

x/y = 2.5 ⇒ y = 2x/5

Let, number of male in 2009 = M

Given, M/2y = 3

M/2(2x/5) = 3 ⇒ M = 12x/5

Percentage increase = M-x/x × 100

= 12x/5-x/ x × 100

= 7/5 × 100

= 140%

Question 10 |

At what time between 6 a.m. and 7 a.m. will the minute hand and hour hand of a clock make an angle closest to 60°?

6:22 am | |

6:27 am | |

6:38 am | |

6:45 am |

Question 10 Explanation:

At 6 a.m., the angle between minute hand and hour hand is 180°.

And for every minute, the angle between them decreases by 6° - (1/2)° = 5 (1/2)°

∴ For the angle to be closest to 60°, the angle must be reduced by atmost 120°.

1 min - 5(1/2)°

x min - 120°

x = 2/11 × 120 = 240/11 = 21.81 m ≈ 22 min

i.e. 6.22 a.m. the angle between minute hand and hour hand will be closest to 60°.

And for every minute, the angle between them decreases by 6° - (1/2)° = 5 (1/2)°

∴ For the angle to be closest to 60°, the angle must be reduced by atmost 120°.

1 min - 5(1/2)°

x min - 120°

x = 2/11 × 120 = 240/11 = 21.81 m ≈ 22 min

i.e. 6.22 a.m. the angle between minute hand and hour hand will be closest to 60°.

Question 11 |

The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functional be denoted by p. Then 100p =_____________.

11.90 | |

11.91 | |

11.92 | |

11.93 |

Question 11 Explanation:

There are 10 systems.

Out of which ‘4’ are chosen at random without replaced and created.

If at least three of them are working then system is deemed functional

i.e., there should be only ‘one’ non-working system in set of ‘4’.

It is possible with combination

W – W – W – N,

W – W – N – W,

W – N – W – W,

N – W – W – W.

For W – W – W – N, the probability = (choosing working out of 10) × (choosing working out of 9) × (choosing working out of 8) × (choosing non-working out of 7)

=4/10×3/9×2/8×1/7

where 4/10 ⇒ 4 working out of 10

3/9 ⇒ 3 working are remaining out of ‘9’ as ‘1’ is already taken

For ‘4’ Sum combinations

Total probability =4×[4/10×3/9×2/8×1/7]=600/5040

We need 100p ⇒100×600/5040=11.90

Out of which ‘4’ are chosen at random without replaced and created.

If at least three of them are working then system is deemed functional

i.e., there should be only ‘one’ non-working system in set of ‘4’.

It is possible with combination

W – W – W – N,

W – W – N – W,

W – N – W – W,

N – W – W – W.

For W – W – W – N, the probability = (choosing working out of 10) × (choosing working out of 9) × (choosing working out of 8) × (choosing non-working out of 7)

=4/10×3/9×2/8×1/7

where 4/10 ⇒ 4 working out of 10

3/9 ⇒ 3 working are remaining out of ‘9’ as ‘1’ is already taken

For ‘4’ Sum combinations

Total probability =4×[4/10×3/9×2/8×1/7]=600/5040

We need 100p ⇒100×600/5040=11.90

Question 12 |

Each of the nine words in the sentence "The quick brown fox jumps over the lazy dog" is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is _____________. (The answer should be rounded to one decimal place.)

3.9 | |

4.0 | |

4.1 | |

4.2 |

Question 12 Explanation:

"The quick brown fox jumps over the lazy dog"

There are ‘9’ words in this sentence.

No. of characters in each word

The (3)

quick (5)

brown (5)

fox (3)

jumps (5)

over (4)

the (3)

lazy (4)

dog (3)

Each word has equal probability.

So expected length = 3×1/9+5×1/9+5×1/9+3×1/9+5×1/9+ 4×1/9+3×1/9+4×1/9+3×1/9

=35/9

=3.9

There are ‘9’ words in this sentence.

No. of characters in each word

The (3)

quick (5)

brown (5)

fox (3)

jumps (5)

over (4)

the (3)

lazy (4)

dog (3)

Each word has equal probability.

So expected length = 3×1/9+5×1/9+5×1/9+3×1/9+5×1/9+ 4×1/9+3×1/9+4×1/9+3×1/9

=35/9

=3.9

Question 13 |

The maximum number of edges in a bipartite graph on 12 vertices is ______.

36 | |

37 | |

38 | |

39 |

Question 13 Explanation:

Max. no. of edges possible in bipartite graph, only if vertices are equal in each set i.e., 12/2 = 6 in each set.

Total no. of edges = 6×6 = 36

Total no. of edges = 6×6 = 36

Question 15 |

A non-zero polynomial f(x) of degree 3 has roots at x = 1, x = 2 and x = 3. Which one of the following must be TRUE?

f(0)f(4) < 0 | |

f(0)f(4) > 0 | |

f(0) + f(4) > 0 | |

f(0) + f(4) < 0 |

Question 15 Explanation:

Roots of polynomial of degree ‘3’ are 1, 2, 3

Polynomial will be

f(x) = (x-1)(x-2)(x-3)

f(0) = -1 × -2 × -3 = -6

f(4) = 3 × 2 × 1 = 6

f(0)∙f(4) = - 36

f(0) + f(4) = 6 - 6 = 0

Option (A) is correct.

Polynomial will be

f(x) = (x-1)(x-2)(x-3)

f(0) = -1 × -2 × -3 = -6

f(4) = 3 × 2 × 1 = 6

f(0)∙f(4) = - 36

f(0) + f(4) = 6 - 6 = 0

Option (A) is correct.

Question 16 |

The dual of a Boolean function F(x

_{1}, x_{2}, ..., x_{n}, +, ⋅, '), written as F^{D}, is the same expression as that of F with + and ⋅ swapped. F is said to be self-dual if F = F^{D}. The number of self-dual functions with n Boolean variables is2 ^{n} | |

2 ^{(n-1)} | |

2 ^{(2n )} | |

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

Question 16 Explanation:

Number of possible minterms = 2

Number of mutually exclusive pairs of minterms = 2

There are 2 choices for each pair i.e., we can choose one of the two minterms from each pair of minterms for the function.

Therefore number of functions = 2 x 2 x …. 2

= 2

^{n}.Number of mutually exclusive pairs of minterms = 2

^{n-1}.There are 2 choices for each pair i.e., we can choose one of the two minterms from each pair of minterms for the function.

Therefore number of functions = 2 x 2 x …. 2

^{n-1}times.= 2

^{(2(n-1) ) }Question 17 |

Let k = 2

^{n}. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2^{n}bit decoder. This circuit is equivalent to ak-bit binary up counter. | |

k-bit binary down counter. | |

k-bit ring counter. | |

k-bit Johnson counter. |

Question 17 Explanation:

A ring counter is a circular shift register with only one flip-flop being set at any particular time and all others are cleared.

A n x 2

A n-bit binary Counter produces outputs from 0 to 2

The n x 2

This circuit is equivalent to a 2

A n x 2

^{n}decoder is a combinational circuit with only one output line has one and all others (2^{n}-1) have zeros.A n-bit binary Counter produces outputs from 0 to 2

^{n}i.e 000...00 to 111...11 and repeats.The n x 2

^{n}Decoder gets the input (000..00 to 111...11 ) from the binary counter and only one output line has one and rest have zeros.This circuit is equivalent to a 2

^{n}- bit ring counter.Question 18 |

Consider the equation (123)

_{5}= (x8)_{y}with x and y as unknown. The number of possible solutions is __________.3 | |

5 | |

6 | |

7 |

Question 18 Explanation:

First we have to fullfill all the conditios,

(123)

In R.H.S. since y is base so y should be greater than x and 8, i.e.,

y > x

y > 8

Now, to solve let's change all the above bases number into base 10 number,

5

38 = xy + 8

xy = 30

⇒ yx = 30

So the possible combinations are

(1,30), (2,15), (3,10), (5,6)

But we will reject (5,6) because it violates the condition (y > 8).

So, total solutions possible is 3.

(123)

_{5}= (x8)_{y}In R.H.S. since y is base so y should be greater than x and 8, i.e.,

y > x

y > 8

Now, to solve let's change all the above bases number into base 10 number,

5

^{2}× 1 +2 × 5 + 3 = y × x + 838 = xy + 8

xy = 30

⇒ yx = 30

So the possible combinations are

(1,30), (2,15), (3,10), (5,6)

But we will reject (5,6) because it violates the condition (y > 8).

So, total solutions possible is 3.

Question 19 |

A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bits for the TAG field is __________.

20 | |

21 | |

22 | |

23 |

Question 19 Explanation:

Physical address size = 32 bits

Cache size = 16K bytes = 2

block size = 8 words = 8⨯4 Byte = 32 Bytes = 2

(where each word = 4 Bytes)

No. of blocks =2

block offset =9bits

Because it is 4-way set associative cache, no. of sets =2

Set of set = 7 bits

TAG = 32 – (7 + 5) = 20 bits

Cache size = 16K bytes = 2

^{14}Bytesblock size = 8 words = 8⨯4 Byte = 32 Bytes = 2

^{5}Bytes(where each word = 4 Bytes)

No. of blocks =2

^{14}/2^{5}=2^{9}block offset =9bits

Because it is 4-way set associative cache, no. of sets =2

^{9}/4=2^{7}Set of set = 7 bits

TAG = 32 – (7 + 5) = 20 bits

Question 20 |

9 | |

10 | |

11 | |

12 |

Question 20 Explanation:

Shift right of 1, which means the number gets half.

Shift left of 1, which means the number gets doubled.

In program, shift right of 1 is given, means every time we enter the loop the number will get halved, and the value of count will get incremented by 1. And when the value of num will become zero then the while loop will get terminated. So,

num = 435/2 = 217/2 = 108/2 = 54/2 = 27/2= 13/2 = 6/2 = 3/2 = 1/2 = 0

Count = 9

So, the value count that will get returned is 9.

Shift left of 1, which means the number gets doubled.

In program, shift right of 1 is given, means every time we enter the loop the number will get halved, and the value of count will get incremented by 1. And when the value of num will become zero then the while loop will get terminated. So,

num = 435/2 = 217/2 = 108/2 = 54/2 = 27/2= 13/2 = 6/2 = 3/2 = 1/2 = 0

Count = 9

So, the value count that will get returned is 9.

Question 21 |

Suppose n and p are unsigned int variables in a C program. We wish to set p to

^{n}C_{3}. If n is large, which one of the following statements is most likely to set p correctly?p = n * (n-1) * (n-2) / 6; | |

p = n * (n-1) / 2 * (n-2) / 3; | |

p = n * (n-1) / 3 * (n-2) / 2; | |

p = n * (n-1) * (n-2) / 6.0; |

Question 21 Explanation:

n & p are unsigned int variable.

From the options n*(n-1)*(n-2) will go out of range. So eliminate A & D.

n*(n-1) is always an even number. So subexpression n(n-1)/2 also an even number.

n*(n-1)/ 2*(n-2), gives a number which is a multiple of 3. So dividing with 3 will not have any loss. Hence B is option.

From the options n*(n-1)*(n-2) will go out of range. So eliminate A & D.

n*(n-1) is always an even number. So subexpression n(n-1)/2 also an even number.

n*(n-1)/ 2*(n-2), gives a number which is a multiple of 3. So dividing with 3 will not have any loss. Hence B is option.

Question 22 |

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

10, 8, 7, 3, 2, 1, 5 | |

10, 8, 7, 2, 3, 1, 5 | |

10, 8, 7, 1, 2, 3, 5 | |

10, 8, 7, 5, 3, 2, 1 |

Question 22 Explanation:

Max-Heap has 5 elements:

The level order traversal in this max heap final is:

10, 8, 7, 3, 2, 1, 5.

The level order traversal in this max heap final is:

10, 8, 7, 3, 2, 1, 5.

Question 23 |

Θ(n) | |

Θ(nlog n) | |

Θ(n ^{2}) | |

Θ(logn) |

Question 23 Explanation:

T(n)=2T(n/2)+logn

Apply Master’s theorem,

a=2,b=2,k=0,p=1

According to Master’s theorem, we can apply Case-I

(I) If a>b

Apply Master’s theorem,

a=2,b=2,k=0,p=1

According to Master’s theorem, we can apply Case-I

(I) If a>b

^{k}, then T(n)=θ(n^{(logba )}) =θ(n^{(log22 )})= θ (n)Question 24 |

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

the shortest path between every pair of vertices. | |

the shortest path from W to every vertex in the graph. | |

the shortest paths from W to only those nodes that are leaves of T. | |

the longest path in the graph. |

Question 24 Explanation:

One of the application of BFS algorithm is to find the shortest path between nodes u and v.

But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.

But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.

Question 25 |

Only (I) | |

Only (II) | |

Both (I) and (II) | |

Neither (I) nor (II) |

Question 25 Explanation:

The regular expression equivalent to L

Since L

So, L

Hence, statement (i) is True but statement (ii) is False.

_{1}and L_{2}are a* and b* respectively.Since L

_{1}and L_{2}both are regular languages and regular languages are closed under concatenation. So their concatenation (i.e., L_{1}⋅ L_{2}) must also be a regular language.So, L

_{1}⋅L_{2}= { a^{n}b^{n}| n ≥ 0}Hence, statement (i) is True but statement (ii) is False.

Question 26 |

Let A≤

_{m}B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?If A≤ _{m} B and B is recursive then A is recursive. | |

If A≤ _{m} Band A is undecidable then B is undecidable. | |

If A≤ _{m} Band B is recursively enumerable then A is recursively enumerable. | |

If A≤ _{m} B and B is not recursively enumerable then A is not recursively enumerable. |

Question 26 Explanation:

The rules are: If A ≤

Rule 1: If B is recursive then A is recursive.

Rule 2: If B is recursively enumerable then A is recursively enumerable.

Rule 3: If A is not recursively enumerable then B is not recursively enumerable.

Rule 4: If A is undecidable then B is undecidable.

Other than these rules, all conclusion are false.

_{p}BRule 1: If B is recursive then A is recursive.

Rule 2: If B is recursively enumerable then A is recursively enumerable.

Rule 3: If A is not recursively enumerable then B is not recursively enumerable.

Rule 4: If A is undecidable then B is undecidable.

Other than these rules, all conclusion are false.

Question 27 |

+ is left associative, while ∗ is right associative | |

+ is right associative, while ∗ is left associative | |

Both + and ∗ are right associative | |

Both + and ∗ are left associative |

Question 27 Explanation:

In production: T ⟶ T * U, since T is left recursive, hence * is left associative.

P ⟶ Q + P, here P is right recursive, so + is right associative.

P ⟶ Q + P, here P is right recursive, so + is right associative.

Question 28 |

Which one of the following is NOT performed during compilation?

Dynamic memory allocation | |

Type checking | |

Symbol table management | |

Inline expansion |

Question 28 Explanation:

Dynamic memory allocation is not performed during compilation, it occurs at run time only. At the time of compilation, compiler only compiles the instructions for dynamic memory allocation, like calloc, malloc….

Question 29 |

Which one of the following is TRUE?

The requirements document also describes how the requirements that are listed in the document are implemented efficiently. | |

Consistency and completeness of functional requirements are always achieved in practice. | |

Prototyping is a method of requirements validation. | |

Requirements review is carried out to find the errors in system design. |

Question 29 Explanation:

Note: Out of syllabus.

Question 30 |

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 × 10

^{6}bytes disk on which the file system is stored and data block size is 10^{3}bytes, the maximum size of a file that can be stored on this disk in units of 10^{6}bytes is ____________.99.60 | |

99.61 | |

99.62 | |

99.63 |

Question 30 Explanation:

Number of entry in FAT

= Total disk size/ disk block size

= 100 × 10

= 100 × 10

∴ Total overhead = 100 × 10

= 400 × 10

= 0.4 × 10

So, Maximum size of file that can be stored in disk is,

Total disk size - Total overhead

= 100 × 10

= 99.6 × 10

= Total disk size/ disk block size

= 100 × 10

^{6}/ 10^{3}= 100 × 10

^{3}∴ Total overhead = 100 × 10

^{3}× 4B= 400 × 10

^{3}B= 0.4 × 10

^{6}BSo, Maximum size of file that can be stored in disk is,

Total disk size - Total overhead

= 100 × 10

^{6}- 0.4 × 10^{6}= 99.6 × 10

^{6}BQuestion 31 |

The maximum number of superkeys for the relation schema R(E, F, G, H) with E as the key is _____.

8 | |

9 | |

10 | |

11 |

Question 31 Explanation:

Maximum no. of possible super keys for a relation with n attributes with one candidate key (only one attribute) = 2

Here, n = 4.

So, the possible super keys = 2

The super keys are: E, EH, EG, EF, EGH, EFH, EFG, EFGH.

^{n-1}Here, n = 4.

So, the possible super keys = 2

^{4-1}= 8The super keys are: E, EH, EG, EF, EGH, EFH, EFG, EFGH.

Question 32 |

19 | |

20 | |

21 | |

22 |

Question 32 Explanation:

There is already one entry with StudentName as “Shankar” and Age as 19. So, X value should not be 19.

Question 33 |

Which one of the following is TRUE about the interior gateway routing protocols – Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)?

RIP uses distance vector routing and OSPF uses link state routing | |

OSPF uses distance vector routing and RIP uses link state routing | |

Both RIP and OSPF use link state routing | |

Both RIP and OSPF use distance vector routing |

Question 33 Explanation:

RIP Uses Distance Vector Routing and OSPF uses Link State Routing.

Question 34 |

Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?

connect | |

bind | |

listen | |

accept |

Question 34 Explanation:

(a) The connect function is used by a TCP client to establish a connection with a TCP server.

(b) The bind function assigns a local protocol address to a socket. With the Internet protocols, the protocol address is the combination of either a 32-bit IPv4 address or a 128-bit IPv6 address, along with a 16-bit TCP or UDP port number.

(c) The listen function converts an unconnected socket into a passive socket, indicating that the kernel should accept incoming connection requests directed to this socket.

(d) The accept function is called by a TCP server to return the next completed connection from the front of the completed connection queue. If the completed connection queue is empty, the process is put to sleep (assuming the default of a blocking socket).

(b) The bind function assigns a local protocol address to a socket. With the Internet protocols, the protocol address is the combination of either a 32-bit IPv4 address or a 128-bit IPv6 address, along with a 16-bit TCP or UDP port number.

(c) The listen function converts an unconnected socket into a passive socket, indicating that the kernel should accept incoming connection requests directed to this socket.

(d) The accept function is called by a TCP server to return the next completed connection from the front of the completed connection queue. If the completed connection queue is empty, the process is put to sleep (assuming the default of a blocking socket).

Question 35 |

26 | |

27 | |

28 | |

29 |

Question 35 Explanation:

TTL field reduced at each router. There are 6 routers in the above diagram.

Initially TTL value was 32, so at the Receiver it will become 32 – 6 = 26.

Initially TTL value was 32, so at the Receiver it will become 32 – 6 = 26.

Question 36 |

T1 < T2 < T3 | |

T1 > T2 > T3 | |

T2 = T3, T3 < T1 | |

T1 = T3, T3 > T2 |

Question 36 Explanation:

Given Bandwidth = 10

L = 10

Case: 1

L = 1000 bytes

Header size = 100 bytes

Total Frame size = 1000 + 100 = 1100 bytes

∴ T

So, T

Case: 2

L = 100 bytes

Header size = 100 bytes

Total Frame size = 100 + 100 = 200 bytes

∴ T

For 10 packets ⇒ T

So, T

Case: 2

L = 50 bytes

Header size = 100 bytes

Total Frame size = 50 + 100 = 150 bytes

∴ T

For 20 packets ⇒ T

So, T

∴ T

T

^{6}bytes/secL = 10

^{3}byteCase: 1

L = 1000 bytes

Header size = 100 bytes

Total Frame size = 1000 + 100 = 1100 bytes

∴ T

_{x}= 1100 × 8/ 10^{6}×8 = 1100μsSo, T

_{1}=3300μsCase: 2

L = 100 bytes

Header size = 100 bytes

Total Frame size = 100 + 100 = 200 bytes

∴ T

_{x}= 200×8/ 10^{6}×8 = 200μs for 1 packetFor 10 packets ⇒ T

_{x}= 2000μsSo, T

_{2}= 2000+200+200 = 2400μsCase: 2

L = 50 bytes

Header size = 100 bytes

Total Frame size = 50 + 100 = 150 bytes

∴ T

_{x}= 150×8/ 10^{6}×8 = 150μs for 1 packetFor 20 packets ⇒ T

_{x}= 3000μsSo, T

_{3}= 3000+150+150 = 3300μs∴ T

_{1}= T_{3}T

_{3}> T_{2}Question 37 |

Only I1 and I2 | |

Only I1 | |

Only I2 and I3 | |

Only I3 and I4 |

Question 37 Explanation:

An Intruder can’t learn [I1] through sniffing at R2 because URLs and Download are functioned at Application layer of OSI Model.

An Intruder can learn [I2] through sniffing at R2 because Port Numbers are encapsulated in the payload field of IP Datagram.

An Intruder can learn [I3] through sniffing at R2 because IP Addresses and Routers are functioned at network layer of OSI Model.

An Intruder can’t learn [I4] through sniffing at R2 because it is related to Data Link Layer of OSI Model.

An Intruder can learn [I2] through sniffing at R2 because Port Numbers are encapsulated in the payload field of IP Datagram.

An Intruder can learn [I3] through sniffing at R2 because IP Addresses and Routers are functioned at network layer of OSI Model.

An Intruder can’t learn [I4] through sniffing at R2 because it is related to Data Link Layer of OSI Model.

Question 38 |

A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from a HTTP server S. The static HTML page has exactly one static embedded image which is also at S. Assuming no caching, which one of the following is correct about the HTML webpage loading (including the embedded image)?

Q needs to send at least 2 HTTP requests to S, each necessarily in a separate TCP connection to server S | |

Q needs to send at least 2 HTTP requests to S, but a single TCP connection to server S is sufficient | |

A single HTTP request from Q to S is sufficient, and a single TCP connection between Q and S is necessary for this | |

A single HTTP request from Q to S is sufficient, and this is possible without any TCP connection between Q and S |

Question 38 Explanation:

By default, HTTP is a persistent connection.

Whenever a browser opens a webpage, a separate HTML request must be sent for each image or component in HTML like css file or javascript. But all can be done in the same TCP connection.

Whenever a browser opens a webpage, a separate HTML request must be sent for each image or component in HTML like css file or javascript. But all can be done in the same TCP connection.

Question 39 |

S is conflict-serializable but not recoverable | |

S is not conflict-serializable but is recoverable | |

S is both conflict-serializable and recoverable | |

S is neither conflict-serializable nor is it recoverable |

Question 39 Explanation:

In the precedence graph, there are no cycles. So, it is conflict serializable and recoverable also.

Question 40 |

Consider a join (relation algebra) between relations r(R) and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R)) < size(s(S)), the join will have fewer number of disk block accesses if

relation r(R) is in the outer loop. | |

relation s(S) is in the outer loop. | |

join selection factor between r(R) and s(S) is more than 0.5. | |

join selection factor between r(R) and s(S) is less than 0.5. |

Question 40 Explanation:

The join between r(R) and s(S) which is using nested loop will be as follows,

For each tuple r in R do

For each tuple s in S do

If r and s satisfy the join condition then

output the tuple

The above algorithm involves (n

block transfer and (n

where,

b

b

h

To have less block accesses in nr should be less and in question it is given that size(r(R)) < size(s(S)).

To have fewer no. of disk block accesses the relation r(R) should be in outer loop.

For each tuple r in R do

For each tuple s in S do

If r and s satisfy the join condition then

output the tuple

The above algorithm involves (n

_{r}*b

_{s}+b

_{r})

block transfer and (n

_{r}+b

_{r}) seeks.

where,

b

_{r}→ no. of blocks in R

b

_{s}→ no. of blocks in S

h

_{r}→ no. of tuples in R

To have less block accesses in nr should be less and in question it is given that size(r(R)) < size(s(S)).

To have fewer no. of disk block accesses the relation r(R) should be in outer loop.

Question 41 |

The producer will be able to add an item to the buffer, but the consumer can never consume it. | |

The consumer will remove no more than one item from the buffer. | |

Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty. | |

The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation. |

Question 41 Explanation:

Answer is (C), because when consumer first access the semaphore 'S' it will down (S) and make 'S'=0, but for semaphore(n), it has to wait for producer to make it 1 but as for producer it can't access the critical section because the value of S=0, so semwait(S) will not work. So there will be deadlock.

Question 42 |

1000 | |

1001 | |

1002 | |

1003 |

Question 42 Explanation:

Gantt chart is shown below:

So 'C' completes its I/O at 1000 time units.

So 'C' completes its I/O at 1000 time units.

Question 43 |

A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

Least-recently-used | |

First-in-first-out | |

Last-in-first-out | |

Most-recently-used |

Question 43 Explanation:

The current status of 20 frames shows page numbers from 101 to 120. Implementation of optimal page replacement policy for above given page reference string would be as follows:

So, there would be 300 page faults in total (each access 100 page faults). Also it is visible that every time a replacement is done for the page which is most recently referred as it will be least recently referred in future. So, for the given page reference string optimal page replacement policy is working same as most recently used policy and thus number of page faults will be same in both of them.

So, there would be 300 page faults in total (each access 100 page faults). Also it is visible that every time a replacement is done for the page which is most recently referred as it will be least recently referred in future. So, for the given page reference string optimal page replacement policy is working same as most recently used policy and thus number of page faults will be same in both of them.

Question 44 |

X is declared as “int X[32][32][8]”. | |

X is declared as “int X[4][1024][32]”. | |

X is declared as “char X[4][32][8]”. | |

X is declared as “char X[32][16][2]”. |

Question 44 Explanation:

Consider a 3-D array: arr[i][j][k]

Arr[0][1][2], this 3-D array contains

1 two dimensional array as i value is zero ( if i =1 then it has 2, two D array ), & the two dimension array has 2 row and 3 column.

So, In a 3-D array, i represent number of 2D arrays, j represent number of rows and k represent number of columns.

Number of 2 D array (M)=1

Number of rows (R)=2

Number of columns (C)=3

As arrays are stored in row major order, so this 2 dimension array will be stored as:

Assume base address of Arr is 1000. The address of required position is calculated as:

Arr[i][j][k]= Arr+ [i*(R*C)+(j*C)+k]*4 // multiplication to 4 is due to int takes 4 Bytes.

Arr[0][1][1]= 1000+[0*(2*3)+(1*3)+1]*4

=1000+[ 0+3+1 ]*4

=1000+4*4

=1016

As you can see that in the given example of row order storing of array also has address of Arr[0][1][1] is 1016.

Now coming to the question:

X [ i ][ j ][ k ] is calculated by 3 address code X[t

X [ i ][ j ][ k ] = X [ t

=X [ t

=X [ t

=X [ t

=X [ i*1024 + j*32 + k*4]

=X [ i*256 + j*8 +k] *4 // taking 4 (common) outside

= X [ i*(32*8)+ (j*8) +k] *4

By comparing the above line with ....... Arr[i][j][k]= Arr+ [i*(R*C)+(j*C)+k]*4

We get R=32, C=8

It means the the declared array has 32 rows and 8 columns and since multiplication by 4 (common outside) so it was declared as INT.

But how many number of 2D arrays in this 3D array, we don't know.

Since option A is the only option with configuration: INT arr[ ] [ 32 ] [ 8]. So it is right option.

Arr[0][1][2], this 3-D array contains

1 two dimensional array as i value is zero ( if i =1 then it has 2, two D array ), & the two dimension array has 2 row and 3 column.

So, In a 3-D array, i represent number of 2D arrays, j represent number of rows and k represent number of columns.

Number of 2 D array (M)=1

Number of rows (R)=2

Number of columns (C)=3

As arrays are stored in row major order, so this 2 dimension array will be stored as:

Assume base address of Arr is 1000. The address of required position is calculated as:

Arr[i][j][k]= Arr+ [i*(R*C)+(j*C)+k]*4 // multiplication to 4 is due to int takes 4 Bytes.

Arr[0][1][1]= 1000+[0*(2*3)+(1*3)+1]*4

=1000+[ 0+3+1 ]*4

=1000+4*4

=1016

As you can see that in the given example of row order storing of array also has address of Arr[0][1][1] is 1016.

Now coming to the question:

X [ i ][ j ][ k ] is calculated by 3 address code X[t

_{4}]X [ i ][ j ][ k ] = X [ t

_{4}] // by substituting in reverse=X [ t

_{3}+ t_{2}]=X [ t

_{1}+ t_{0}+ k*4]=X [ t

_{0}+ t_{1}+ k*4] // t_{0}and t_{1}swapped as swapping doesn't have any impact=X [ i*1024 + j*32 + k*4]

=X [ i*256 + j*8 +k] *4 // taking 4 (common) outside

= X [ i*(32*8)+ (j*8) +k] *4

By comparing the above line with ....... Arr[i][j][k]= Arr+ [i*(R*C)+(j*C)+k]*4

We get R=32, C=8

It means the the declared array has 32 rows and 8 columns and since multiplication by 4 (common outside) so it was declared as INT.

But how many number of 2D arrays in this 3D array, we don't know.

Since option A is the only option with configuration: INT arr[ ] [ 32 ] [ 8]. So it is right option.

Question 45 |

Let <M> be the encoding of a Turing machine as a string over Σ = {0, 1} Let L = {<M> |M is a Turing machine that accepts a string of length 2014}. Then, L is

decidable and recursively enumerable | |

undecidable but recursively enumerable | |

undecidable and not recursively enumerable | |

decidable but not recursively enumerable |

Question 45 Explanation:

If L is recursive language then there must exist a Turing Machine which always HALT for every case (either acceptance or rejectance of string). Let the Turing Machine for L is M1.

Now, since total number of strings of length 2014 is finite, so M1 will run the encoding of M for the string of length 2014 and if the M accept the string then M1 will halt in ACCEPT state. But if M goes for infinte loop for every string of length 2014, then M1 also will go into infinite loop. Hence language L is recursively enumerable but not recursive, as in case of rejectance halting is not guaranteed.

Now, since total number of strings of length 2014 is finite, so M1 will run the encoding of M for the string of length 2014 and if the M accept the string then M1 will halt in ACCEPT state. But if M goes for infinte loop for every string of length 2014, then M1 also will go into infinite loop. Hence language L is recursively enumerable but not recursive, as in case of rejectance halting is not guaranteed.

Question 46 |

Let L

_{1}= {w ∈ {0,1}* | w has at least as many occurrences of (110)’s as (011)’s}. Let L_{2}= {w ∈ {0,1}*|w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?L _{1} is regular but not L_{2} | |

L _{2} is regular but not L_{1} | |

Both L _{1} and L_{2} are regular | |

Neither nor L _{1} are L_{2} regular |

Question 46 Explanation:

In L

{Number of occurrences of (110)} ≥ {Number of occurrences of (011)}

Lets analyse the language, consider a string in which occurrence of (110) is more than one.

The following possibilities are: {1100110, 1101110, 110110, ….}

Please observe whenever strings start with “11” then in every situation whatever comes after “11” the string will never violate the condition. So strings of the form 11(0+1)* will always satisfy the condition.

Consider a string in which occurrence of (011) is more than one.

The following possibilities are: {011011, 0111011, 0110011, ….}

In the following possibilities please observe that number of occurrence “011” is two but number of occurrence of (110) is one, which violate the conditions.

If we add “0” in every string mentioned above, i.e. {0110110, 01110110, 01100110, ….} Now, observe that number of occurrence “011” and the number of occurrence of (110) both are equal, which satisfies the conditions.

With these analysis, we can make the DFA , which is mentioned below.

But language L

_{1}any string “w” must satisfy the condition:{Number of occurrences of (110)} ≥ {Number of occurrences of (011)}

Lets analyse the language, consider a string in which occurrence of (110) is more than one.

The following possibilities are: {1100110, 1101110, 110110, ….}

Please observe whenever strings start with “11” then in every situation whatever comes after “11” the string will never violate the condition. So strings of the form 11(0+1)* will always satisfy the condition.

Consider a string in which occurrence of (011) is more than one.

The following possibilities are: {011011, 0111011, 0110011, ….}

In the following possibilities please observe that number of occurrence “011” is two but number of occurrence of (110) is one, which violate the conditions.

If we add “0” in every string mentioned above, i.e. {0110110, 01110110, 01100110, ….} Now, observe that number of occurrence “011” and the number of occurrence of (110) both are equal, which satisfies the conditions.

With these analysis, we can make the DFA , which is mentioned below.

But language L

_{2}requires infinite comparison to count the occurrences of (000’s) and (111’s), hence it is not regular.Question 47 |

Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x+10y = _________.

34 | |

35 | |

36 | |

37 |

Question 47 Explanation:

Given is

A = “qpqrr” B = “pqprqrp”

The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:

(1) qpqr

(2) pqrr

(3) qprr

So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34

A = “qpqrr” B = “pqprqrp”

The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:

(1) qpqr

(2) pqrr

(3) qprr

So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34

Question 48 |

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ______.

358 | |

359 | |

360 | |

361 |

Question 48 Explanation:

The implementation of optimal algorithm for merging sequences is as follows.

In the above implementation, total number of comparisons is

(44-1) + (94-1) + (65-1) + (159-1) = 358

Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.

In the above implementation, total number of comparisons is

(44-1) + (94-1) + (65-1) + (159-1) = 358

Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.

Question 50 |

1.73 | |

1.74 | |

1.75 | |

1.76 |

Question 50 Explanation:

f(q) will return q, if

x

So, x

x

x

x < 1.732

Hence, x = 1.73.

x

^{2}- 3 < 0.01 will become True.So, x

^{2}- 3 < 0.01x

^{2}- 3 < 0.01x

^{2}< 3.01x < 1.732

Hence, x = 1.73.

Question 51 |

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

A queue cannot be implemented using this stack. | |

A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions. | |

A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction. | |

A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each. |

Question 51 Explanation:

A Queue can be implemented where Enqueue takes 3 operations & dequeuer takes 1 operation.

Suppose:

Dequeue:

If we want to delete an element, that first we need to delete 1.

Enqueue:

Suppose:

Dequeue:

If we want to delete an element, that first we need to delete 1.

Enqueue:

Question 52 |

The function returns 0 for all values of j. | |

The function prints the string something for all values of j. | |

The function returns 0 when j = 50. | |

The function will exhaust the runtime stack or run into an infinite loop when j = 50. |

Question 52 Explanation:

Let's say that value of j given inside the function is 50.

int f(int j)

{

static int i = 50;

int k;

if (i == j) // This will be True.

{

printf ("Something");

k = f(i); // Again called f(i) with value of i as 50. So, the function will run into infinite loop.

return 0;

}

else return 0;

}

int f(int j)

{

static int i = 50;

int k;

if (i == j) // This will be True.

{

printf ("Something");

k = f(i); // Again called f(i) with value of i as 50. So, the function will run into infinite loop.

return 0;

}

else return 0;

}

Question 53 |

In designing a computer’s cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?

A smaller block size implies better spatial locality | |

A smaller block size implies a smaller cache tag and hence lower cache tag overhead | |

A smaller block size implies a larger cache tag and hence lower cache hit time | |

A smaller block size incurs a lower cache miss penalty |

Question 53 Explanation:

When a cache block size is smaller, it could accommodate more number of blocks, it improves the hit ratio for cache, so the miss penalty for cache will be lowered.

Question 54 |

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

Width of tag comparator | |

Width of set index decoder | |

Width of way selection multiplexor | |

Width of processor to main memory data bus |

Question 54 Explanation:

When associativity is doubled, then the set offset will be affected, accordingly, the number of bits used for TAG comparator be affected.

Width of set index decoder also will be affected when set offset is changed.

A k-way set associative cache needs k-to-1 way selection multiplexer. If the associativity is doubled the width of way selection multiplexer will also be doubled.

With of processor to main memory data bus is guaranteed to be NOT affected as this is not dependent on the cache associativity.

Width of set index decoder also will be affected when set offset is changed.

A k-way set associative cache needs k-to-1 way selection multiplexer. If the associativity is doubled the width of way selection multiplexer will also be doubled.

With of processor to main memory data bus is guaranteed to be NOT affected as this is not dependent on the cache associativity.

Question 55 |

The value of a float type variable is represented using the single-precision 32-bit floating point format of IEEE-754 standard that uses 1 bit for sign, 8 bits for biased exponent and 23 bits for mantissa. A float type variable X is assigned the decimal value of −14.25. The representation of X in hexadecimal notation is

C1640000H | |

416C0000H | |

41640000H | |

C16C0000H |

Question 55 Explanation:

Given number is a negative number. So sign bit =1

(14.25)

= 1.11001000 x 2

23 bit Mantissa = 11001000000000000000000

Biased Exponent = exponent + bias

= 3 + 127 = 130 = 1000 0010

(-14.25) in 32-bit IEEE-754 floating point representation is

1 10000010 11001000000000000000000

=1100 0001 0110 0100 0000 0000 000 0000

= (C 1 6 4 0 0 0 0)

(14.25)

_{10}= 1110.01000= 1.11001000 x 2

^{3}23 bit Mantissa = 11001000000000000000000

Biased Exponent = exponent + bias

= 3 + 127 = 130 = 1000 0010

(-14.25) in 32-bit IEEE-754 floating point representation is

1 10000010 11001000000000000000000

=1100 0001 0110 0100 0000 0000 000 0000

= (C 1 6 4 0 0 0 0)

_{16}Question 56 |

Only I | |

Only II | |

Both I and II | |

Neither I nor II |

Question 56 Explanation:

Note: Numerical methods are not in GATE CS syllabus.

Question 57 |

6 | |

7 | |

8 | |

9 |

Question 57 Explanation:

Characteristic equation for matrix ‘A’ is

AX = λX

x

x

(1) + (2) ⇒ 2(x

x

x

x

(4)+(5)+(6) = 3(x

Product = λ

AX = λX

x

_{1}+ x_{5}= λx_{1}---------- (1)x

_{1}+ x_{5}= λx_{5}---------- (2)(1) + (2) ⇒ 2(x

_{1}+ x_{5}) = λ(x_{1}+ x_{5}) ⇒ λ_{1}= 2x

_{2}+ x_{3}+ x_{4}= λ∙x_{2}-------- (4)x

_{2}+ x_{3}+ x_{4}= λ∙x_{3}-------- (5)x

_{2}+ x_{3}+ x_{4}= λ∙x_{4}-------- (6)(4)+(5)+(6) = 3(x

_{2}+ x_{3}+ x_{4}) = λ(x_{2}+ x_{3}+ x_{4}) ⇒ λ_{2}=3Product = λ

_{1}× λ_{2}= 2×3 = 6Question 58 |

The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .

0.259 to 0.261 | |

0.260 to 0.262 | |

0.261 to 0.263 | |

0.262 to 0.264 |

Question 58 Explanation:

Let A = divisible by 2, B = divisible by 3 and C = divisible by 5, then

n(A)=50, n(B)=33, n(C)=20

n(A∩B)=16, n(B∩C)=6, n(A∩C)=10

n(A∩B∩C)=3

P(A∪B∪C)=P(A)+P(B)+P(C)-P(A∩B)-P(B∩C) -P(A∩C)+P(A∩B∩C)=74/100

∴ Required probability is P(A∩B∩C)=1-P(A∪B∪C)=0.26

n(A)=50, n(B)=33, n(C)=20

n(A∩B)=16, n(B∩C)=6, n(A∩C)=10

n(A∩B∩C)=3

P(A∪B∪C)=P(A)+P(B)+P(C)-P(A∩B)-P(B∩C) -P(A∩C)+P(A∩B∩C)=74/100

∴ Required probability is P(A∩B∩C)=1-P(A∪B∪C)=0.26

Question 59 |

The number of distinct positive integral factors of 2014 is _________

0.26 | |

0.27 | |

8 | |

0.29 |

Question 59 Explanation:

First lets find prime factorization of 2014

= 2' × 19' × 53'

Now number of distinct integral factors of 2014 will be,

(1+1)×(1+1)×(1+1) = 2×2×2 = 8

= 2' × 19' × 53'

Now number of distinct integral factors of 2014 will be,

(1+1)×(1+1)×(1+1) = 2×2×2 = 8

Question 60 |

Both S1 and S2 are true | |

S1 is true and S2 is false | |

S2 is true and S1 is false | |

Neither S1 nor S2 is true |

Question 60 Explanation:

Given: S = {1, 2, 3, …, 2014}

U⊂S, V⊂S

Let U = {1, 2, 3}

V = {2, 3, 4}

Symmetric difference:

(U – V) ∪ (V – U) = {1} ∪ {4} = {1, 4}

The minimum element in the symmetric difference is 1 and 1∈U.

S1: Let S = Universal set = {1, 2, … 2014}

This universal set is larger than every other subset.

S2: Null set is smaller than every other set.

Let U = { }, V = {1}

Symmetric difference = ({ } – {1}) ∪ ({1} – { }) = { } ∪ {1} = {1}

So, U < V because { } ∈ U.

U⊂S, V⊂S

Let U = {1, 2, 3}

V = {2, 3, 4}

Symmetric difference:

(U – V) ∪ (V – U) = {1} ∪ {4} = {1, 4}

The minimum element in the symmetric difference is 1 and 1∈U.

S1: Let S = Universal set = {1, 2, … 2014}

This universal set is larger than every other subset.

S2: Null set is smaller than every other set.

Let U = { }, V = {1}

Symmetric difference = ({ } – {1}) ∪ ({1} – { }) = { } ∪ {1} = {1}

So, U < V because { } ∈ U.

Question 61 |

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

5 | |

6 | |

7 | |

8 |

Question 61 Explanation:

Complement of a graph means, we need to remove the existing edges from the graph and place the new edges which were not earlier among the actual graph.

In a cycle of n vertices, each vertex is connected to other two vertices. So each vertex degree is 2.

When we complement it, each vertex will be connected to remaining n-3 vertices ( one is self and two other vertices in actual graph).

As per given question,

n-3 =2

n=5

Cycle of 5 vertices is

Complement of the above graph1 is

Graph1 and Graph2 are complement each other.

So, the value of n is 5.

In a cycle of n vertices, each vertex is connected to other two vertices. So each vertex degree is 2.

When we complement it, each vertex will be connected to remaining n-3 vertices ( one is self and two other vertices in actual graph).

As per given question,

n-3 =2

n=5

Cycle of 5 vertices is

Complement of the above graph1 is

Graph1 and Graph2 are complement each other.

So, the value of n is 5.

Question 62 |

6 | |

7 | |

8 | |

9 |

Question 62 Explanation:

Minimum Spanning Tree:

From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.

So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.

Question 63 |

Which one of the following Boolean expressions is NOT a tautology?

((a ⟶ b) ∧ (b ⟶ c)) ⟶ (a ⟶ c) | |

(a ⟷ c) ⟶ (∽ b ⟶ (a ∧ c)) | |

(a ∧ b ∧ c) ⟶ (c ∨ a) | |

a ⟶ (b ⟶ a) |

Question 63 Explanation:

A:

((a → b) ∧ (b → c)) → (a → c)

If (a → b) is false with a = T, b = F,

then (F ∧ (b → c)) → (a → c)

F → (a → c)

which is True for any (a → c)

This is tautology.

B:

(a ⟷ c) ⟶ (∽b ⟶ (a ∧ c))

For (a ⟷ c) be True and

∽b → (a ∧ c) should be False

Let a = c = F

(F → F) → (∽b (F ∩ F))

T → (∽b → F)

This is False for b = F

So, this is not True.

C:

(a ∧ b ∧ c) ⟶ (c ∨ a)

(c ∨ a) is False only for a = c = F

if (c ∨ a) is False

(F ∧ b ∧ F) → F

F → F which is Tautology

True always.

D:

a ⟶ (b ⟶ a)

a ⟶ (~b ∨ a)

(~a ∨ a) ∨ ~b = T ∨ ~b = T which is tautology

((a → b) ∧ (b → c)) → (a → c)

If (a → b) is false with a = T, b = F,

then (F ∧ (b → c)) → (a → c)

F → (a → c)

which is True for any (a → c)

This is tautology.

B:

(a ⟷ c) ⟶ (∽b ⟶ (a ∧ c))

For (a ⟷ c) be True and

∽b → (a ∧ c) should be False

Let a = c = F

(F → F) → (∽b (F ∩ F))

T → (∽b → F)

This is False for b = F

So, this is not True.

C:

(a ∧ b ∧ c) ⟶ (c ∨ a)

(c ∨ a) is False only for a = c = F

if (c ∨ a) is False

(F ∧ b ∧ F) → F

F → F which is Tautology

True always.

D:

a ⟶ (b ⟶ a)

a ⟶ (~b ∨ a)

(~a ∨ a) ∨ ~b = T ∨ ~b = T which is tautology

Question 64 |

select R.* from R,S where R.a=S.a | |

select distinct R.* from R,S where R.a=S.a | |

select R.* from R,(select distinct a from S) as S1 where R.a=S1.a | |

select R.* from R,S where R.a=S.a and is unique R |

Question 64 Explanation:

Multiplicity of duplicate tuples will be distributed when there is a match between R.a and S.a; and for that match, S.a's value is repeated in each cases except the third case. So, the output of query given in the question matches with the output of (C).

Question 65 |

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in 1 millisecond is ____________

10000 | |

10001 | |

10002 | |

10003 |

Question 65 Explanation:

Each write request, the bus is occupied for 100 n.s

Storing of data requires 100 n.s.

In 100 n.s – 1 store

100/10

1 m.s=10

Storing of data requires 100 n.s.

In 100 n.s – 1 store

100/10

^{6}m.s=1 store1 m.s=10

^{6}/100stores=10000 stores
There are 65 questions to complete.