CS/IT Gate Yearwise 


CS and IT GATE 2016 Set-2 Questions with Answer

Ques 40 Design Algorithm Analysis

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ?

I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

A

I and II only

B

I and III only

C

II and IV only

D

I and IV only



Ques 41 Digital Logic Design

The width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is ____________ bits.


a is the correct answer.


Ques 42 Digital Logic Design

Let X be the number of distinct 16-bit integers in 2’s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then X −Y is _________


a is the correct answer.


Ques 43 Digital Logic Design

Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2’s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is _____________


a is the correct answer.


Ques 44 Digital Logic Design

Let, x1⊕x2⊕x3⊕x4= 0 where x1, x2, x3, x4 are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE ?

A

x1x2x3x4=0

B

x1x3+x4=0

C

x'1⊕x'3=x'2⊕x'4

D

x1+x2+x3+x4=0



Ques 45 Discrete Mathematics

The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________


a is the correct answer.


Ques 46 Discrete Mathematics

Consider the following expressions:

(i) false
(ii) Q
(iii) true
(iv) P ∨ Q
(v) ¬Q ∨ P

The number of expressions given above that are logically implied by P ∧ (P ⇒ Q) is ______________


a is the correct answer.


Ques 47 Discrete Mathematics

Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements:

I. Each compound in U S reacts with an odd number of compounds.
II. At least one compound in U S reacts with an odd number of compounds.
III. Each compound in U S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

A

Only I

B

Only II

C

Only III

D

None



Ques 48 Discrete Mathematics

Which one of the following well-formed formulae in predicate calculus is NOT valid?

A

(∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x¬p(x) ∨ ∀x q(x))

B

(∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))

C

∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))

D

∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))



Ques 49 Discrete Mathematics

A binary relation R on N x N is defined as follows:

(a, b) R (c, d) if a <= c or b <= d.

Consider the following propositions:

P: R is reflexive
Q: R is transitive

Which one of the following statements is TRUE?

A

Both P and Q are true.

B

P is true and Q is false.

C

P is false and Q is true.

D

Both P and Q are false.



Ques 50 Mathematics

Suppose that the eigenvalues of matrix A are 1, 2, 4. The determinant of (A−1)T is _________.


a is the correct answer.


Ques 51 Mathematics

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type 2 is 0.4. The probability that an LED bulb chosen uniformly at random lasts more than 100 hours is_________.


a is the correct answer.


Ques 52 Mathematics

Let f (x) be a polynomial and g(x) = f^^(x) be its derivative. If the degree of (f(x) + f(−x)) is 10, then the degree of (g(x) − g(−x)) is ___________ .


a is the correct answer.


Unique Visitor Count

Total Unique Visitors

Loading......