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

 Page 1


CS? GATE Paper 2010
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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