# GATE CSE 2007

 Question 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. C Both P and Q are true. D Both P and Q are false.
Engineering Mathematics   Calculus
Question 1 Explanation:
 Question 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 $n^{2} \; and \; n$ C $n^{2} \; and \; 0$ D n and 1
Discrete Mathematics   Set Theory
Question 2 Explanation:
 Question 3
What is the maximum number of different Boolean functions involving n Boolean variables?
 A $n^{2}$ B $2^{n}$ C $2^{2^{n}}$ D $2^{n^{2}}$
Digital Logic   Boolean Algebra
Question 3 Explanation:
 Question 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 C 10 edges and 5 vertices D 10 edges and 6 vertices
Discrete Mathematics   Planar Graph
Question 4 Explanation:
 Question 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 C 1 3 2 4 6 5 D 3 2 4 1 6 5
Algorithm   Graph Traversal
Question 5 Explanation:
 Question 6
Which of the following problems is undecidable?
 A Membership problem for CFGs. B Ambiguity problem for CFGs. C Finiteness problem for FSAs. D Equivalence problem for FSAs.
Theory of Computation   Undecidability
Question 6 Explanation:
 Question 7
Which of the following is TRUE?
 A Every subset of a regular set is regular. B Every finite subset of a non-regular set is regular. C The union of two non-regular sets is not regular. D Infinite union of finite sets is regular.
Discrete Mathematics   Set Theory
Question 7 Explanation:
 Question 8
How many 3-to-8 line decoders with an enable input are needed to construct a 6- to-64 line decoder without using any other logic gates?
 A 7 B 8 C 9 D 10
Digital Logic   Combinational Circuit
Question 8 Explanation:
 Question 9
Consider the following Boolean function of four variables:
f (w, x, y, z)=$\Sigma$(1,3,4,6,9,11,12,14)
The function is:
 A independent of one variables B independent of two variables. C independent of three variables. D dependent on all the variables
Digital Logic   Boolean Algebra
Question 9 Explanation:
 Question 10
Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:
 A 9, 6, 5 B 7, 7, 6 C 7, 5, 8 D 9, 5, 6
Computer Organization   Cache Memory
Question 10 Explanation:
There are 10 questions to complete.