CS/IT Gate Yearwise 


CS and IT Gate 2016 Set-2 Questions with Answer

Ques 40 Gate 2016 Set-2

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


(Complexity) is the correct answer.

Ques 41 Gate 2016 Set-2

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 Gate 2016 Set-2

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 Gate 2016 Set-2

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 Gate 2016 Set-2

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


(Logic Gates) is the correct answer.

Ques 45 Gate 2016 Set-2

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


(a) is the correct answer.

Ques 46 Gate 2016 Set-2

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 Gate 2016 Set-2

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


(Graph Theory) is the correct answer.

Ques 48 Gate 2016 Set-2

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


(Pridicate Calculus) is the correct answer.

Ques 49 Gate 2016 Set-2

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.


(Set Theory) is the correct answer.

Ques 50 Gate 2016 Set-2

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 Gate 2016 Set-2

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 Gate 2016 Set-2

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

Question Options

Contributed by: