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

 Page 1


CS? ? ? ?GATE Paper 2007
  
Q.1 – Q.20 Carry One Mark Each 
1. Consider the following two statements about the function ( ) : f x x =
P. ( ) f x is continuous for all real values of x
Q. ( ) f x is differentiable for all real values of x
Which of the following is TRUE? 
(A) P is true and Q is false. (B) P is false and Q is true. 
(C) Both P and Q are true. (D) Both P and Q are false. 
2. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) 
2
n and n (C) 
2
n and 0 (D) n and 1
3. What is the maximum number of different Boolean functions involving n Boolean
variables?
(A)
2
n (B) 2
n
 (C) 
2
2
n
(D) 
2
2
n
4. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
5. Consider the DAG with { } 1,2,3,4,5,6 , V = shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6  (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5 
6. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs. 
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs. 
2 5 
1 
3 
4 
6 
Page 2


CS? ? ? ?GATE Paper 2007
  
Q.1 – Q.20 Carry One Mark Each 
1. Consider the following two statements about the function ( ) : f x x =
P. ( ) f x is continuous for all real values of x
Q. ( ) f x is differentiable for all real values of x
Which of the following is TRUE? 
(A) P is true and Q is false. (B) P is false and Q is true. 
(C) Both P and Q are true. (D) Both P and Q are false. 
2. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) 
2
n and n (C) 
2
n and 0 (D) n and 1
3. What is the maximum number of different Boolean functions involving n Boolean
variables?
(A)
2
n (B) 2
n
 (C) 
2
2
n
(D) 
2
2
n
4. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
5. Consider the DAG with { } 1,2,3,4,5,6 , V = shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6  (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5 
6. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs. 
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs. 
2 5 
1 
3 
4 
6 
CS? ? ? ?GATE Paper 2007
7. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.
8. How many 3-to-8 line decoders with an enable input are needed to construct a 6-
to-64 line decoder without using any other logic gates?
(A) 7 (B) 8 (C) 9 (D) 10
9. Consider the following Boolean function of four variables:
( ) ( ) , , , 1,3,4,6,9,11,12,14 f w x y z =
?
The function is: 
(A) independent of one variables. (B) independent of two variables. 
(C) independent of three variables. (D) dependent on all the variables. 
10. Consider a 4-way set associative cache consisting of 128 lines with a line size of
64 words. The CPU generates a 20-bit address of a word in main memory. The
number of bits in the TAG, LINE and WORD fields are respectively:
(A) 9, 6, 5 (B) 7, 7, 6 (C) 7, 5, 8 (D) 9, 5, 6 
11. Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors
per track. 512 bytes of data are stored in a bit serial manner in a sector. The
capacity of the disk pack and the number of bits required to specify a particular
sector in the disk are respectively:
(A) 256 Mbyte, 19 bits (B) 256 Mbyte, 28 bits 
(C) 512 Mbyte, 20 bits (D) 64 Gbyte, 28 bits 
12. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:
(A) 2 1
h
- (B) 
1
2 1
h-
- (C) 
1
2 1
h+
- (D) 
1
2
h+
13. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3
14. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort 
Page 3


CS? ? ? ?GATE Paper 2007
  
Q.1 – Q.20 Carry One Mark Each 
1. Consider the following two statements about the function ( ) : f x x =
P. ( ) f x is continuous for all real values of x
Q. ( ) f x is differentiable for all real values of x
Which of the following is TRUE? 
(A) P is true and Q is false. (B) P is false and Q is true. 
(C) Both P and Q are true. (D) Both P and Q are false. 
2. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) 
2
n and n (C) 
2
n and 0 (D) n and 1
3. What is the maximum number of different Boolean functions involving n Boolean
variables?
(A)
2
n (B) 2
n
 (C) 
2
2
n
(D) 
2
2
n
4. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
5. Consider the DAG with { } 1,2,3,4,5,6 , V = shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6  (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5 
6. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs. 
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs. 
2 5 
1 
3 
4 
6 
CS? ? ? ?GATE Paper 2007
7. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.
8. How many 3-to-8 line decoders with an enable input are needed to construct a 6-
to-64 line decoder without using any other logic gates?
(A) 7 (B) 8 (C) 9 (D) 10
9. Consider the following Boolean function of four variables:
( ) ( ) , , , 1,3,4,6,9,11,12,14 f w x y z =
?
The function is: 
(A) independent of one variables. (B) independent of two variables. 
(C) independent of three variables. (D) dependent on all the variables. 
10. Consider a 4-way set associative cache consisting of 128 lines with a line size of
64 words. The CPU generates a 20-bit address of a word in main memory. The
number of bits in the TAG, LINE and WORD fields are respectively:
(A) 9, 6, 5 (B) 7, 7, 6 (C) 7, 5, 8 (D) 9, 5, 6 
11. Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors
per track. 512 bytes of data are stored in a bit serial manner in a sector. The
capacity of the disk pack and the number of bits required to specify a particular
sector in the disk are respectively:
(A) 256 Mbyte, 19 bits (B) 256 Mbyte, 28 bits 
(C) 512 Mbyte, 20 bits (D) 64 Gbyte, 28 bits 
12. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:
(A) 2 1
h
- (B) 
1
2 1
h-
- (C) 
1
2 1
h+
- (D) 
1
2
h+
13. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3
14. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort 
CS? ? ? ?GATE Paper 2007
15. Consider the following segment of C-code:
int j, n; 
 j = 1; 
 while (j <=n) 
  j = j*2; 
The number of comparisons made in the execution of the loop for any n > 0 is: 
(A) 
2
log 1 n + ? ?
? ?
(B) n (C) 
2
log n ? ?
? ?
(D) 
2
log 1 n + ? ?
? ?
16. Group 1 contains some CPU scheduling algorithms and Group 2 contains some
applications. Match entries in Group 1 to entries in Group 2.
(A) P  -  3  Q  -  2    R  -  1 (B) P  -  1  Q  -  2    R  -  3 
(C) P  -  2  Q  -  3    R  -  1 (D) P  -  1  Q  -  3    R  -  2 
17. Consider the following statements about user level threads and kernel level
threads. Which one of the following statements is FALSE?
(A) Context switch time is longer for kernel level threads than for user level
threads.  
(B) User level threads do not need any hardware support.  
(C) Related kernel level threads can be scheduled on different processors in a 
multi-processor system.  
(D) Blocking one kernel level thread blocks all related threads. 
18. Which one of the following is a top-down parser?
(A) Recursive descent parser. (B) Operator precedence parser. 
(C) An LR(k) parser. (D) An LALR(k) parser. 
19. In Ethernet when Manchester encoding is used, the bit rate is:
(A) Half the baud rate. (B) Twice the baud rate. 
(C) Same as the baud rate. (D) None of the above 
20. Which one of the following uses UDP as the transport protocol?
(A) HTTP (B) Telnet (C) DNS (D) SMTP 
Group I Group II 
(P) Gang Scheduling (1) Guaranteed Scheduling 
(Q) Rate Monotonic Scheduling  (2) Real-time Scheduling 
(R) Fair Share Scheduling  (3) Thread Scheduling  
Page 4


CS? ? ? ?GATE Paper 2007
  
Q.1 – Q.20 Carry One Mark Each 
1. Consider the following two statements about the function ( ) : f x x =
P. ( ) f x is continuous for all real values of x
Q. ( ) f x is differentiable for all real values of x
Which of the following is TRUE? 
(A) P is true and Q is false. (B) P is false and Q is true. 
(C) Both P and Q are true. (D) Both P and Q are false. 
2. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) 
2
n and n (C) 
2
n and 0 (D) n and 1
3. What is the maximum number of different Boolean functions involving n Boolean
variables?
(A)
2
n (B) 2
n
 (C) 
2
2
n
(D) 
2
2
n
4. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
5. Consider the DAG with { } 1,2,3,4,5,6 , V = shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6  (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5 
6. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs. 
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs. 
2 5 
1 
3 
4 
6 
CS? ? ? ?GATE Paper 2007
7. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.
8. How many 3-to-8 line decoders with an enable input are needed to construct a 6-
to-64 line decoder without using any other logic gates?
(A) 7 (B) 8 (C) 9 (D) 10
9. Consider the following Boolean function of four variables:
( ) ( ) , , , 1,3,4,6,9,11,12,14 f w x y z =
?
The function is: 
(A) independent of one variables. (B) independent of two variables. 
(C) independent of three variables. (D) dependent on all the variables. 
10. Consider a 4-way set associative cache consisting of 128 lines with a line size of
64 words. The CPU generates a 20-bit address of a word in main memory. The
number of bits in the TAG, LINE and WORD fields are respectively:
(A) 9, 6, 5 (B) 7, 7, 6 (C) 7, 5, 8 (D) 9, 5, 6 
11. Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors
per track. 512 bytes of data are stored in a bit serial manner in a sector. The
capacity of the disk pack and the number of bits required to specify a particular
sector in the disk are respectively:
(A) 256 Mbyte, 19 bits (B) 256 Mbyte, 28 bits 
(C) 512 Mbyte, 20 bits (D) 64 Gbyte, 28 bits 
12. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:
(A) 2 1
h
- (B) 
1
2 1
h-
- (C) 
1
2 1
h+
- (D) 
1
2
h+
13. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3
14. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort 
CS? ? ? ?GATE Paper 2007
15. Consider the following segment of C-code:
int j, n; 
 j = 1; 
 while (j <=n) 
  j = j*2; 
The number of comparisons made in the execution of the loop for any n > 0 is: 
(A) 
2
log 1 n + ? ?
? ?
(B) n (C) 
2
log n ? ?
? ?
(D) 
2
log 1 n + ? ?
? ?
16. Group 1 contains some CPU scheduling algorithms and Group 2 contains some
applications. Match entries in Group 1 to entries in Group 2.
(A) P  -  3  Q  -  2    R  -  1 (B) P  -  1  Q  -  2    R  -  3 
(C) P  -  2  Q  -  3    R  -  1 (D) P  -  1  Q  -  3    R  -  2 
17. Consider the following statements about user level threads and kernel level
threads. Which one of the following statements is FALSE?
(A) Context switch time is longer for kernel level threads than for user level
threads.  
(B) User level threads do not need any hardware support.  
(C) Related kernel level threads can be scheduled on different processors in a 
multi-processor system.  
(D) Blocking one kernel level thread blocks all related threads. 
18. Which one of the following is a top-down parser?
(A) Recursive descent parser. (B) Operator precedence parser. 
(C) An LR(k) parser. (D) An LALR(k) parser. 
19. In Ethernet when Manchester encoding is used, the bit rate is:
(A) Half the baud rate. (B) Twice the baud rate. 
(C) Same as the baud rate. (D) None of the above 
20. Which one of the following uses UDP as the transport protocol?
(A) HTTP (B) Telnet (C) DNS (D) SMTP 
Group I Group II 
(P) Gang Scheduling (1) Guaranteed Scheduling 
(Q) Rate Monotonic Scheduling  (2) Real-time Scheduling 
(R) Fair Share Scheduling  (3) Thread Scheduling  
CS? ? ? ?GATE Paper 2007
Q.21 – Q.75 Carry Two Marks Each 
21. How many different non-isomorphic Abelian groups of order 4 are there?
(A) 2 (B) 3 (C) 4 (D) 5
22. Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be
a predicate which denotes that x is connected. Which of the following first order
logic sentences DOES NOT represent the statement: “Not every graph is
connected”?
(A) ( ) ( ) ( )
x Graph x Connected x ¬? ? (B) ( ) ( ) ( )
x Graph x Connected x ? ?¬
(C) ( ) ( ) ( )
x Graph x Connected x ¬? ¬ ? (D) ( ) ( ) ( )
x Graph x Connected x ? ? ¬
23. Which of the following graphs has an Eulerian circuit?
(A) Any k-regular graph where k is an even number.
(B) A complete graph on 90 vertices.
(C) The complement of a cycle on 25 vertices.
(D) None of the above
24. Suppose we uniformly and randomly select a permutation from the 20!
Permutations of 1, 2,3 ,…..,20. What is the probability that 2 appears at an
earlier position than any other even number in the selected permutation?
(A) 
1
2
(B) 
1
10
(C) 
9!
20!
(D) None of these 
25. Let A be a 4 × 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an
eigenvalue of ,
A I
I A
? ?
? ?
? ?
where I is the 4 × 4 identity matrix?
(A) -5 (B) -7 (C) 2 (D) 1 
26. Consider the set { } , , , . S a b c d = Consider the following 4 partitions 
1 2 3 4
, , , p p p p on
{ } { } { } { } 1 2 3 4
: , , , , , , , , . S abcd ab cd abc d a b c d p p p p = = = = Let p be the partial
order on the set of partitions { }
1 2 3 4
, , , S p p p p ' = defined as follows:
i j
p p p if and
only if 
i
p refines .
j
p The poset diagram for ( ) , S' p is: 
(A) (B) 
1
p 
2
p
3
p
4
p 
1
p 
2
p
3
p
4
p 
Page 5


CS? ? ? ?GATE Paper 2007
  
Q.1 – Q.20 Carry One Mark Each 
1. Consider the following two statements about the function ( ) : f x x =
P. ( ) f x is continuous for all real values of x
Q. ( ) f x is differentiable for all real values of x
Which of the following is TRUE? 
(A) P is true and Q is false. (B) P is false and Q is true. 
(C) Both P and Q are true. (D) Both P and Q are false. 
2. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) 
2
n and n (C) 
2
n and 0 (D) n and 1
3. What is the maximum number of different Boolean functions involving n Boolean
variables?
(A)
2
n (B) 2
n
 (C) 
2
2
n
(D) 
2
2
n
4. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
5. Consider the DAG with { } 1,2,3,4,5,6 , V = shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6  (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5 
6. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs. 
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs. 
2 5 
1 
3 
4 
6 
CS? ? ? ?GATE Paper 2007
7. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.
8. How many 3-to-8 line decoders with an enable input are needed to construct a 6-
to-64 line decoder without using any other logic gates?
(A) 7 (B) 8 (C) 9 (D) 10
9. Consider the following Boolean function of four variables:
( ) ( ) , , , 1,3,4,6,9,11,12,14 f w x y z =
?
The function is: 
(A) independent of one variables. (B) independent of two variables. 
(C) independent of three variables. (D) dependent on all the variables. 
10. Consider a 4-way set associative cache consisting of 128 lines with a line size of
64 words. The CPU generates a 20-bit address of a word in main memory. The
number of bits in the TAG, LINE and WORD fields are respectively:
(A) 9, 6, 5 (B) 7, 7, 6 (C) 7, 5, 8 (D) 9, 5, 6 
11. Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors
per track. 512 bytes of data are stored in a bit serial manner in a sector. The
capacity of the disk pack and the number of bits required to specify a particular
sector in the disk are respectively:
(A) 256 Mbyte, 19 bits (B) 256 Mbyte, 28 bits 
(C) 512 Mbyte, 20 bits (D) 64 Gbyte, 28 bits 
12. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:
(A) 2 1
h
- (B) 
1
2 1
h-
- (C) 
1
2 1
h+
- (D) 
1
2
h+
13. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3
14. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort 
CS? ? ? ?GATE Paper 2007
15. Consider the following segment of C-code:
int j, n; 
 j = 1; 
 while (j <=n) 
  j = j*2; 
The number of comparisons made in the execution of the loop for any n > 0 is: 
(A) 
2
log 1 n + ? ?
? ?
(B) n (C) 
2
log n ? ?
? ?
(D) 
2
log 1 n + ? ?
? ?
16. Group 1 contains some CPU scheduling algorithms and Group 2 contains some
applications. Match entries in Group 1 to entries in Group 2.
(A) P  -  3  Q  -  2    R  -  1 (B) P  -  1  Q  -  2    R  -  3 
(C) P  -  2  Q  -  3    R  -  1 (D) P  -  1  Q  -  3    R  -  2 
17. Consider the following statements about user level threads and kernel level
threads. Which one of the following statements is FALSE?
(A) Context switch time is longer for kernel level threads than for user level
threads.  
(B) User level threads do not need any hardware support.  
(C) Related kernel level threads can be scheduled on different processors in a 
multi-processor system.  
(D) Blocking one kernel level thread blocks all related threads. 
18. Which one of the following is a top-down parser?
(A) Recursive descent parser. (B) Operator precedence parser. 
(C) An LR(k) parser. (D) An LALR(k) parser. 
19. In Ethernet when Manchester encoding is used, the bit rate is:
(A) Half the baud rate. (B) Twice the baud rate. 
(C) Same as the baud rate. (D) None of the above 
20. Which one of the following uses UDP as the transport protocol?
(A) HTTP (B) Telnet (C) DNS (D) SMTP 
Group I Group II 
(P) Gang Scheduling (1) Guaranteed Scheduling 
(Q) Rate Monotonic Scheduling  (2) Real-time Scheduling 
(R) Fair Share Scheduling  (3) Thread Scheduling  
CS? ? ? ?GATE Paper 2007
Q.21 – Q.75 Carry Two Marks Each 
21. How many different non-isomorphic Abelian groups of order 4 are there?
(A) 2 (B) 3 (C) 4 (D) 5
22. Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be
a predicate which denotes that x is connected. Which of the following first order
logic sentences DOES NOT represent the statement: “Not every graph is
connected”?
(A) ( ) ( ) ( )
x Graph x Connected x ¬? ? (B) ( ) ( ) ( )
x Graph x Connected x ? ?¬
(C) ( ) ( ) ( )
x Graph x Connected x ¬? ¬ ? (D) ( ) ( ) ( )
x Graph x Connected x ? ? ¬
23. Which of the following graphs has an Eulerian circuit?
(A) Any k-regular graph where k is an even number.
(B) A complete graph on 90 vertices.
(C) The complement of a cycle on 25 vertices.
(D) None of the above
24. Suppose we uniformly and randomly select a permutation from the 20!
Permutations of 1, 2,3 ,…..,20. What is the probability that 2 appears at an
earlier position than any other even number in the selected permutation?
(A) 
1
2
(B) 
1
10
(C) 
9!
20!
(D) None of these 
25. Let A be a 4 × 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an
eigenvalue of ,
A I
I A
? ?
? ?
? ?
where I is the 4 × 4 identity matrix?
(A) -5 (B) -7 (C) 2 (D) 1 
26. Consider the set { } , , , . S a b c d = Consider the following 4 partitions 
1 2 3 4
, , , p p p p on
{ } { } { } { } 1 2 3 4
: , , , , , , , , . S abcd ab cd abc d a b c d p p p p = = = = Let p be the partial
order on the set of partitions { }
1 2 3 4
, , , S p p p p ' = defined as follows:
i j
p p p if and
only if 
i
p refines .
j
p The poset diagram for ( ) , S' p is: 
(A) (B) 
1
p 
2
p
3
p
4
p 
1
p 
2
p
3
p
4
p 
CS? ? ? ?GATE Paper 2007
(C) (D) 
27. Consider the set of (column) vectors defined by
{ }
3
1 2 3 1 2 3
0, where , , .
T
T
X x R x x x x x x x = ? + + = = ? ?
? ?
 Which of the following is 
TRUE?
(A)
{ }
1, 1,0 , 1,0, 1
T T
- - ? ? ? ?
? ? ? ?
is a basis for the subspace X.
(B) 
{ }
1, 1,0 , 1,0, 1
T T
- - ? ? ? ?
? ? ? ?
is a linearly independent set, but it does not span X and
therefore is not a basis of X. 
(C) X is not a subspace of 
3
R
(D) None of the above  
28. Consider the series
1 0
9
, 0.5
2 8
n
n
n
x
x x
x
+
= + = obtained from the Newton-Raphson 
method. The series converges to 
(A) 1.5 (B) 2 (C) 1.6 (D) 1.4 
29. A minimum state deterministic finite automaton accepting the language
{ }
{ }
*
0,1 , number of 0s and 1s in  are divisible by 3 and 5, respectively L w w w = ?
has
(A) 15 states (B) 11 states (C) 10 states (D) 9 states 
30. The language
{ }
0 21 0
i i
L i = = over the alphabet { } 0,1,2 is:
(A) not recursive 
(B) is recursive and is a deterministic CFL. 
(C) is a regular language.  
(D) is not a deterministic CFL but a CFL. 
1
p 
2
p
4
p 
3
p
3
p
2
p
1
p 
4
p