CS/IT Gate Yearwise 


CS and IT Gate 2020 Questions with Answer

Ques 40 Gate 2020

Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE ?

A

R has a nontrivial functional dependency X→A, where X is not a superkey and A is a prime attribute.

B

R has a nontrivial functional dependency X→A, where X is not a superkey and A is a non-prime attribute and X is not a proper subset of any key.

C

R has a nontrivial functional dependency X→A, where X is not a superkey and A is a non-prime attribute and X is a proper subset of some key.

D

A cell in R holds a set instead of an atomic value.


(a) is the correct answer.

Ques 41 Gate 2020

Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram ?

A

Diamonds with double/bold border

B

Rectangles with double/bold border

C

Ovals with double/bold border

D

Ovals that contain underlined identifiers


(a) is the correct answer.

Ques 42 Gate 2020

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?

A

Θ(n)

B

Θ(nlogn)

C

Θ(n2)

D

Θ(1)


(c) is the correct answer.

Ques 43 Gate 2020

What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially ?

A

Θ(n4)

B

Θ(n2)

C

Θ(n2log(n))

D

Θ(n3)


(c) is the correct answer.

Ques 44 Gate 2020

For parameters a and b, both of which are ω(1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is

A

Θ(logalogbn)

B

Θ(logabn)

C

Θ(logblogan)

D

Θ(log2log2n)


(a) is the correct answer.

Ques 45 Gate 2020

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ________ .


(12 ) is the correct answer.

Ques 46 Gate 2020

If there are m input lines n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m+n is ________ .


(1024) is the correct answer.

Ques 47 Gate 2020

Which one of the following predicate formulae is NOT logically valid ? Note that W is a predicate formula without any free occurrence of x.

A

∀x(p(x) ∨ W) ≡ ∀x(px) ∨ W

B

∃x(p(x) ∧ W) ≡ ∃xp(x) ∧ W

C

∀x(p(x) → W) ≡ ∀xp(x) → W

D

∃x(p(x) → W) ≡ ∀xp(x) → W


(c) is the correct answer.

Ques 48 Gate 2020

Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ________ .


(7) is the correct answer.

Ques 49 Gate 2020

Let R be the set of all binary relations on the set {1, 2, 3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ________ .


(0.125) is the correct answer.

Ques 50 Gate 2020

Let A and B be two n×n matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements.

I. rank(AB) = rank(A)*rank (B)
II. det(AB) = det(A)*det(B)
III. rank(A+B) ≤ rank(A) + rank(B)
IV. det(A+B) ≤ det(A) + det(B)

Which of the above statements are TRUE ?

A

I and II only

B

I and IV only

C

II and III only

D

III and IV only


(c) is the correct answer.

Ques 51 Gate 2020

Consider the functions

I. e-x
II. x2 - sin x
III. √x^3+1

Which of the above functions is/are increasing everywhere in [0, 1] ?

A

Ⅲ only

B

Ⅱ only

C

Ⅱ and Ⅲ only

D

Ⅰ and Ⅲ only


(a) is the correct answer.

Ques 52 Gate 2020

For n>2, let a∈{0, 1}n be a non-zero vector. Suppose that x is chosen uniformly at random from {0,1}n. Then, the probability that Σi=1i=n aixi is an odd number is _________


(0.50) is the correct answer.

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: