Gate (CS) 2008 Paper without Solution | GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Computer Science Engineering (CSE) PDF Download

 Page 1


CS? GATE Paper 2008
Q.1 – Q.20 Carry One Mark Each 
1. 
x
x sinx
lim equals
x cos x
?8
-
+
 
(A) 1 (B) -1 (C) 8 (D) -8
2. If P, Q, R are subsets of the universal set U, then 
( ) ( )
c c c
P Q R P Q R Q R n n ? n n ? ? is
(A) 
c c
Q R ? (B) 
c c
P Q R ? ? (C) 
c c c
P Q R ? ? (D) U 
3. The following system of equations
1 2 3
1 2 3
1 2 3
x x 2x 1
x 2x 3x 2
x 4x x 4
+ + =
+ + =
+ +a =
has a unique solution. The only possible value(s) for a is/are
(A) 0 (B) either 0 or 1 
(C) one of 0, 1 or -1 (D) any real number 
4. In the IEEE floating point representation the hexadecimal value 0x00000000
corresponds to
(A) The normalized value 2
-127
 (B) The normalized value 2
-126
(C) The normalized value +0 (D) The special value +0
5. In the Karnaugh map shown below, X denotes a don’t care term. What is the
minimal form of the function represented by the Karnaugh map?
(A) b.d a.d + (B) a.b b.d a.b.d + + (C) b.d a.b.d + (D) a.b b.d a.d + +
6. Let r denote number system radix. The only value(s) of r that satisfy the
equation 
r r
121 11 is / are =
(A) decimal 10 (B) decimal 11 
(C) decimal 10 and 11 (D) any value >2 
1 1 1
X
X
1 X 1
00 01 10 11
ab
cd
00
01
11
10
Page 2


CS? GATE Paper 2008
Q.1 – Q.20 Carry One Mark Each 
1. 
x
x sinx
lim equals
x cos x
?8
-
+
 
(A) 1 (B) -1 (C) 8 (D) -8
2. If P, Q, R are subsets of the universal set U, then 
( ) ( )
c c c
P Q R P Q R Q R n n ? n n ? ? is
(A) 
c c
Q R ? (B) 
c c
P Q R ? ? (C) 
c c c
P Q R ? ? (D) U 
3. The following system of equations
1 2 3
1 2 3
1 2 3
x x 2x 1
x 2x 3x 2
x 4x x 4
+ + =
+ + =
+ +a =
has a unique solution. The only possible value(s) for a is/are
(A) 0 (B) either 0 or 1 
(C) one of 0, 1 or -1 (D) any real number 
4. In the IEEE floating point representation the hexadecimal value 0x00000000
corresponds to
(A) The normalized value 2
-127
 (B) The normalized value 2
-126
(C) The normalized value +0 (D) The special value +0
5. In the Karnaugh map shown below, X denotes a don’t care term. What is the
minimal form of the function represented by the Karnaugh map?
(A) b.d a.d + (B) a.b b.d a.b.d + + (C) b.d a.b.d + (D) a.b b.d a.d + +
6. Let r denote number system radix. The only value(s) of r that satisfy the
equation 
r r
121 11 is / are =
(A) decimal 10 (B) decimal 11 
(C) decimal 10 and 11 (D) any value >2 
1 1 1
X
X
1 X 1
00 01 10 11
ab
cd
00
01
11
10
CS? GATE Paper 2008
7. The most efficient algorithm for finding the number of connected components in
an undirected graph on n vertices and m edges has time complexity
(A) ( ) n T (B) ( ) m T (C) ( ) m n T + (D) ( ) mn T
8. Given f
1
, f
3
 and f in canonical sum of products form (in decimal) for the circuit
( )
( )
( )
1
3
2
f m 4,5,6,7,8
f m 1,6,15
f m 1,6,8,15
then f is
= S
= S
= S
(A) ( ) m 4,6 S (B) ( ) m 4,8 S (C) ( ) m 6,8 S (D) ( ) m 4,6,8 S
9. Which of the following is true for the language
{ }
p
a p is a prime ? 
(A) It is not accepted by a Turing Machine 
(B) It is regular but not context-free 
(C) It is context-free but not regular 
(D) It is neither regular nor context-free, but accepted by a Turing machine 
10. Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
(A) I and II (B) I and IV (C) II and III (D)II and IV 
11. Which of the following describes a handle (as applicable to LR-parsing)
appropriately?
(A) It is the position in a sentential form where the next shift or reduce operation
will occur 
(B) It is non-terminal whose production will be used for reduction in the next 
step 
(C) It is a production that may be used for reduction in a future step along with a 
position in the sentential form where the next shift or reduce operation will 
occur 
(D) It is the production p that will be used for reduction in the next step along 
with a position in the sentential form where the right hand side of the 
production may be found 
f 2
f
1
f
3
f
Page 3


CS? GATE Paper 2008
Q.1 – Q.20 Carry One Mark Each 
1. 
x
x sinx
lim equals
x cos x
?8
-
+
 
(A) 1 (B) -1 (C) 8 (D) -8
2. If P, Q, R are subsets of the universal set U, then 
( ) ( )
c c c
P Q R P Q R Q R n n ? n n ? ? is
(A) 
c c
Q R ? (B) 
c c
P Q R ? ? (C) 
c c c
P Q R ? ? (D) U 
3. The following system of equations
1 2 3
1 2 3
1 2 3
x x 2x 1
x 2x 3x 2
x 4x x 4
+ + =
+ + =
+ +a =
has a unique solution. The only possible value(s) for a is/are
(A) 0 (B) either 0 or 1 
(C) one of 0, 1 or -1 (D) any real number 
4. In the IEEE floating point representation the hexadecimal value 0x00000000
corresponds to
(A) The normalized value 2
-127
 (B) The normalized value 2
-126
(C) The normalized value +0 (D) The special value +0
5. In the Karnaugh map shown below, X denotes a don’t care term. What is the
minimal form of the function represented by the Karnaugh map?
(A) b.d a.d + (B) a.b b.d a.b.d + + (C) b.d a.b.d + (D) a.b b.d a.d + +
6. Let r denote number system radix. The only value(s) of r that satisfy the
equation 
r r
121 11 is / are =
(A) decimal 10 (B) decimal 11 
(C) decimal 10 and 11 (D) any value >2 
1 1 1
X
X
1 X 1
00 01 10 11
ab
cd
00
01
11
10
CS? GATE Paper 2008
7. The most efficient algorithm for finding the number of connected components in
an undirected graph on n vertices and m edges has time complexity
(A) ( ) n T (B) ( ) m T (C) ( ) m n T + (D) ( ) mn T
8. Given f
1
, f
3
 and f in canonical sum of products form (in decimal) for the circuit
( )
( )
( )
1
3
2
f m 4,5,6,7,8
f m 1,6,15
f m 1,6,8,15
then f is
= S
= S
= S
(A) ( ) m 4,6 S (B) ( ) m 4,8 S (C) ( ) m 6,8 S (D) ( ) m 4,6,8 S
9. Which of the following is true for the language
{ }
p
a p is a prime ? 
(A) It is not accepted by a Turing Machine 
(B) It is regular but not context-free 
(C) It is context-free but not regular 
(D) It is neither regular nor context-free, but accepted by a Turing machine 
10. Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
(A) I and II (B) I and IV (C) II and III (D)II and IV 
11. Which of the following describes a handle (as applicable to LR-parsing)
appropriately?
(A) It is the position in a sentential form where the next shift or reduce operation
will occur 
(B) It is non-terminal whose production will be used for reduction in the next 
step 
(C) It is a production that may be used for reduction in a future step along with a 
position in the sentential form where the next shift or reduce operation will 
occur 
(D) It is the production p that will be used for reduction in the next step along 
with a position in the sentential form where the right hand side of the 
production may be found 
f 2
f
1
f
3
f
CS? GATE Paper 2008
12. Some code optimizations are carried out on the intermediate code because
(A) They enhance the portability of the compiler to other target processors
(B) Program analysis is more accurate on intermediate code than on machine
code 
(C) The information from dataflow analysis cannot otherwise be used for 
optimization 
(D) The information from the front end cannot otherwise be used for optimization 
13. If L and L are recursively enumerable then L is
(A) regular (B) context-free 
(C) context-sensitive (D) recursive 
14. What is the maximum size of data that the application layer can pass on to the
TCP layer below?
(A) Any size   (B) 2
16
 bytes-size of TCP header
(C) 2
16
 bytes   (D) 1500 bytes
15. Which of the following tuple relational calculus expression(s) is/are equivalent to
( ) ( )
t r P t ? ? ?
( ) ( )
( ) ( )
( ) ( )
( ) ( )
I. t r P t
II. t r P t
III. t r P t
IV. t r P t
¬? ?
? ?
¬? ? ¬
? ? ¬
(A) I only (B) II only 
(C) III only (D) III and IV only 
16. A clustering index is defined on the fields which are of type
(A) non-key and ordering (B) non-key and non-ordering 
(C) key and ordering (D) key and non-ordering 
17. Which of the following system calls results in the sending of SYN packets?
(A) socket (B) bind (C) listen (D) connect 
18. Which combination of the integer variables x, y and z makes the variable a get
the value 4 in the following expression?
( ) ( ) ( ) ( ) ( )
a x y ? x z ?x : z : y z ?y : z = > > >
(A) x 3,y 4,z 2 = = = (B) x 6,y 5,z 3 = = =
(C) x 6,y 3,z 5 = = = (D) x 5,y 4,z 5 = = =
Page 4


CS? GATE Paper 2008
Q.1 – Q.20 Carry One Mark Each 
1. 
x
x sinx
lim equals
x cos x
?8
-
+
 
(A) 1 (B) -1 (C) 8 (D) -8
2. If P, Q, R are subsets of the universal set U, then 
( ) ( )
c c c
P Q R P Q R Q R n n ? n n ? ? is
(A) 
c c
Q R ? (B) 
c c
P Q R ? ? (C) 
c c c
P Q R ? ? (D) U 
3. The following system of equations
1 2 3
1 2 3
1 2 3
x x 2x 1
x 2x 3x 2
x 4x x 4
+ + =
+ + =
+ +a =
has a unique solution. The only possible value(s) for a is/are
(A) 0 (B) either 0 or 1 
(C) one of 0, 1 or -1 (D) any real number 
4. In the IEEE floating point representation the hexadecimal value 0x00000000
corresponds to
(A) The normalized value 2
-127
 (B) The normalized value 2
-126
(C) The normalized value +0 (D) The special value +0
5. In the Karnaugh map shown below, X denotes a don’t care term. What is the
minimal form of the function represented by the Karnaugh map?
(A) b.d a.d + (B) a.b b.d a.b.d + + (C) b.d a.b.d + (D) a.b b.d a.d + +
6. Let r denote number system radix. The only value(s) of r that satisfy the
equation 
r r
121 11 is / are =
(A) decimal 10 (B) decimal 11 
(C) decimal 10 and 11 (D) any value >2 
1 1 1
X
X
1 X 1
00 01 10 11
ab
cd
00
01
11
10
CS? GATE Paper 2008
7. The most efficient algorithm for finding the number of connected components in
an undirected graph on n vertices and m edges has time complexity
(A) ( ) n T (B) ( ) m T (C) ( ) m n T + (D) ( ) mn T
8. Given f
1
, f
3
 and f in canonical sum of products form (in decimal) for the circuit
( )
( )
( )
1
3
2
f m 4,5,6,7,8
f m 1,6,15
f m 1,6,8,15
then f is
= S
= S
= S
(A) ( ) m 4,6 S (B) ( ) m 4,8 S (C) ( ) m 6,8 S (D) ( ) m 4,6,8 S
9. Which of the following is true for the language
{ }
p
a p is a prime ? 
(A) It is not accepted by a Turing Machine 
(B) It is regular but not context-free 
(C) It is context-free but not regular 
(D) It is neither regular nor context-free, but accepted by a Turing machine 
10. Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
(A) I and II (B) I and IV (C) II and III (D)II and IV 
11. Which of the following describes a handle (as applicable to LR-parsing)
appropriately?
(A) It is the position in a sentential form where the next shift or reduce operation
will occur 
(B) It is non-terminal whose production will be used for reduction in the next 
step 
(C) It is a production that may be used for reduction in a future step along with a 
position in the sentential form where the next shift or reduce operation will 
occur 
(D) It is the production p that will be used for reduction in the next step along 
with a position in the sentential form where the right hand side of the 
production may be found 
f 2
f
1
f
3
f
CS? GATE Paper 2008
12. Some code optimizations are carried out on the intermediate code because
(A) They enhance the portability of the compiler to other target processors
(B) Program analysis is more accurate on intermediate code than on machine
code 
(C) The information from dataflow analysis cannot otherwise be used for 
optimization 
(D) The information from the front end cannot otherwise be used for optimization 
13. If L and L are recursively enumerable then L is
(A) regular (B) context-free 
(C) context-sensitive (D) recursive 
14. What is the maximum size of data that the application layer can pass on to the
TCP layer below?
(A) Any size   (B) 2
16
 bytes-size of TCP header
(C) 2
16
 bytes   (D) 1500 bytes
15. Which of the following tuple relational calculus expression(s) is/are equivalent to
( ) ( )
t r P t ? ? ?
( ) ( )
( ) ( )
( ) ( )
( ) ( )
I. t r P t
II. t r P t
III. t r P t
IV. t r P t
¬? ?
? ?
¬? ? ¬
? ? ¬
(A) I only (B) II only 
(C) III only (D) III and IV only 
16. A clustering index is defined on the fields which are of type
(A) non-key and ordering (B) non-key and non-ordering 
(C) key and ordering (D) key and non-ordering 
17. Which of the following system calls results in the sending of SYN packets?
(A) socket (B) bind (C) listen (D) connect 
18. Which combination of the integer variables x, y and z makes the variable a get
the value 4 in the following expression?
( ) ( ) ( ) ( ) ( )
a x y ? x z ?x : z : y z ?y : z = > > >
(A) x 3,y 4,z 2 = = = (B) x 6,y 5,z 3 = = =
(C) x 6,y 3,z 5 = = = (D) x 5,y 4,z 5 = = =
CS? GATE Paper 2008
19. The Breadth First Search algorithm has been implemented using the queue data
structure. One possible order of visiting the nodes of the following graph is
(A) MNOPQR (B) NQMPOR (C) QMNPRO (D) QMNPOR 
20. The data blocks of a very large file in the Unix file system are allocated using
(A) contiguous allocation
(B) linked allocation
(C) indexed allocation
(D) an extension of indexed allocation
Q.21 – Q.75 Carry Two Marks Each 
21. The minimum number of equal length subintervals needed to approximate
2
x 6
1
1
xe dx to an accuracy of at least 10 using the trapezoidal rule is
3
-
×
?
 
(A) 1000e (B) 1000 (C) 100e (D) 100 
22. The Newton-Raphson iteration 
n 1 n
n
1 R
x x
2 x
+
? ?
= +
? ?
? ?
 can be used to compute the 
(A) square of R (B) reciprocal of R 
(C) square root of R (D) logarithm of R 
23. Which of the following statements is true for every planar graph on n vertices?
(A) The graph is connected
(B) The graph is Eulerian
(C) The graph has a vertex-cover of size at most 3n/4
(D) The graph has an independent set of size at least n/3
24. 
1 i 2k 1 i 2k
i odd i even
Let P i and Q i, where k is a positive integer. Then
== ==
= =
? ?
(A) P Q K = - (B) P Q K = + (C) P = Q (D) P Q 2K = +
M N O
R Q P
Page 5


CS? GATE Paper 2008
Q.1 – Q.20 Carry One Mark Each 
1. 
x
x sinx
lim equals
x cos x
?8
-
+
 
(A) 1 (B) -1 (C) 8 (D) -8
2. If P, Q, R are subsets of the universal set U, then 
( ) ( )
c c c
P Q R P Q R Q R n n ? n n ? ? is
(A) 
c c
Q R ? (B) 
c c
P Q R ? ? (C) 
c c c
P Q R ? ? (D) U 
3. The following system of equations
1 2 3
1 2 3
1 2 3
x x 2x 1
x 2x 3x 2
x 4x x 4
+ + =
+ + =
+ +a =
has a unique solution. The only possible value(s) for a is/are
(A) 0 (B) either 0 or 1 
(C) one of 0, 1 or -1 (D) any real number 
4. In the IEEE floating point representation the hexadecimal value 0x00000000
corresponds to
(A) The normalized value 2
-127
 (B) The normalized value 2
-126
(C) The normalized value +0 (D) The special value +0
5. In the Karnaugh map shown below, X denotes a don’t care term. What is the
minimal form of the function represented by the Karnaugh map?
(A) b.d a.d + (B) a.b b.d a.b.d + + (C) b.d a.b.d + (D) a.b b.d a.d + +
6. Let r denote number system radix. The only value(s) of r that satisfy the
equation 
r r
121 11 is / are =
(A) decimal 10 (B) decimal 11 
(C) decimal 10 and 11 (D) any value >2 
1 1 1
X
X
1 X 1
00 01 10 11
ab
cd
00
01
11
10
CS? GATE Paper 2008
7. The most efficient algorithm for finding the number of connected components in
an undirected graph on n vertices and m edges has time complexity
(A) ( ) n T (B) ( ) m T (C) ( ) m n T + (D) ( ) mn T
8. Given f
1
, f
3
 and f in canonical sum of products form (in decimal) for the circuit
( )
( )
( )
1
3
2
f m 4,5,6,7,8
f m 1,6,15
f m 1,6,8,15
then f is
= S
= S
= S
(A) ( ) m 4,6 S (B) ( ) m 4,8 S (C) ( ) m 6,8 S (D) ( ) m 4,6,8 S
9. Which of the following is true for the language
{ }
p
a p is a prime ? 
(A) It is not accepted by a Turing Machine 
(B) It is regular but not context-free 
(C) It is context-free but not regular 
(D) It is neither regular nor context-free, but accepted by a Turing machine 
10. Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
(A) I and II (B) I and IV (C) II and III (D)II and IV 
11. Which of the following describes a handle (as applicable to LR-parsing)
appropriately?
(A) It is the position in a sentential form where the next shift or reduce operation
will occur 
(B) It is non-terminal whose production will be used for reduction in the next 
step 
(C) It is a production that may be used for reduction in a future step along with a 
position in the sentential form where the next shift or reduce operation will 
occur 
(D) It is the production p that will be used for reduction in the next step along 
with a position in the sentential form where the right hand side of the 
production may be found 
f 2
f
1
f
3
f
CS? GATE Paper 2008
12. Some code optimizations are carried out on the intermediate code because
(A) They enhance the portability of the compiler to other target processors
(B) Program analysis is more accurate on intermediate code than on machine
code 
(C) The information from dataflow analysis cannot otherwise be used for 
optimization 
(D) The information from the front end cannot otherwise be used for optimization 
13. If L and L are recursively enumerable then L is
(A) regular (B) context-free 
(C) context-sensitive (D) recursive 
14. What is the maximum size of data that the application layer can pass on to the
TCP layer below?
(A) Any size   (B) 2
16
 bytes-size of TCP header
(C) 2
16
 bytes   (D) 1500 bytes
15. Which of the following tuple relational calculus expression(s) is/are equivalent to
( ) ( )
t r P t ? ? ?
( ) ( )
( ) ( )
( ) ( )
( ) ( )
I. t r P t
II. t r P t
III. t r P t
IV. t r P t
¬? ?
? ?
¬? ? ¬
? ? ¬
(A) I only (B) II only 
(C) III only (D) III and IV only 
16. A clustering index is defined on the fields which are of type
(A) non-key and ordering (B) non-key and non-ordering 
(C) key and ordering (D) key and non-ordering 
17. Which of the following system calls results in the sending of SYN packets?
(A) socket (B) bind (C) listen (D) connect 
18. Which combination of the integer variables x, y and z makes the variable a get
the value 4 in the following expression?
( ) ( ) ( ) ( ) ( )
a x y ? x z ?x : z : y z ?y : z = > > >
(A) x 3,y 4,z 2 = = = (B) x 6,y 5,z 3 = = =
(C) x 6,y 3,z 5 = = = (D) x 5,y 4,z 5 = = =
CS? GATE Paper 2008
19. The Breadth First Search algorithm has been implemented using the queue data
structure. One possible order of visiting the nodes of the following graph is
(A) MNOPQR (B) NQMPOR (C) QMNPRO (D) QMNPOR 
20. The data blocks of a very large file in the Unix file system are allocated using
(A) contiguous allocation
(B) linked allocation
(C) indexed allocation
(D) an extension of indexed allocation
Q.21 – Q.75 Carry Two Marks Each 
21. The minimum number of equal length subintervals needed to approximate
2
x 6
1
1
xe dx to an accuracy of at least 10 using the trapezoidal rule is
3
-
×
?
 
(A) 1000e (B) 1000 (C) 100e (D) 100 
22. The Newton-Raphson iteration 
n 1 n
n
1 R
x x
2 x
+
? ?
= +
? ?
? ?
 can be used to compute the 
(A) square of R (B) reciprocal of R 
(C) square root of R (D) logarithm of R 
23. Which of the following statements is true for every planar graph on n vertices?
(A) The graph is connected
(B) The graph is Eulerian
(C) The graph has a vertex-cover of size at most 3n/4
(D) The graph has an independent set of size at least n/3
24. 
1 i 2k 1 i 2k
i odd i even
Let P i and Q i, where k is a positive integer. Then
== ==
= =
? ?
(A) P Q K = - (B) P Q K = + (C) P = Q (D) P Q 2K = +
M N O
R Q P
CS? GATE Paper 2008
25. A point on a curve is said to be an extremum if it is a local minimum or a local
maximum. The number of distinct extrema for the curve 
4 3 2
3x 16x 24x 37 is - + +
(A) 0 (B) 1 (C) 2 (D) 3
26. If P, Q, R are Boolean variables, then
( )( )( )
P Q P.Q P.R P.R Q + + +
Simplifies to 
(A) P.Q (B) P.R (C) P.Q R + (D) P.R Q +
27. Aishwarya studies either computer science or mathematics everyday. If she
studies computer science on a day, then the probability that the studies
mathematics the next day is 0.6. If she studies mathematics on a day, then the
probability that the studies computer science the next day is 0.4. Given that
Aishwarya studies computer science on Monday, what is the probability that she
studies computer science on Wednesday?
(A) 0.24 (B) 0.36 (C) 0.4 (D) 0.6 
28. How many of the following matrices have an eigenvalue 1?
1 0 0 1 1 1 1 0
and
0 0 0 0 1 1 1 1
- - ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
-
? ? ? ? ? ? ? ?
(A) one (B) two (C) three (D) four 
29. Let X be a random variable following normal distribution with mean +1 and
variance 4. Let Y be another normal variable with mean -1 and variance
unknown. If ( ) ( ) P X 1 P Y 2 , = - = = the standard deviation of Y is
(A) 3 (B) 2 (C) 2 (D) 1 
30. Let fsa and pda be two predicates such that fsa(x) means x is a finite state
automaton, and pda(y) means that y is a pushdown automaton. Let equivalent
be another predicate such that equivalent (a, b) means a and b are equivalent.
Which of the following first order logic statements represents the following:
Each finite state automaton has an equivalent pushdown automaton
(A) ( ) ( ) ( ) ( ) ( )
x fsa x y pda y equivalent x,y ? ? ? ?
(B) ( ) ( ) ( ) ( )
~ y x fsa x pda y equivalent x,y ? ? ? ?
(C) ( ) ( ) ( ) ( )
x y fsa x pda y equivalent x,y ? ? ? ?
(D) ( ) ( ) ( ) ( )
x y fsa y pda x equivalent x,y ? ? ? ?