Computer Science & Information Technology (CS) 2010 GATE Paper without solution (unsolved) PDF Download

 Page 1


        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Let G=(V, E) be a graph. Define ( )
d
d
? G i d = ×
?
, where i
d
 is the number of 
vertices of degree d in G. If S and T are two different trees with ( ) ( ) ? = ? S T , 
then 
 (A) S 2 T = (B) S T 1 = - (C) S T = (D) S T 1 = + 
 
2. Newton-Raphson method is used to compute a root of the equation 
2
x 13 0 - = 
with 3.5 as the initial value. The approximation after one iteration is 
 (A) 3.575 (B) 3.676 (C) 3.667 (D) 3.607 
 
3. What is the possible number of reflexive relations on a set of 5 elements? 
 (A) 2
10
 (B) 2
15
 (C) 2
20
 (D) 2
25 
 
4. Consider the set S = {1, ?, ?
2
}, where ? and ?
2
 are cube roots of unity. If * 
denotes the multiplication operation, the structure (S, *) forms 
 (A) A group   (B) A ring 
 (C) An integral domain  (D) A field 
 
5. What is the value of 
2n
n
1
lim 1 ?
n
?8
? ?
-
? ?
? ?
 
 (A) 0 (B) e
-2
 (C) e
-1/2
 (D) 1 
 
6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + 
 (A) 
2 4 6 7
m m m m + + +  (B) 
0 1 3 5
m m m m + + + 
 (C) 
0 1 6 7
m m m m + + +   (D) 
2 3 4 5
m m m m + + + 
 
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit 
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The 
time taken for a single refresh operation is 100 nanoseconds. The time required 
to perform one refresh operation on all the cells in the memory unit is 
 (A) 100 nanoseconds   (B) 100*2
10
 nanoseconds 
 (C) 100*2
20
 nanoseconds  (D) 3200*2
20
 nanoseconds 
 
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)
16
. 
The 2’s complement representation of 8*P is 
 (A) ( )
16
C3D8 (B) ( )
16
187B (C) ( )
16
F878 (D) ( )
16
987B 
Page 2


        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Let G=(V, E) be a graph. Define ( )
d
d
? G i d = ×
?
, where i
d
 is the number of 
vertices of degree d in G. If S and T are two different trees with ( ) ( ) ? = ? S T , 
then 
 (A) S 2 T = (B) S T 1 = - (C) S T = (D) S T 1 = + 
 
2. Newton-Raphson method is used to compute a root of the equation 
2
x 13 0 - = 
with 3.5 as the initial value. The approximation after one iteration is 
 (A) 3.575 (B) 3.676 (C) 3.667 (D) 3.607 
 
3. What is the possible number of reflexive relations on a set of 5 elements? 
 (A) 2
10
 (B) 2
15
 (C) 2
20
 (D) 2
25 
 
4. Consider the set S = {1, ?, ?
2
}, where ? and ?
2
 are cube roots of unity. If * 
denotes the multiplication operation, the structure (S, *) forms 
 (A) A group   (B) A ring 
 (C) An integral domain  (D) A field 
 
5. What is the value of 
2n
n
1
lim 1 ?
n
?8
? ?
-
? ?
? ?
 
 (A) 0 (B) e
-2
 (C) e
-1/2
 (D) 1 
 
6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + 
 (A) 
2 4 6 7
m m m m + + +  (B) 
0 1 3 5
m m m m + + + 
 (C) 
0 1 6 7
m m m m + + +   (D) 
2 3 4 5
m m m m + + + 
 
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit 
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The 
time taken for a single refresh operation is 100 nanoseconds. The time required 
to perform one refresh operation on all the cells in the memory unit is 
 (A) 100 nanoseconds   (B) 100*2
10
 nanoseconds 
 (C) 100*2
20
 nanoseconds  (D) 3200*2
20
 nanoseconds 
 
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)
16
. 
The 2’s complement representation of 8*P is 
 (A) ( )
16
C3D8 (B) ( )
16
187B (C) ( )
16
F878 (D) ( )
16
987B 
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
2 
9. The Boolean expression for the output f of the multiplexer shown below is 
 
 (A) P Q R ? ? 
 
 (B) P Q R ? ? 
 
 (C) P Q R + + 
 
 (D) P Q R + + 
 
10. In a binary tree with n nodes, every node has an odd number of descendants. 
Every node is considered to be its own descendant. What is the number of nodes 
in the tree that have exactly one child? 
 (A) 0 (B) 1 (C) ( ) n 1 /2 - (D) n-1 
 
11. What does the following program print? 
 
( )
( )
#include stdio.h
void f int *p, int * g {
p q;
*p 2;
}
int i 0, j 1;
int main ( ){
f(&i, & j);
print f "%d %d \ n", i, j ;
return 0;
}
< >
=
=
= = 
 (A) 2 2 (B) 2 1 (C) 0 1 (D) 0 2 
 
12. Two alternative packages A and B are available for processing a database having 
10
k
 records. Package A requires 0.0001n
2
 time units and package B requires 
10nlog
10
n time units to process n records. What is the smallest value of k for 
which package B will be preferred over A? 
 (A) 12 (B) 10 (C) 6 (D) 5 
 
13. Which data structure in a compiler is used for managing information about 
variables and their attributes? 
 (A) Abstract syntax tree  (B) Symbol table 
 (C) Semantic stack   (D) Parse table 
f
P Q
R
R
R
R
Page 3


        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Let G=(V, E) be a graph. Define ( )
d
d
? G i d = ×
?
, where i
d
 is the number of 
vertices of degree d in G. If S and T are two different trees with ( ) ( ) ? = ? S T , 
then 
 (A) S 2 T = (B) S T 1 = - (C) S T = (D) S T 1 = + 
 
2. Newton-Raphson method is used to compute a root of the equation 
2
x 13 0 - = 
with 3.5 as the initial value. The approximation after one iteration is 
 (A) 3.575 (B) 3.676 (C) 3.667 (D) 3.607 
 
3. What is the possible number of reflexive relations on a set of 5 elements? 
 (A) 2
10
 (B) 2
15
 (C) 2
20
 (D) 2
25 
 
4. Consider the set S = {1, ?, ?
2
}, where ? and ?
2
 are cube roots of unity. If * 
denotes the multiplication operation, the structure (S, *) forms 
 (A) A group   (B) A ring 
 (C) An integral domain  (D) A field 
 
5. What is the value of 
2n
n
1
lim 1 ?
n
?8
? ?
-
? ?
? ?
 
 (A) 0 (B) e
-2
 (C) e
-1/2
 (D) 1 
 
6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + 
 (A) 
2 4 6 7
m m m m + + +  (B) 
0 1 3 5
m m m m + + + 
 (C) 
0 1 6 7
m m m m + + +   (D) 
2 3 4 5
m m m m + + + 
 
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit 
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The 
time taken for a single refresh operation is 100 nanoseconds. The time required 
to perform one refresh operation on all the cells in the memory unit is 
 (A) 100 nanoseconds   (B) 100*2
10
 nanoseconds 
 (C) 100*2
20
 nanoseconds  (D) 3200*2
20
 nanoseconds 
 
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)
16
. 
The 2’s complement representation of 8*P is 
 (A) ( )
16
C3D8 (B) ( )
16
187B (C) ( )
16
F878 (D) ( )
16
987B 
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
2 
9. The Boolean expression for the output f of the multiplexer shown below is 
 
 (A) P Q R ? ? 
 
 (B) P Q R ? ? 
 
 (C) P Q R + + 
 
 (D) P Q R + + 
 
10. In a binary tree with n nodes, every node has an odd number of descendants. 
Every node is considered to be its own descendant. What is the number of nodes 
in the tree that have exactly one child? 
 (A) 0 (B) 1 (C) ( ) n 1 /2 - (D) n-1 
 
11. What does the following program print? 
 
( )
( )
#include stdio.h
void f int *p, int * g {
p q;
*p 2;
}
int i 0, j 1;
int main ( ){
f(&i, & j);
print f "%d %d \ n", i, j ;
return 0;
}
< >
=
=
= = 
 (A) 2 2 (B) 2 1 (C) 0 1 (D) 0 2 
 
12. Two alternative packages A and B are available for processing a database having 
10
k
 records. Package A requires 0.0001n
2
 time units and package B requires 
10nlog
10
n time units to process n records. What is the smallest value of k for 
which package B will be preferred over A? 
 (A) 12 (B) 10 (C) 6 (D) 5 
 
13. Which data structure in a compiler is used for managing information about 
variables and their attributes? 
 (A) Abstract syntax tree  (B) Symbol table 
 (C) Semantic stack   (D) Parse table 
f
P Q
R
R
R
R
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
3 
14. Which languages necessarily need heap allocation in the runtime environment? 
 (A) Those that support recursion (B) Those that use dynamic scoping 
 (C) Those that allow dynamic data structures (D) Those that use global variables 
 
15. One of the header fields in an IP datagram is the Time to Live (TTL) field. Which 
of the following statements best explains the need for this field? 
 (A) It can be used to prioritize packets  
 (B) It can be used to reduce delays 
 (C) It can be used to optimize throughput 
 (D) It can be used to prevent packet looping 
 
16. Which one of the following is not a client server application? 
 (A) Internet chat (B) Web browsing (C) E-mail (D) Ping 
 
17. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively 
enumerable but not recursive. Which of the following statements is not 
necessarily true? 
 (A) L2 – L1 is recursively enumerable  
 (B) L1 – L3 is recursively enumerable 
 (C) L2 n L1 is recursively enumerable 
 (D) L2 ? L1 is recursively enumerable 
 
18. Consider a B
+
-tree in which the maximum number of keys in a node is 5. What is 
the minimum number of keys in any non-root node? 
 (A) 1 (B) 2 (C) 3 (D) 4 
 
19. A relational schema for a train reservation database is given below 
 
( )
( )
Passenger pid, pname, age
Reservation pid, cass, tid
 
 
Table :Passenger
pid 'pname Age
0 'Sachin' 65
1 'Rahul' 66
2 'Sourav' 67
3 'Anil' 69
Table :Reservation
pid class tid
0 'AC' 8200
1 'AC' 8201
2 'SC' 8201
5 'AC' 8203
1 'SC' 8204
3 'AC' 8202
 
Page 4


        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Let G=(V, E) be a graph. Define ( )
d
d
? G i d = ×
?
, where i
d
 is the number of 
vertices of degree d in G. If S and T are two different trees with ( ) ( ) ? = ? S T , 
then 
 (A) S 2 T = (B) S T 1 = - (C) S T = (D) S T 1 = + 
 
2. Newton-Raphson method is used to compute a root of the equation 
2
x 13 0 - = 
with 3.5 as the initial value. The approximation after one iteration is 
 (A) 3.575 (B) 3.676 (C) 3.667 (D) 3.607 
 
3. What is the possible number of reflexive relations on a set of 5 elements? 
 (A) 2
10
 (B) 2
15
 (C) 2
20
 (D) 2
25 
 
4. Consider the set S = {1, ?, ?
2
}, where ? and ?
2
 are cube roots of unity. If * 
denotes the multiplication operation, the structure (S, *) forms 
 (A) A group   (B) A ring 
 (C) An integral domain  (D) A field 
 
5. What is the value of 
2n
n
1
lim 1 ?
n
?8
? ?
-
? ?
? ?
 
 (A) 0 (B) e
-2
 (C) e
-1/2
 (D) 1 
 
6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + 
 (A) 
2 4 6 7
m m m m + + +  (B) 
0 1 3 5
m m m m + + + 
 (C) 
0 1 6 7
m m m m + + +   (D) 
2 3 4 5
m m m m + + + 
 
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit 
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The 
time taken for a single refresh operation is 100 nanoseconds. The time required 
to perform one refresh operation on all the cells in the memory unit is 
 (A) 100 nanoseconds   (B) 100*2
10
 nanoseconds 
 (C) 100*2
20
 nanoseconds  (D) 3200*2
20
 nanoseconds 
 
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)
16
. 
The 2’s complement representation of 8*P is 
 (A) ( )
16
C3D8 (B) ( )
16
187B (C) ( )
16
F878 (D) ( )
16
987B 
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
2 
9. The Boolean expression for the output f of the multiplexer shown below is 
 
 (A) P Q R ? ? 
 
 (B) P Q R ? ? 
 
 (C) P Q R + + 
 
 (D) P Q R + + 
 
10. In a binary tree with n nodes, every node has an odd number of descendants. 
Every node is considered to be its own descendant. What is the number of nodes 
in the tree that have exactly one child? 
 (A) 0 (B) 1 (C) ( ) n 1 /2 - (D) n-1 
 
11. What does the following program print? 
 
( )
( )
#include stdio.h
void f int *p, int * g {
p q;
*p 2;
}
int i 0, j 1;
int main ( ){
f(&i, & j);
print f "%d %d \ n", i, j ;
return 0;
}
< >
=
=
= = 
 (A) 2 2 (B) 2 1 (C) 0 1 (D) 0 2 
 
12. Two alternative packages A and B are available for processing a database having 
10
k
 records. Package A requires 0.0001n
2
 time units and package B requires 
10nlog
10
n time units to process n records. What is the smallest value of k for 
which package B will be preferred over A? 
 (A) 12 (B) 10 (C) 6 (D) 5 
 
13. Which data structure in a compiler is used for managing information about 
variables and their attributes? 
 (A) Abstract syntax tree  (B) Symbol table 
 (C) Semantic stack   (D) Parse table 
f
P Q
R
R
R
R
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
3 
14. Which languages necessarily need heap allocation in the runtime environment? 
 (A) Those that support recursion (B) Those that use dynamic scoping 
 (C) Those that allow dynamic data structures (D) Those that use global variables 
 
15. One of the header fields in an IP datagram is the Time to Live (TTL) field. Which 
of the following statements best explains the need for this field? 
 (A) It can be used to prioritize packets  
 (B) It can be used to reduce delays 
 (C) It can be used to optimize throughput 
 (D) It can be used to prevent packet looping 
 
16. Which one of the following is not a client server application? 
 (A) Internet chat (B) Web browsing (C) E-mail (D) Ping 
 
17. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively 
enumerable but not recursive. Which of the following statements is not 
necessarily true? 
 (A) L2 – L1 is recursively enumerable  
 (B) L1 – L3 is recursively enumerable 
 (C) L2 n L1 is recursively enumerable 
 (D) L2 ? L1 is recursively enumerable 
 
18. Consider a B
+
-tree in which the maximum number of keys in a node is 5. What is 
the minimum number of keys in any non-root node? 
 (A) 1 (B) 2 (C) 3 (D) 4 
 
19. A relational schema for a train reservation database is given below 
 
( )
( )
Passenger pid, pname, age
Reservation pid, cass, tid
 
 
Table :Passenger
pid 'pname Age
0 'Sachin' 65
1 'Rahul' 66
2 'Sourav' 67
3 'Anil' 69
Table :Reservation
pid class tid
0 'AC' 8200
1 'AC' 8201
2 'SC' 8201
5 'AC' 8203
1 'SC' 8204
3 'AC' 8202
 
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
4 
 What pids are returned by the following SQL query for the above instance of the 
tables? 
 
SELECT pid
FROM Reservation
WHERE class 'AC' AND
EXISTS (SELECT *
FROM Passenger
WHERE age 65 AND
Passenger.pid Reservation.pid)
=
>
=
 
 (A) 1, 0 (B) 1, 2 (C) 1, 3 (D) 1, 5 
 
20. Which of the following concurrency control protocols ensure both conflict 
serializability and freedom from deadlock? 
 I. 2-phase locking 
 II. Time-stamp ordering 
 (A) I only   (B) II only 
 (C) Both I and II   (D) Neither I nor II 
 
21. The cyclomatic complexity of each of the modules A and B shown below is 
10. What is the cyclomatic complexity of the sequential integration shown on 
the right hand side? 
 
 
 
 
 
 
 
 
 
 (A) 19 (B) 21 (C) 20 (D) 10 
 
22. What is the appropriate pairing of items in the two columns listing various 
activities encountered in a software life cycle? 
 P. Requirements Capture 1. Module Development and Integration 
 Q. Design   2. Domain Analysis 
 R. Implementation   3. Structural and Behavioral Modeling 
 S. Maintenance   4. Performance Tuning 
 (A) P-3, Q-2,R-4,S-1   (B) P-2, Q-3,R-1,S-4 
 (C) P-3, Q-2,R-1,S-4   (D) P-2, Q-3,R-4,S-1 
A B
B
A
Page 5


        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
1 
Q. No. 1 – 25 Carry One Mark Each 
 
1. Let G=(V, E) be a graph. Define ( )
d
d
? G i d = ×
?
, where i
d
 is the number of 
vertices of degree d in G. If S and T are two different trees with ( ) ( ) ? = ? S T , 
then 
 (A) S 2 T = (B) S T 1 = - (C) S T = (D) S T 1 = + 
 
2. Newton-Raphson method is used to compute a root of the equation 
2
x 13 0 - = 
with 3.5 as the initial value. The approximation after one iteration is 
 (A) 3.575 (B) 3.676 (C) 3.667 (D) 3.607 
 
3. What is the possible number of reflexive relations on a set of 5 elements? 
 (A) 2
10
 (B) 2
15
 (C) 2
20
 (D) 2
25 
 
4. Consider the set S = {1, ?, ?
2
}, where ? and ?
2
 are cube roots of unity. If * 
denotes the multiplication operation, the structure (S, *) forms 
 (A) A group   (B) A ring 
 (C) An integral domain  (D) A field 
 
5. What is the value of 
2n
n
1
lim 1 ?
n
?8
? ?
-
? ?
? ?
 
 (A) 0 (B) e
-2
 (C) e
-1/2
 (D) 1 
 
6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + 
 (A) 
2 4 6 7
m m m m + + +  (B) 
0 1 3 5
m m m m + + + 
 (C) 
0 1 6 7
m m m m + + +   (D) 
2 3 4 5
m m m m + + + 
 
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit 
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The 
time taken for a single refresh operation is 100 nanoseconds. The time required 
to perform one refresh operation on all the cells in the memory unit is 
 (A) 100 nanoseconds   (B) 100*2
10
 nanoseconds 
 (C) 100*2
20
 nanoseconds  (D) 3200*2
20
 nanoseconds 
 
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)
16
. 
The 2’s complement representation of 8*P is 
 (A) ( )
16
C3D8 (B) ( )
16
187B (C) ( )
16
F878 (D) ( )
16
987B 
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
2 
9. The Boolean expression for the output f of the multiplexer shown below is 
 
 (A) P Q R ? ? 
 
 (B) P Q R ? ? 
 
 (C) P Q R + + 
 
 (D) P Q R + + 
 
10. In a binary tree with n nodes, every node has an odd number of descendants. 
Every node is considered to be its own descendant. What is the number of nodes 
in the tree that have exactly one child? 
 (A) 0 (B) 1 (C) ( ) n 1 /2 - (D) n-1 
 
11. What does the following program print? 
 
( )
( )
#include stdio.h
void f int *p, int * g {
p q;
*p 2;
}
int i 0, j 1;
int main ( ){
f(&i, & j);
print f "%d %d \ n", i, j ;
return 0;
}
< >
=
=
= = 
 (A) 2 2 (B) 2 1 (C) 0 1 (D) 0 2 
 
12. Two alternative packages A and B are available for processing a database having 
10
k
 records. Package A requires 0.0001n
2
 time units and package B requires 
10nlog
10
n time units to process n records. What is the smallest value of k for 
which package B will be preferred over A? 
 (A) 12 (B) 10 (C) 6 (D) 5 
 
13. Which data structure in a compiler is used for managing information about 
variables and their attributes? 
 (A) Abstract syntax tree  (B) Symbol table 
 (C) Semantic stack   (D) Parse table 
f
P Q
R
R
R
R
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
3 
14. Which languages necessarily need heap allocation in the runtime environment? 
 (A) Those that support recursion (B) Those that use dynamic scoping 
 (C) Those that allow dynamic data structures (D) Those that use global variables 
 
15. One of the header fields in an IP datagram is the Time to Live (TTL) field. Which 
of the following statements best explains the need for this field? 
 (A) It can be used to prioritize packets  
 (B) It can be used to reduce delays 
 (C) It can be used to optimize throughput 
 (D) It can be used to prevent packet looping 
 
16. Which one of the following is not a client server application? 
 (A) Internet chat (B) Web browsing (C) E-mail (D) Ping 
 
17. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively 
enumerable but not recursive. Which of the following statements is not 
necessarily true? 
 (A) L2 – L1 is recursively enumerable  
 (B) L1 – L3 is recursively enumerable 
 (C) L2 n L1 is recursively enumerable 
 (D) L2 ? L1 is recursively enumerable 
 
18. Consider a B
+
-tree in which the maximum number of keys in a node is 5. What is 
the minimum number of keys in any non-root node? 
 (A) 1 (B) 2 (C) 3 (D) 4 
 
19. A relational schema for a train reservation database is given below 
 
( )
( )
Passenger pid, pname, age
Reservation pid, cass, tid
 
 
Table :Passenger
pid 'pname Age
0 'Sachin' 65
1 'Rahul' 66
2 'Sourav' 67
3 'Anil' 69
Table :Reservation
pid class tid
0 'AC' 8200
1 'AC' 8201
2 'SC' 8201
5 'AC' 8203
1 'SC' 8204
3 'AC' 8202
 
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
4 
 What pids are returned by the following SQL query for the above instance of the 
tables? 
 
SELECT pid
FROM Reservation
WHERE class 'AC' AND
EXISTS (SELECT *
FROM Passenger
WHERE age 65 AND
Passenger.pid Reservation.pid)
=
>
=
 
 (A) 1, 0 (B) 1, 2 (C) 1, 3 (D) 1, 5 
 
20. Which of the following concurrency control protocols ensure both conflict 
serializability and freedom from deadlock? 
 I. 2-phase locking 
 II. Time-stamp ordering 
 (A) I only   (B) II only 
 (C) Both I and II   (D) Neither I nor II 
 
21. The cyclomatic complexity of each of the modules A and B shown below is 
10. What is the cyclomatic complexity of the sequential integration shown on 
the right hand side? 
 
 
 
 
 
 
 
 
 
 (A) 19 (B) 21 (C) 20 (D) 10 
 
22. What is the appropriate pairing of items in the two columns listing various 
activities encountered in a software life cycle? 
 P. Requirements Capture 1. Module Development and Integration 
 Q. Design   2. Domain Analysis 
 R. Implementation   3. Structural and Behavioral Modeling 
 S. Maintenance   4. Performance Tuning 
 (A) P-3, Q-2,R-4,S-1   (B) P-2, Q-3,R-1,S-4 
 (C) P-3, Q-2,R-1,S-4   (D) P-2, Q-3,R-4,S-1 
A B
B
A
        CS? GATE Paper 2010       www.gateforum.com  
© All rights reserved by Gateforum Educational Services Pvt. Ltd.  No part of this booklet may be reproduced or utilized in any form without the 
written permission. Discuss this question paper at www.gatementor.com.                                                                 
5 
23. Consider the methods used by processes P1 and P2 for accessing their critical 
sections whenever needed, as given below. The initial values of shared boolean 
variables S1 and S2 are randomly assigned.  
Method used by PI Method used by P2 
while (S1 = = S2) ; 
Critica1 Section 
S1 = S2; 
while (S1 != S2) ; 
Critica1 Section 
S2 = not (S1); 
 Which one of the following statements describes the properties achieved? 
 (A) Mutual exclusion but not progress  
 (B) Progress but not mutual exclusion 
 (C) Neither mutual exclusion nor progress 
 (D) Both mutual exclusion and progress 
 
24. A system uses FIFO policy for page replacement. It has 4 page frames with no 
pages loaded to begin with. The system first accesses 100 distinct pages in some 
order and then accesses the same 100 pages but now in the reverse order. How 
many page faults will occur? 
 (A) 196 (B) 192 (C) 197 (D) 195 
 
25. Which of the following statements are true? 
 I. Shortest remaining time first scheduling may cause starvation 
 II. Preemptive scheduling may cause starvation 
 III. Round robin is better than FCFS in terms of response time 
 (A) I only (B) I and III only (C) II and III only (D) I, II and III 
 
Q. No. 26 – 55 Carry Two Marks Each 
 
26. Consider a company that assembles computers. The probability of a faulty 
assembly of any computer is p. The company therefore subjects each 
computer to a testing process. This testing process gives the correct result for 
any computer with a probability of q. What is the probability of a computer 
being declared faulty? 
 (A) ( )( ) pq 1 p 1 q + - - (B) ( ) 1 q p - (C) ( ) 1 p q - (D) pq 
 
27. What is the probability that divisor of 10
99
 is a multiple of 10
96
? 
 (A) 1/625 (B) 4/625 (C) 12/625 (D) 16/625 
 
28. The degree sequence of a simple graph is the sequence of the degrees of the 
nodes in the graph in decreasing order. Which of the following sequences can not 
be the degree sequence of any graph? 
 I. 7, 6, 5, 4, 4, 3, 2, 1  II. 6, 6, 6, 6, 3, 3, 2, 2