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 ? ? ? ?Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

131 docs|159 tests