08-16-2017, 08:46 PM

Computer Science: Gate 2007 Paper

[attachment=283]

1. Consider the following two statements about the function f (x) = x :

P. f (x) is continuous for all real values of x

Q. f (x) is differentiable for all real values of x

Which of the following is TRUE?

(A) P is true and Q is false. (B) P is false and Q is true.

© Both P and Q are true. (D) Both P and Q are false.

2. Let S be a set of n elements. The number of ordered pairs in the largest and the

smallest equivalence relations on S are:

(A) n and n (B) 2 n and n © 2 n and 0 (D) n and 1

3. What is the maximum number of different Boolean functions involving n Boolean

variables?

(A) 2 n (B) 2n © 2 2

n

(D)

2

2n

4. Let G be the non-planar graph with the minimum possible number of edges. Then

G has

(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices

© 10 edges and 5 vertices (D) 10 edges and 6 vertices

5. Consider the DAG with V = {1,2,3,4,5,6}, shown below.

Which of the following is NOT a topological ordering?

(A) 1 2 3 4 5 6 (B) 1 3 2 4 5 6 © 1 3 2 4 6 5 (D) 3 2 4 1 6 5

6. Which of the following problems is undecidable?

(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs.

© Finiteness problem for FSAs. (D) Equivalence problem for FSAs.