GATE Exam Papers - (Computer Science) - Part 8

Que. 1 A relation R is defined on the set of integers as x Ry if f(x + y) is
even. Which of the following statements is true?
A R is not an equivalence relation
B R is an equivalence relation having 1 equivalence class
C R is an equivalence relation having 2 equivalence classes
D R is an equivalence relation having 3 equivalence classes

Que. 2 Let a, b, c, d be propositions. Assume that the equivalences a<-> (b
V-b) and b<->c hold. Then the truth value of the formula (a Ù b) -J. (a
Ù c) Ù d) is always
A True
B False
C Same as the truth value of b
D Same as the truth value of d

Que. 3 Consider the following relations:
R1 (a, b) if f(a + b) is even over the set of integers
R2 (a, b) if f(a + b) is odd over the set of integers
R3 (a, b) if f a.b > 0 over the set of non-zero rational numbers
R4 (a, b) iff |a - b | Which of the following statements is correct?
A R1 and R2 are equivalence relations, R3 and R4 are not
B R1 and R3 are equivalence relations, R2 and R4 are not
C R1 and R4 are equivalence relations, R2 and R3 are not
D R1, R2, R3 and R4 are all equivalence relations

Que. 4 Seven (distinct) car accidents occurred in a week. What is the probability
that they all occurred on the same day?
A (1/7)^7
B (1/7)^6
C (1/2)^7
D (7/2)^7

Que. 5 In the interval {0, (pi)} the equation x=cosx has
A no solution
B exactly one solution
C exactly two solution
D an infinite number of solution

Que. 6 In a room containing 28 people,there are 18 peoples who speaks english,15
people who speak hindi and 22 people who speak kannada.9 persons speak
both english and hindi,11 persons speak both hindi and kannada.Where as
13 persons speak both english and kannada.how many people speak all the
three languages?
A 9
B 8
C 7
D 6

Que. 7 Given the following relation instance X Y Z 1 4 2
1 5 3 1 6 3 3 2 2 Which of the following
functional dependencies are satisfied by the instance?
A XY->Z and Z ->Y
B YZ->X and Y->Z
C YZ->X and X->Z
D XZ->Y and Y->X

Que. 8 Let f(n) = (n^2)1 g n and g(n) = n (1 g n)^10 be two positive functions
of n. Which of the following statements is correct ?
A f(n) = O(g(n) and g(n)!= O(f(n))
B g(n) = O(f(n) and f(n) != O(g(n))
C f(n) != O(g(n)) and g(n) != O(f(n))
D f(n) = O(g(n)) and g(n) = O(f(n))

Que. 9 The proposition P^(~pvq) is
A A tautology
B logically equivalent to p^q
C logically equivalent to pvq
D A contradiction

Que. 10 Let A and B be real symmetric matrices of size n*n.Then which one of the
following is true?
A A(A^t)=1
B A=(A^-1)
C AB=BA
D (AB)^t=BA

Que. 11 The number of distinct simple graph with upto three nodes is
A 15
B 10
C 7
D 9

Que. 12 The Newton-Raphson method is used to find the root of the equation x^2-2=0.
if the iteration are started from -1,the iteration will
A converage to -1
B converage to [(sqrt)2]
C converage to -[(sqrt)2]
D not converage

Que. 13 What is the converse ofthe following assertion? I stay only
if you go
A I stay if you go
B if I stay then you go
C if you do not go then i donot stay
D if i do not stay then you go

Que. 14 In a room containing 28 people,there are 18 peoples who speak english,15
people who speak hindiand 22 people who speak kannada.9 persons speak
both english and hindi 11 persons speak both hindi and kannads whereas
13 persons speak both kannada and english.how many people speak all therr
languages?
A 9
B 8
C 7
D 6

Que. 15 Let L be the set of all binary strings whoes last two symbols are same.the
number of states in the minimum state determinimstc finite 0 state automaton
accepting L is
A 2
B 5
C 8
D 3

Que. 16 Which oneof the following operations is commutative but not associative?
A AND
B OR
C NAND
D EXOR

Que. 17 What is the maximum value of the function f(x)=2(x^2) -2x +6 in the interval
[0,2]?
A 6
B 10
C 12
D 5.5

Que. 18 The function
f(x,y)=(x^2)y-3xy+2y+x has
A no local extremun
B one local minimum but no local maximum
C one local maximum but no local minimum
D one local minimum and one local maximum

Que. 19 Let L be a set with a relation R which istransitive,anti
symmetric and reflexive and for any two elements a, b Î L let the
least upper bound lub (a, b) and the greatest lower bound glb
(a, b) exist. Which of the following is/are true?
A L is a poset
B L is a boolean algebra
C L is a lattice
D None of the above

Que. 20 The number of binary strings of n zeros and k ones that no two
ones are adjacent is
A n-1 C k
B n C k
C n C k+l
D None of the above


Que. 21 A polynomial p(x) satisfies the following: p (1) = p(3) = p(5) = 1
p(2) = p(4) = -1 The minimum degree of such a polynomial is
A 1
B 2
C 3
D 4

Que. 22 Suppose the adjacency relation of vertices in a graph is represented
in a table Adj(X, Y). Which of the following queries cannot be expressed
by a relational algebra expression of constant length?
A List all vertices adjacent to a given vertex
B List all vertices which have self loops
C List all vertices which belong to cycles of less than three vertices
D List all vertices reachable from a given vertex

Que. 23 Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression s A=a (r |X| s) is always equal to
A s A=a (r)
B r
C s A=a (r) |X| s
D none of the above

Que. 24 Let f : A->B be a function, and let E and F be subsets of A. Consider
the following statements about images. S1 :f (E(union)F)=f (E)(union)
f (F) S2 :f (E (intersection) F)=f(E)(intersection)f (F) Which of the
following is true about S1 and S2 ?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 and S2 is correct

Que. 25 The proposition p <-> q means
A p if and only if q
B which is true if both p and q are true
C it is false when p is true and q is false
D all of the above

Que. 26 If A={a,b} then A+ is
A {a,b} (union) {{a,b}}
B {{a,b} (union) {a,b}}
C {a,b} (union) {a,b}}
D none of these

Que. 27 What is the number of ways to point 12 offices so that 3 of them will
be green,2 of them pink,2 of them yellow and the remaining onces white
A 166324
B 166328
C 166320
D 166322

Que. 28 The number of binary relations on a set with n elements is
A n^2
B 2^n
C 2^(n^2)
D none of these

Que. 29 Let A,B,C,D be n*n matrices,each with non-zero determinant.If ABCD=1 then
B^(-1) is
A D(-1)C(-1)A(-1)
B CDA
C ADC
D Does not necessarily exist

Que. 30 Given the following input (4322,1334,1471,1989,6171,6173,4199) ans the
following hash function x mod 10,which of the following statments are
true? (i) 9679,1989,4199 hash to the same value
(ii) 1471,6171 hash to the same value (iii)all elements
hash to the same value (iv)Each element hashes to a different
value
A (i) only
B (ii) only
C (i) and (ii) only
D (iii) or (iv)

Que. 31 In a group of 30 persons,a total of 16 take tea while 9 take tea but not
coffee. how many persons in this group take coffee but not tea?
A 27
B 20
C 25
D 11

Que. 32 The less than relation,<,on reals is
A A partical ordering since it is asymmetric and reflexive
B A partical ordering since it is antiymmetric and reflexive
C not a partical ordering it is not asymmetric and not reflexive
D not a partical ordering it is not asymmetric and reflexive
(E)none of these

Que. 33 The number of element in the power set P(S) of the set
S={(fi),1,(2,3)} is
A 2
B 4
C 8
D none of the above

Que. 34 The rank of the following (n+1)*(n+1) natrix,where a is a real number is
|1 a a^2... a^n|
|1 a a^2... a^n|
|. . . . |
|. . . . |
|. . . . |
|1 a a^2... a^n|
A 1
B 2
C n
D depend on the value of a

Que. 35 The determinant of the matrix
|6 -8 1 1|
|0 2 4 6|
|0 0 4 8|
|0 0 0 -1|
is
A 11
B -48
C 0
D -24

Que. 36 What is the maximum value of the function f(x)=2(x^2)-2x+6 in the interval
[0,2]?
A 6
B 10
C 12
D 5.5

Que. 37 The solution to the recurrence equation T(2^k)=3T[2^(k-1)]+1, T(1)=1,
is
A 2^k
B [3^(k+1)-1]/2
C [3^(log2 k)]
D [2^(log2 k)]

Que. 38 For X=4.0 the value of I in the FORTRAN 77 statment I=-2**2+5.0*X/X*3+3/4
is
A 11
B -11
C 22
D -22

Que. 39 A polynomial p(x) is such that p(0)=5, p(1)=4,P(2)=9 and p(3)=20.The minimum
degree it can have is
A 1
B 2
C 3
D 4

Que. 40 Let f(x,y,z)=x'+y'x+xz be a switching function.Which one of the following
is valid
A y'x is a prime implicant of f
B xz is a minterm of f
C xz is an implicant of f
D y is a prime implicant of f