Gate (CS) 2012 Paper with Solution (Set A) | GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Computer Science Engineering (CSE) PDF Download

 Page 1


|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Which of the following problems are decidable? 
 1)  Does a given program ever produce an output? 
 2)  If L is context-free language, then, is L also context-free? 
 3)  If L is regular language, then, is L also regular? 
 4)  If L is recursive language, then, is L also recursive? 
 (A) 1,2,3,4 (B) 1,2 (C) 2,3,4 (D) 3,4 
 
Answer:- (D) 
Exp:-  CFL’s are not closed under complementation. Regular and recursive languages are closed 
under complementation. 
 
2. Given the language L-{ab, aa, baa}, which of the following strings are in L*? 
  1) abaabaaabaa 
  2) aaaabaaaa 
  3) baaaaabaaaab 
  4) baaaaabaa 
 (A) 1,2 and 3 (B) 2,3 and 4 (C) 1,2 and 4 (D) 1,3 and 4 
Answer:-(C) 
Exp:- { } L ab, aa, baa = 
 Let S1 = ab , S2 = aa and S3 =baa 
 abaabaaabaa can be written as S1S2S3S1S2 
 aaaabaaaa can be written as S1S1S3S1 
 baaaaabaa can be written as S3S2S1S2 
 
3. In the IPv4 addressing format, the number of networks allowed under Class C addresses is 
 (A) 2
14 
(B) 2
7 
(C) 2
21 
(B) 2
24 
Answer:-(C) 
Exp:- For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence 
total number of networks possible is 2
21
 
 
4. Which of the following transport layer protocols is used to support electronic mail? 
 (A) SMTP (B) IP (C) TCP (D) UDP 
Answer:-(C) 
Exp:- E-mail uses SMTP, application layer protocol which intern uses TCP transport layer protocol. 
 
5. Consider a random variable X that takes values + 1 and -1 with probability 0.5 each. The 
values of the cumulative distribution function F(x) at x = -1 and +1 are 
 (A) 0 and 0.5   (B) 0 and 1   
Page 2


|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Which of the following problems are decidable? 
 1)  Does a given program ever produce an output? 
 2)  If L is context-free language, then, is L also context-free? 
 3)  If L is regular language, then, is L also regular? 
 4)  If L is recursive language, then, is L also recursive? 
 (A) 1,2,3,4 (B) 1,2 (C) 2,3,4 (D) 3,4 
 
Answer:- (D) 
Exp:-  CFL’s are not closed under complementation. Regular and recursive languages are closed 
under complementation. 
 
2. Given the language L-{ab, aa, baa}, which of the following strings are in L*? 
  1) abaabaaabaa 
  2) aaaabaaaa 
  3) baaaaabaaaab 
  4) baaaaabaa 
 (A) 1,2 and 3 (B) 2,3 and 4 (C) 1,2 and 4 (D) 1,3 and 4 
Answer:-(C) 
Exp:- { } L ab, aa, baa = 
 Let S1 = ab , S2 = aa and S3 =baa 
 abaabaaabaa can be written as S1S2S3S1S2 
 aaaabaaaa can be written as S1S1S3S1 
 baaaaabaa can be written as S3S2S1S2 
 
3. In the IPv4 addressing format, the number of networks allowed under Class C addresses is 
 (A) 2
14 
(B) 2
7 
(C) 2
21 
(B) 2
24 
Answer:-(C) 
Exp:- For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence 
total number of networks possible is 2
21
 
 
4. Which of the following transport layer protocols is used to support electronic mail? 
 (A) SMTP (B) IP (C) TCP (D) UDP 
Answer:-(C) 
Exp:- E-mail uses SMTP, application layer protocol which intern uses TCP transport layer protocol. 
 
5. Consider a random variable X that takes values + 1 and -1 with probability 0.5 each. The 
values of the cumulative distribution function F(x) at x = -1 and +1 are 
 (A) 0 and 0.5   (B) 0 and 1   
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 2 
 (C) 0.5 and 1   (D) 0.25 and 0.75 
Answer:-(C) 
Exp:- The cumulative distribution function 
  
( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( )
F x P X x
F 1 P X 1 P X 1 0.5
F 1 P X 1 P X 1 P X 1 0.5 0.5 1
= =
- = =- = =- =
+ = =+ = =- + =+ = + =
 
 
6. Register renaming is done is pipelined processors 
 (A) as an alternative to register allocation at compile time 
 (B) for efficient access to function parameters and local variables 
 (C) to handle certain kinds of hazards 
 (D) as part of address translation 
Answer:-(C) 
Exp:- Register renaming is done to eliminate WAR/WAW hazards. 
 
7. The amount of ROM needed to implement a 4 bit multiplier is 
 (A) 64 bits (B) 128 bits (C) 1 Kbits (D) 2 Kbits 
Answer:-(D) 
Exp:- For a 4 bit multiplier there are 
4 4 8
2 2 2 256 × = = combinations. 
 Output will contain 8 bits. 
 So the amount of ROM needed is 
8
2 8 bits 2Kbits. × = 
 
8. Let W(n) and A(n) denote respectively, the worst case and average case running time of an 
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE? 
 (A) ( ) ( ) ( )
A n W n =O  (B) ( ) ( ) ( )
A n W n =T 
 (C) ( ) ( ) ( )
A n O W n =  (D) ( ) ( ) ( )
A n o W n = 
Answer:-(C)  
Exp:-  The average case time can be lesser than or even equal to the worst case. So A(n) would be 
upper bounded by W(n)  and it will not be strict upper bound as it can even be same (e.g. 
Bubble Sort and merge sort). 
 ( ) ( ) ( )
A n O W n ? = 
 
9. Let G be a simple undirected planar graph on 10 vertices with 15edges. If G is a connected 
graph, then the number of bounded faces in any embedding of G on the plane is equal to 
 (A) 3 (B) 4 (C) 5 (D) 6 
Answer:-(D) 
Exp:- We have the relation V-E+F=2, by this we will get the total number of faces,  
Page 3


|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Which of the following problems are decidable? 
 1)  Does a given program ever produce an output? 
 2)  If L is context-free language, then, is L also context-free? 
 3)  If L is regular language, then, is L also regular? 
 4)  If L is recursive language, then, is L also recursive? 
 (A) 1,2,3,4 (B) 1,2 (C) 2,3,4 (D) 3,4 
 
Answer:- (D) 
Exp:-  CFL’s are not closed under complementation. Regular and recursive languages are closed 
under complementation. 
 
2. Given the language L-{ab, aa, baa}, which of the following strings are in L*? 
  1) abaabaaabaa 
  2) aaaabaaaa 
  3) baaaaabaaaab 
  4) baaaaabaa 
 (A) 1,2 and 3 (B) 2,3 and 4 (C) 1,2 and 4 (D) 1,3 and 4 
Answer:-(C) 
Exp:- { } L ab, aa, baa = 
 Let S1 = ab , S2 = aa and S3 =baa 
 abaabaaabaa can be written as S1S2S3S1S2 
 aaaabaaaa can be written as S1S1S3S1 
 baaaaabaa can be written as S3S2S1S2 
 
3. In the IPv4 addressing format, the number of networks allowed under Class C addresses is 
 (A) 2
14 
(B) 2
7 
(C) 2
21 
(B) 2
24 
Answer:-(C) 
Exp:- For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence 
total number of networks possible is 2
21
 
 
4. Which of the following transport layer protocols is used to support electronic mail? 
 (A) SMTP (B) IP (C) TCP (D) UDP 
Answer:-(C) 
Exp:- E-mail uses SMTP, application layer protocol which intern uses TCP transport layer protocol. 
 
5. Consider a random variable X that takes values + 1 and -1 with probability 0.5 each. The 
values of the cumulative distribution function F(x) at x = -1 and +1 are 
 (A) 0 and 0.5   (B) 0 and 1   
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 2 
 (C) 0.5 and 1   (D) 0.25 and 0.75 
Answer:-(C) 
Exp:- The cumulative distribution function 
  
( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( )
F x P X x
F 1 P X 1 P X 1 0.5
F 1 P X 1 P X 1 P X 1 0.5 0.5 1
= =
- = =- = =- =
+ = =+ = =- + =+ = + =
 
 
6. Register renaming is done is pipelined processors 
 (A) as an alternative to register allocation at compile time 
 (B) for efficient access to function parameters and local variables 
 (C) to handle certain kinds of hazards 
 (D) as part of address translation 
Answer:-(C) 
Exp:- Register renaming is done to eliminate WAR/WAW hazards. 
 
7. The amount of ROM needed to implement a 4 bit multiplier is 
 (A) 64 bits (B) 128 bits (C) 1 Kbits (D) 2 Kbits 
Answer:-(D) 
Exp:- For a 4 bit multiplier there are 
4 4 8
2 2 2 256 × = = combinations. 
 Output will contain 8 bits. 
 So the amount of ROM needed is 
8
2 8 bits 2Kbits. × = 
 
8. Let W(n) and A(n) denote respectively, the worst case and average case running time of an 
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE? 
 (A) ( ) ( ) ( )
A n W n =O  (B) ( ) ( ) ( )
A n W n =T 
 (C) ( ) ( ) ( )
A n O W n =  (D) ( ) ( ) ( )
A n o W n = 
Answer:-(C)  
Exp:-  The average case time can be lesser than or even equal to the worst case. So A(n) would be 
upper bounded by W(n)  and it will not be strict upper bound as it can even be same (e.g. 
Bubble Sort and merge sort). 
 ( ) ( ) ( )
A n O W n ? = 
 
9. Let G be a simple undirected planar graph on 10 vertices with 15edges. If G is a connected 
graph, then the number of bounded faces in any embedding of G on the plane is equal to 
 (A) 3 (B) 4 (C) 5 (D) 6 
Answer:-(D) 
Exp:- We have the relation V-E+F=2, by this we will get the total number of faces,  
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 3 
 F = 7. Out of 7 faces one is an unbounded face, so total 6 bounded faces. 
10. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem 
with n discs is 
 (A) ( ) ( ) T n 2T n 2 2 = - +  (B) ( ) ( ) T n 2T n 1 n = - + 
 (C) ( ) ( ) T n 2T n / 2 1 = +  (D) ( ) ( ) T n 2T n 1 1 = - + 
Answer:-(D) 
Exp:- Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B 
 The following sequence of steps are executed recursively 
   1.move n-1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)  
 2.move disc n from A to C---------1  
 3.move n-1 discs from B to C so they sit on disc n----- T(n-1) 
 So, T(n) = 2T(n-1) +1 
 
11. Which of the following statements are TRUE about an SQL query? 
 P :  An SQL query can contain a HAVING clause even if it does not have a  
       GROUP BY clause 
 Q :  An SQL query can contain a HAVING clause only if it has GROUP BY       
        clause  
 R :  All attributes used in the GROUP BY clause must appear in the SELECT  
        clause 
 S : Not all attributes used in the GROUP BY clause need to appear in the    
       SELECT clause 
 (A) P and R (B) P and S (C) Q and R (D) Q and S 
Answer:-(B) 
Exp:-  If we use a HAVING clause without a GROUP BY clause, the HAVING condition applies to 
all rows that satisfy the search condition. In other words, all rows that satisfy the search 
condition make up a single group. So, option P is true and Q is  false. 
 
 S is also true as an example consider the following table and query. 
Id Name 
1 Ramesh 
 2 Ramesh 
3 Rajesh 
4 Suresh 
 Select count (*) 
 From student 
 Group by Name 
  
 Output will be  
  
Count (*) 
2 
1 
Page 4


|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Which of the following problems are decidable? 
 1)  Does a given program ever produce an output? 
 2)  If L is context-free language, then, is L also context-free? 
 3)  If L is regular language, then, is L also regular? 
 4)  If L is recursive language, then, is L also recursive? 
 (A) 1,2,3,4 (B) 1,2 (C) 2,3,4 (D) 3,4 
 
Answer:- (D) 
Exp:-  CFL’s are not closed under complementation. Regular and recursive languages are closed 
under complementation. 
 
2. Given the language L-{ab, aa, baa}, which of the following strings are in L*? 
  1) abaabaaabaa 
  2) aaaabaaaa 
  3) baaaaabaaaab 
  4) baaaaabaa 
 (A) 1,2 and 3 (B) 2,3 and 4 (C) 1,2 and 4 (D) 1,3 and 4 
Answer:-(C) 
Exp:- { } L ab, aa, baa = 
 Let S1 = ab , S2 = aa and S3 =baa 
 abaabaaabaa can be written as S1S2S3S1S2 
 aaaabaaaa can be written as S1S1S3S1 
 baaaaabaa can be written as S3S2S1S2 
 
3. In the IPv4 addressing format, the number of networks allowed under Class C addresses is 
 (A) 2
14 
(B) 2
7 
(C) 2
21 
(B) 2
24 
Answer:-(C) 
Exp:- For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence 
total number of networks possible is 2
21
 
 
4. Which of the following transport layer protocols is used to support electronic mail? 
 (A) SMTP (B) IP (C) TCP (D) UDP 
Answer:-(C) 
Exp:- E-mail uses SMTP, application layer protocol which intern uses TCP transport layer protocol. 
 
5. Consider a random variable X that takes values + 1 and -1 with probability 0.5 each. The 
values of the cumulative distribution function F(x) at x = -1 and +1 are 
 (A) 0 and 0.5   (B) 0 and 1   
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 2 
 (C) 0.5 and 1   (D) 0.25 and 0.75 
Answer:-(C) 
Exp:- The cumulative distribution function 
  
( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( )
F x P X x
F 1 P X 1 P X 1 0.5
F 1 P X 1 P X 1 P X 1 0.5 0.5 1
= =
- = =- = =- =
+ = =+ = =- + =+ = + =
 
 
6. Register renaming is done is pipelined processors 
 (A) as an alternative to register allocation at compile time 
 (B) for efficient access to function parameters and local variables 
 (C) to handle certain kinds of hazards 
 (D) as part of address translation 
Answer:-(C) 
Exp:- Register renaming is done to eliminate WAR/WAW hazards. 
 
7. The amount of ROM needed to implement a 4 bit multiplier is 
 (A) 64 bits (B) 128 bits (C) 1 Kbits (D) 2 Kbits 
Answer:-(D) 
Exp:- For a 4 bit multiplier there are 
4 4 8
2 2 2 256 × = = combinations. 
 Output will contain 8 bits. 
 So the amount of ROM needed is 
8
2 8 bits 2Kbits. × = 
 
8. Let W(n) and A(n) denote respectively, the worst case and average case running time of an 
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE? 
 (A) ( ) ( ) ( )
A n W n =O  (B) ( ) ( ) ( )
A n W n =T 
 (C) ( ) ( ) ( )
A n O W n =  (D) ( ) ( ) ( )
A n o W n = 
Answer:-(C)  
Exp:-  The average case time can be lesser than or even equal to the worst case. So A(n) would be 
upper bounded by W(n)  and it will not be strict upper bound as it can even be same (e.g. 
Bubble Sort and merge sort). 
 ( ) ( ) ( )
A n O W n ? = 
 
9. Let G be a simple undirected planar graph on 10 vertices with 15edges. If G is a connected 
graph, then the number of bounded faces in any embedding of G on the plane is equal to 
 (A) 3 (B) 4 (C) 5 (D) 6 
Answer:-(D) 
Exp:- We have the relation V-E+F=2, by this we will get the total number of faces,  
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 3 
 F = 7. Out of 7 faces one is an unbounded face, so total 6 bounded faces. 
10. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem 
with n discs is 
 (A) ( ) ( ) T n 2T n 2 2 = - +  (B) ( ) ( ) T n 2T n 1 n = - + 
 (C) ( ) ( ) T n 2T n / 2 1 = +  (D) ( ) ( ) T n 2T n 1 1 = - + 
Answer:-(D) 
Exp:- Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B 
 The following sequence of steps are executed recursively 
   1.move n-1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)  
 2.move disc n from A to C---------1  
 3.move n-1 discs from B to C so they sit on disc n----- T(n-1) 
 So, T(n) = 2T(n-1) +1 
 
11. Which of the following statements are TRUE about an SQL query? 
 P :  An SQL query can contain a HAVING clause even if it does not have a  
       GROUP BY clause 
 Q :  An SQL query can contain a HAVING clause only if it has GROUP BY       
        clause  
 R :  All attributes used in the GROUP BY clause must appear in the SELECT  
        clause 
 S : Not all attributes used in the GROUP BY clause need to appear in the    
       SELECT clause 
 (A) P and R (B) P and S (C) Q and R (D) Q and S 
Answer:-(B) 
Exp:-  If we use a HAVING clause without a GROUP BY clause, the HAVING condition applies to 
all rows that satisfy the search condition. In other words, all rows that satisfy the search 
condition make up a single group. So, option P is true and Q is  false. 
 
 S is also true as an example consider the following table and query. 
Id Name 
1 Ramesh 
 2 Ramesh 
3 Rajesh 
4 Suresh 
 Select count (*) 
 From student 
 Group by Name 
  
 Output will be  
  
Count (*) 
2 
1 
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 4 
1 
12. Given the basic ER and relational models, which of the following is INCORRECT? 
 (A)  An attribute of an entity can have more than one value 
 (B)  An attribute of an entity can be composite  
 (C)  In a row of a relational table, an attribute can have more than one value 
 (D)  In a row of a relational table, an attribute can have exactly one value or a NULL value 
Answer:-(C) 
Exp:-  The term ‘entity’ belongs to ER model and the term ‘relational table’ belongs to relational 
model. 
 Options A and B both are true since ER model supports both multivalued and composite 
attributes. 
 As multivalued attributes are not allowed in relational databases, in a row of a relational 
(table), an attribute cannot have more than one value. 
 
13. What is the complement of the language accepted by the NFA show below? 
 Assume {a} and S= e is the empty string. 
  
 
 
 
 
 
 (A) Ø (B) { } e (C) a * (D) { } a,e 
Answer:- (B) 
Exp:- Language accepted by NFA is a
+
, so complement of this language is {?} 
 
 
14. What is the correct translation of the following statement into mathematical logic? 
 “Some real numbers are rational” 
 (A) ( ) ( ) ( )
x real x v rational x ? (B) ( ) ( ) ( )
x real x rational x ? ? 
 (C) ( ) ( ) ( )
x real x rational x ? ? (D) ( ) ( ) ( )
x rational x real x ? ? 
Answer:- (C) 
Exp:- Option A:  There exists x which is either real or rational and can be both. 
 Option B: All real numbers are rational 
 Option C: There exists a real number which is rational. 
 Option D: There exists some number which is not rational or which is real.  
 
15. Let A be the 2 x 2 matrix with elements a
11
 = a
12
 = a
21
= + 1 and a
22
 =-1. Then the eigen values 
of the matrix A
19
 are 
 (A) 1024 and -1024   (B) 1024 2 and 1024 2 - 
a e
 
e
 
Page 5


|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Which of the following problems are decidable? 
 1)  Does a given program ever produce an output? 
 2)  If L is context-free language, then, is L also context-free? 
 3)  If L is regular language, then, is L also regular? 
 4)  If L is recursive language, then, is L also recursive? 
 (A) 1,2,3,4 (B) 1,2 (C) 2,3,4 (D) 3,4 
 
Answer:- (D) 
Exp:-  CFL’s are not closed under complementation. Regular and recursive languages are closed 
under complementation. 
 
2. Given the language L-{ab, aa, baa}, which of the following strings are in L*? 
  1) abaabaaabaa 
  2) aaaabaaaa 
  3) baaaaabaaaab 
  4) baaaaabaa 
 (A) 1,2 and 3 (B) 2,3 and 4 (C) 1,2 and 4 (D) 1,3 and 4 
Answer:-(C) 
Exp:- { } L ab, aa, baa = 
 Let S1 = ab , S2 = aa and S3 =baa 
 abaabaaabaa can be written as S1S2S3S1S2 
 aaaabaaaa can be written as S1S1S3S1 
 baaaaabaa can be written as S3S2S1S2 
 
3. In the IPv4 addressing format, the number of networks allowed under Class C addresses is 
 (A) 2
14 
(B) 2
7 
(C) 2
21 
(B) 2
24 
Answer:-(C) 
Exp:- For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence 
total number of networks possible is 2
21
 
 
4. Which of the following transport layer protocols is used to support electronic mail? 
 (A) SMTP (B) IP (C) TCP (D) UDP 
Answer:-(C) 
Exp:- E-mail uses SMTP, application layer protocol which intern uses TCP transport layer protocol. 
 
5. Consider a random variable X that takes values + 1 and -1 with probability 0.5 each. The 
values of the cumulative distribution function F(x) at x = -1 and +1 are 
 (A) 0 and 0.5   (B) 0 and 1   
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 2 
 (C) 0.5 and 1   (D) 0.25 and 0.75 
Answer:-(C) 
Exp:- The cumulative distribution function 
  
( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( )
F x P X x
F 1 P X 1 P X 1 0.5
F 1 P X 1 P X 1 P X 1 0.5 0.5 1
= =
- = =- = =- =
+ = =+ = =- + =+ = + =
 
 
6. Register renaming is done is pipelined processors 
 (A) as an alternative to register allocation at compile time 
 (B) for efficient access to function parameters and local variables 
 (C) to handle certain kinds of hazards 
 (D) as part of address translation 
Answer:-(C) 
Exp:- Register renaming is done to eliminate WAR/WAW hazards. 
 
7. The amount of ROM needed to implement a 4 bit multiplier is 
 (A) 64 bits (B) 128 bits (C) 1 Kbits (D) 2 Kbits 
Answer:-(D) 
Exp:- For a 4 bit multiplier there are 
4 4 8
2 2 2 256 × = = combinations. 
 Output will contain 8 bits. 
 So the amount of ROM needed is 
8
2 8 bits 2Kbits. × = 
 
8. Let W(n) and A(n) denote respectively, the worst case and average case running time of an 
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE? 
 (A) ( ) ( ) ( )
A n W n =O  (B) ( ) ( ) ( )
A n W n =T 
 (C) ( ) ( ) ( )
A n O W n =  (D) ( ) ( ) ( )
A n o W n = 
Answer:-(C)  
Exp:-  The average case time can be lesser than or even equal to the worst case. So A(n) would be 
upper bounded by W(n)  and it will not be strict upper bound as it can even be same (e.g. 
Bubble Sort and merge sort). 
 ( ) ( ) ( )
A n O W n ? = 
 
9. Let G be a simple undirected planar graph on 10 vertices with 15edges. If G is a connected 
graph, then the number of bounded faces in any embedding of G on the plane is equal to 
 (A) 3 (B) 4 (C) 5 (D) 6 
Answer:-(D) 
Exp:- We have the relation V-E+F=2, by this we will get the total number of faces,  
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 3 
 F = 7. Out of 7 faces one is an unbounded face, so total 6 bounded faces. 
10. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem 
with n discs is 
 (A) ( ) ( ) T n 2T n 2 2 = - +  (B) ( ) ( ) T n 2T n 1 n = - + 
 (C) ( ) ( ) T n 2T n / 2 1 = +  (D) ( ) ( ) T n 2T n 1 1 = - + 
Answer:-(D) 
Exp:- Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B 
 The following sequence of steps are executed recursively 
   1.move n-1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)  
 2.move disc n from A to C---------1  
 3.move n-1 discs from B to C so they sit on disc n----- T(n-1) 
 So, T(n) = 2T(n-1) +1 
 
11. Which of the following statements are TRUE about an SQL query? 
 P :  An SQL query can contain a HAVING clause even if it does not have a  
       GROUP BY clause 
 Q :  An SQL query can contain a HAVING clause only if it has GROUP BY       
        clause  
 R :  All attributes used in the GROUP BY clause must appear in the SELECT  
        clause 
 S : Not all attributes used in the GROUP BY clause need to appear in the    
       SELECT clause 
 (A) P and R (B) P and S (C) Q and R (D) Q and S 
Answer:-(B) 
Exp:-  If we use a HAVING clause without a GROUP BY clause, the HAVING condition applies to 
all rows that satisfy the search condition. In other words, all rows that satisfy the search 
condition make up a single group. So, option P is true and Q is  false. 
 
 S is also true as an example consider the following table and query. 
Id Name 
1 Ramesh 
 2 Ramesh 
3 Rajesh 
4 Suresh 
 Select count (*) 
 From student 
 Group by Name 
  
 Output will be  
  
Count (*) 
2 
1 
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 4 
1 
12. Given the basic ER and relational models, which of the following is INCORRECT? 
 (A)  An attribute of an entity can have more than one value 
 (B)  An attribute of an entity can be composite  
 (C)  In a row of a relational table, an attribute can have more than one value 
 (D)  In a row of a relational table, an attribute can have exactly one value or a NULL value 
Answer:-(C) 
Exp:-  The term ‘entity’ belongs to ER model and the term ‘relational table’ belongs to relational 
model. 
 Options A and B both are true since ER model supports both multivalued and composite 
attributes. 
 As multivalued attributes are not allowed in relational databases, in a row of a relational 
(table), an attribute cannot have more than one value. 
 
13. What is the complement of the language accepted by the NFA show below? 
 Assume {a} and S= e is the empty string. 
  
 
 
 
 
 
 (A) Ø (B) { } e (C) a * (D) { } a,e 
Answer:- (B) 
Exp:- Language accepted by NFA is a
+
, so complement of this language is {?} 
 
 
14. What is the correct translation of the following statement into mathematical logic? 
 “Some real numbers are rational” 
 (A) ( ) ( ) ( )
x real x v rational x ? (B) ( ) ( ) ( )
x real x rational x ? ? 
 (C) ( ) ( ) ( )
x real x rational x ? ? (D) ( ) ( ) ( )
x rational x real x ? ? 
Answer:- (C) 
Exp:- Option A:  There exists x which is either real or rational and can be both. 
 Option B: All real numbers are rational 
 Option C: There exists a real number which is rational. 
 Option D: There exists some number which is not rational or which is real.  
 
15. Let A be the 2 x 2 matrix with elements a
11
 = a
12
 = a
21
= + 1 and a
22
 =-1. Then the eigen values 
of the matrix A
19
 are 
 (A) 1024 and -1024   (B) 1024 2 and 1024 2 - 
a e
 
e
 
|CS-GATE-2012 PAPER|  

 India’s No.1 institute for GATE Training  
 1 Lakh+ Students trained till date  
 65+ Centers across India 
 5 
 (C) 4 2 and 4 2 -   (D) 512 2 and 512 2 - 
Answer:-(D) 
Exp:- Characteristic equation of A is |A I | 0 where is the eigen value -? = ? 
 
2 2
1 1
0 2 0 2
1 1
-?
= ?? - = ?? =±
- -?
 
 Every matrix satisfies its characteristic equation 
 Therefore 
2 2
A 2I 0 A 2I - = ? = 
 
( ) ( )
9
9
19 18 2
19
A A A A A 2I A 512 A
Hence eigen values of A are 512 2
= × = × = × = ×
±
 
 
16. The protocol data unit (PDU) for the application layer in the Internet stack is 
 (A) Segment (B) Datagram (C) Message (D) Frame 
Answer:-(C) 
Exp:- The PDU for Datalink layer, Network layer , Transport layer and Application layer are frame, 
datagram, segment and message respectively. 
 
17. Consider the function f(x) = sin(x) in the interval [ ] x / 4,7 / 4 ? p p . The number and location 
(s) of the local minima of this function are 
 (A) One, at / 2 p   (B) One, at 3 / 2 p 
 (C) Two, at / 2 p and 3 / 2 p (D) Two, at / 4and3 / 2 p p 
Answer:-(B) 
Exp:- Sin x has a maximum value of 1 at ,
2
p
 and a minimum value of –1 at 
3
2
p
 and at all angles 
conterminal with them. 
 The graph of ( ) f x sin x is = 
 
 
7
In the int erval ,
4 4
p p ? ?
?
? ?
? ?
, it has one local minimum at 
3
x
2
p
= 
18. A process executes the code  
 fork (); 
 fork (); 
 fork (); 
 The total number of child processes created is 
 (A) 3 (B) 4 (C) 7 (D) 8 
Answer:- (C)