Gate (CS) 2009 Paper without Solution

# Gate (CS) 2009 Paper without Solution - GATE Computer Science Engineering(CSE) 2024 Mock Test Series - Computer Science Engineering (CSE)

``` Page 1

CS? GATE Paper 2009
Q. No. 1 – 20 Carry One Mark Each
1. Which one of the following in NOT necessarily a property of a Group?
(A) Commutativity   (B) Associativity
(C) Existence of inverse for every element (D) Existence of identity
2. What is the chromatic number of an n-vertex simple connected graph which does
not contain any odd length cycle? Assume n= 2.
(A) 2  (B) 3 (C) n-1 (D) n
3. Which one of the following is TRUE for any simple connected undirected graph
with more than 2 vertices?
(A)  No two vertices have the same degree.
(B)  At least two vertices have the same degree.
(C)  At least three vertices have the same degree.
(D)  All vertices have the same degree.
4. Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
Which one of the following is TRUE?
(A)  R is symmetric but NOT antisymmetric
(B)  R is NOT symmetric but antisymmetric
(C)  R is both symmetric and antisymmetric
(D)  R is neither symmetric nor antisymmetric
5. (1217)
8
is equivalent to
(A) (1217)
16
(B) (028F)
16
(C) (2297)
10
(D) (0B17)
16

6. What is the minimum number of gates required to implement the Boolean
function (AB+C) if we have to use only 2-input NOR gates?
(A) 2 (B) 3 (C) 4 (D) 5
7. How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-
bytes?
(A) 8  (B) 32 (C) 64 (D) 128
8. A CPU generally handles an interrupt by executing an interrupt service routine
(A)  As soon as an interrupt is raised
(B)  By checking the interrupt register at the end of fetch cycle.
(C)  By checking the interrupt register after finishing the execution of the current
instruction.
(D)  By checking the interrupt register at fixed time intervals.
Page 2

CS? GATE Paper 2009
Q. No. 1 – 20 Carry One Mark Each
1. Which one of the following in NOT necessarily a property of a Group?
(A) Commutativity   (B) Associativity
(C) Existence of inverse for every element (D) Existence of identity
2. What is the chromatic number of an n-vertex simple connected graph which does
not contain any odd length cycle? Assume n= 2.
(A) 2  (B) 3 (C) n-1 (D) n
3. Which one of the following is TRUE for any simple connected undirected graph
with more than 2 vertices?
(A)  No two vertices have the same degree.
(B)  At least two vertices have the same degree.
(C)  At least three vertices have the same degree.
(D)  All vertices have the same degree.
4. Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
Which one of the following is TRUE?
(A)  R is symmetric but NOT antisymmetric
(B)  R is NOT symmetric but antisymmetric
(C)  R is both symmetric and antisymmetric
(D)  R is neither symmetric nor antisymmetric
5. (1217)
8
is equivalent to
(A) (1217)
16
(B) (028F)
16
(C) (2297)
10
(D) (0B17)
16

6. What is the minimum number of gates required to implement the Boolean
function (AB+C) if we have to use only 2-input NOR gates?
(A) 2 (B) 3 (C) 4 (D) 5
7. How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-
bytes?
(A) 8  (B) 32 (C) 64 (D) 128
8. A CPU generally handles an interrupt by executing an interrupt service routine
(A)  As soon as an interrupt is raised
(B)  By checking the interrupt register at the end of fetch cycle.
(C)  By checking the interrupt register after finishing the execution of the current
instruction.
(D)  By checking the interrupt register at fixed time intervals.
CS? GATE Paper 2009
9. In which one of the following page replacement policies, Belady’s anomaly may
occur?
(A) FIFO (B) Optimal (C) LRU (D) MRU
10. The essential content(s) in each entry of a page table is / are
(A) Virtual page number
(B) Page frame number
(C) Both virtual page number and page frame number
(D) Access right information
11. What is the number of swaps required to sort n elements using selection sort, in
the worst case?
(A) (n) ? (B) (n log n) ? (C)
2
(n ) ? (D)
2
(n log n) ?
12. S aSa bSb a b ? ;The language generated by the above grammar over the
alphabet {a,b} is the set of
(A) All palindromes.
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes.
13. Which of the following statement(s) is / are correct regarding Bellman-Ford
shortest path algorithm?
P.  Always finds a negative weighted cycle, if one exists.
Q.  Finds whether any negative weighted cycle is reachable from the source.
(A)  P only   (B)  Q only
(C)  both P and Q   (D)  Neither P nor Q
14. Let
A
p be a problem that belongs to the class NP. Then which one of the
following is TRUE?
(A) There is no polynomial time algorithm for
A
p .
(B) If
A
p can be solved deterministically in polynomial time, then P = NP.
(C) If
A
p is NP-hard, then it is NP-complete.
(D)
A
p may be undecidable.
15. Which one of the following languages over the alphabet {0,1} is described by the
regular expression: (0+1)*0(0+1)*0(0+1)*?
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.
Page 3

CS? GATE Paper 2009
Q. No. 1 – 20 Carry One Mark Each
1. Which one of the following in NOT necessarily a property of a Group?
(A) Commutativity   (B) Associativity
(C) Existence of inverse for every element (D) Existence of identity
2. What is the chromatic number of an n-vertex simple connected graph which does
not contain any odd length cycle? Assume n= 2.
(A) 2  (B) 3 (C) n-1 (D) n
3. Which one of the following is TRUE for any simple connected undirected graph
with more than 2 vertices?
(A)  No two vertices have the same degree.
(B)  At least two vertices have the same degree.
(C)  At least three vertices have the same degree.
(D)  All vertices have the same degree.
4. Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
Which one of the following is TRUE?
(A)  R is symmetric but NOT antisymmetric
(B)  R is NOT symmetric but antisymmetric
(C)  R is both symmetric and antisymmetric
(D)  R is neither symmetric nor antisymmetric
5. (1217)
8
is equivalent to
(A) (1217)
16
(B) (028F)
16
(C) (2297)
10
(D) (0B17)
16

6. What is the minimum number of gates required to implement the Boolean
function (AB+C) if we have to use only 2-input NOR gates?
(A) 2 (B) 3 (C) 4 (D) 5
7. How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-
bytes?
(A) 8  (B) 32 (C) 64 (D) 128
8. A CPU generally handles an interrupt by executing an interrupt service routine
(A)  As soon as an interrupt is raised
(B)  By checking the interrupt register at the end of fetch cycle.
(C)  By checking the interrupt register after finishing the execution of the current
instruction.
(D)  By checking the interrupt register at fixed time intervals.
CS? GATE Paper 2009
9. In which one of the following page replacement policies, Belady’s anomaly may
occur?
(A) FIFO (B) Optimal (C) LRU (D) MRU
10. The essential content(s) in each entry of a page table is / are
(A) Virtual page number
(B) Page frame number
(C) Both virtual page number and page frame number
(D) Access right information
11. What is the number of swaps required to sort n elements using selection sort, in
the worst case?
(A) (n) ? (B) (n log n) ? (C)
2
(n ) ? (D)
2
(n log n) ?
12. S aSa bSb a b ? ;The language generated by the above grammar over the
alphabet {a,b} is the set of
(A) All palindromes.
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes.
13. Which of the following statement(s) is / are correct regarding Bellman-Ford
shortest path algorithm?
P.  Always finds a negative weighted cycle, if one exists.
Q.  Finds whether any negative weighted cycle is reachable from the source.
(A)  P only   (B)  Q only
(C)  both P and Q   (D)  Neither P nor Q
14. Let
A
p be a problem that belongs to the class NP. Then which one of the
following is TRUE?
(A) There is no polynomial time algorithm for
A
p .
(B) If
A
p can be solved deterministically in polynomial time, then P = NP.
(C) If
A
p is NP-hard, then it is NP-complete.
(D)
A
p may be undecidable.
15. Which one of the following languages over the alphabet {0,1} is described by the
regular expression: (0+1)*0(0+1)*0(0+1)*?
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.
CS? GATE Paper 2009
16. Which one of the following is FALSE?
(A) There is unique minimal DFA for every regular language
(B) Every NFA can be converted to an equivalent PDA.
(C) Complement of every context-free language is recursive.
(D) Every nondeterministic PDA can be converted to an equivalent deterministic
PDA.
17. Match all items in Group 1 with correct options from those given in Group 2.
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
(A) P-4. Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4, S-3
18. Consider the program below:
# include < stdio.h >
int fun(int n, int * f_p) {
int t, f;
if (n <= 1) {
*f_p = 1;
return 1;
}
t = fun (n-1, f_p);
f = t+*f_p;
*f_p = t;
return f;
}
int main() {
int x = 15;
printf ("%d\ n", fun(5,& x));
return 0;
}
The value printed is
(A) 6  (B) 8 (C) 14 (D) 15
19. The coupling between different modules of a software is categorized as follows:
I.  Content coupling II. Common coupling
III. Control coupling IV Stamp coupling
V. Data coupling
Coupling between modules can be ranked in the order of strongest (least
desirable) to weakest (most desirable) as follows:
(A) I-II-III-IV-V (B) V-IV-III-II-I (C) I-III-V -II-IV (D) IV-II-V -III-I
Page 4

CS? GATE Paper 2009
Q. No. 1 – 20 Carry One Mark Each
1. Which one of the following in NOT necessarily a property of a Group?
(A) Commutativity   (B) Associativity
(C) Existence of inverse for every element (D) Existence of identity
2. What is the chromatic number of an n-vertex simple connected graph which does
not contain any odd length cycle? Assume n= 2.
(A) 2  (B) 3 (C) n-1 (D) n
3. Which one of the following is TRUE for any simple connected undirected graph
with more than 2 vertices?
(A)  No two vertices have the same degree.
(B)  At least two vertices have the same degree.
(C)  At least three vertices have the same degree.
(D)  All vertices have the same degree.
4. Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
Which one of the following is TRUE?
(A)  R is symmetric but NOT antisymmetric
(B)  R is NOT symmetric but antisymmetric
(C)  R is both symmetric and antisymmetric
(D)  R is neither symmetric nor antisymmetric
5. (1217)
8
is equivalent to
(A) (1217)
16
(B) (028F)
16
(C) (2297)
10
(D) (0B17)
16

6. What is the minimum number of gates required to implement the Boolean
function (AB+C) if we have to use only 2-input NOR gates?
(A) 2 (B) 3 (C) 4 (D) 5
7. How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-
bytes?
(A) 8  (B) 32 (C) 64 (D) 128
8. A CPU generally handles an interrupt by executing an interrupt service routine
(A)  As soon as an interrupt is raised
(B)  By checking the interrupt register at the end of fetch cycle.
(C)  By checking the interrupt register after finishing the execution of the current
instruction.
(D)  By checking the interrupt register at fixed time intervals.
CS? GATE Paper 2009
9. In which one of the following page replacement policies, Belady’s anomaly may
occur?
(A) FIFO (B) Optimal (C) LRU (D) MRU
10. The essential content(s) in each entry of a page table is / are
(A) Virtual page number
(B) Page frame number
(C) Both virtual page number and page frame number
(D) Access right information
11. What is the number of swaps required to sort n elements using selection sort, in
the worst case?
(A) (n) ? (B) (n log n) ? (C)
2
(n ) ? (D)
2
(n log n) ?
12. S aSa bSb a b ? ;The language generated by the above grammar over the
alphabet {a,b} is the set of
(A) All palindromes.
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes.
13. Which of the following statement(s) is / are correct regarding Bellman-Ford
shortest path algorithm?
P.  Always finds a negative weighted cycle, if one exists.
Q.  Finds whether any negative weighted cycle is reachable from the source.
(A)  P only   (B)  Q only
(C)  both P and Q   (D)  Neither P nor Q
14. Let
A
p be a problem that belongs to the class NP. Then which one of the
following is TRUE?
(A) There is no polynomial time algorithm for
A
p .
(B) If
A
p can be solved deterministically in polynomial time, then P = NP.
(C) If
A
p is NP-hard, then it is NP-complete.
(D)
A
p may be undecidable.
15. Which one of the following languages over the alphabet {0,1} is described by the
regular expression: (0+1)*0(0+1)*0(0+1)*?
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.
CS? GATE Paper 2009
16. Which one of the following is FALSE?
(A) There is unique minimal DFA for every regular language
(B) Every NFA can be converted to an equivalent PDA.
(C) Complement of every context-free language is recursive.
(D) Every nondeterministic PDA can be converted to an equivalent deterministic
PDA.
17. Match all items in Group 1 with correct options from those given in Group 2.
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
(A) P-4. Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4, S-3
18. Consider the program below:
# include < stdio.h >
int fun(int n, int * f_p) {
int t, f;
if (n <= 1) {
*f_p = 1;
return 1;
}
t = fun (n-1, f_p);
f = t+*f_p;
*f_p = t;
return f;
}
int main() {
int x = 15;
printf ("%d\ n", fun(5,& x));
return 0;
}
The value printed is
(A) 6  (B) 8 (C) 14 (D) 15
19. The coupling between different modules of a software is categorized as follows:
I.  Content coupling II. Common coupling
III. Control coupling IV Stamp coupling
V. Data coupling
Coupling between modules can be ranked in the order of strongest (least
desirable) to weakest (most desirable) as follows:
(A) I-II-III-IV-V (B) V-IV-III-II-I (C) I-III-V -II-IV (D) IV-II-V -III-I
CS? GATE Paper 2009
20. Consider the HTML table definition given below:
table border=1>
<tr> <td rowspan=2> ab </td>
<td colspan=2> cd </td>
</tr>
<tr> <td> ef </td>
<td rowspan=2> gh </td>
</tr>
<tr> <td colspan=2> ik </td>
</tr>
</table>
<
The number of rows in each column and the number of columns in each row are:
(A) 2,2,3 and 2,3,2 (B) 2,2,3 and 2,2,3
(C) 2,3,2 and 2,3,2 (D) 2,3,2 and 2,2,3
Q. No. 21 – 56 Carry Two Marks Each
21. An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The
probability that the face value is odd is 90% of the probability that the face value
is even. The probability of getting any even numbered face is the same.
If the probability that the face is even given that it is greater than 3 is 0.75,
which one of the following options is closest to the probability that the face value
exceeds 3?
(A) 0.453 (B) 0.468 (C) 0.485 (D) 0.492
22. For the composition table of a cyclic group shown below
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
Which one of the following choices is correct?
(A) a, b are generators (B) b, c are generators
(C) c, d are generators (D) d, a are generators
23. Which one of the following is the most appropriate logical formula to represent
the statement? “Gold and silver ornaments are precious”.
The following notations are used:
G(x): x is a gold ornament
S(x): x is a silver ornament
P(x): x is precious
(A) ( ) ( ) ( ) ( ) ( )
x P x G x S x ? ? ? (B) ( ) ( ) ( ) ( )
( )
x G x S x P x ? ? ?
(C) ( ) ( ) ( ) ( )
( )
x G x S x P x ? ? ? (D) ( ) ( ) ( ) ( )
( )
x G x S x P x ? ? ?
Page 5

CS? GATE Paper 2009
Q. No. 1 – 20 Carry One Mark Each
1. Which one of the following in NOT necessarily a property of a Group?
(A) Commutativity   (B) Associativity
(C) Existence of inverse for every element (D) Existence of identity
2. What is the chromatic number of an n-vertex simple connected graph which does
not contain any odd length cycle? Assume n= 2.
(A) 2  (B) 3 (C) n-1 (D) n
3. Which one of the following is TRUE for any simple connected undirected graph
with more than 2 vertices?
(A)  No two vertices have the same degree.
(B)  At least two vertices have the same degree.
(C)  At least three vertices have the same degree.
(D)  All vertices have the same degree.
4. Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
Which one of the following is TRUE?
(A)  R is symmetric but NOT antisymmetric
(B)  R is NOT symmetric but antisymmetric
(C)  R is both symmetric and antisymmetric
(D)  R is neither symmetric nor antisymmetric
5. (1217)
8
is equivalent to
(A) (1217)
16
(B) (028F)
16
(C) (2297)
10
(D) (0B17)
16

6. What is the minimum number of gates required to implement the Boolean
function (AB+C) if we have to use only 2-input NOR gates?
(A) 2 (B) 3 (C) 4 (D) 5
7. How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K-
bytes?
(A) 8  (B) 32 (C) 64 (D) 128
8. A CPU generally handles an interrupt by executing an interrupt service routine
(A)  As soon as an interrupt is raised
(B)  By checking the interrupt register at the end of fetch cycle.
(C)  By checking the interrupt register after finishing the execution of the current
instruction.
(D)  By checking the interrupt register at fixed time intervals.
CS? GATE Paper 2009
9. In which one of the following page replacement policies, Belady’s anomaly may
occur?
(A) FIFO (B) Optimal (C) LRU (D) MRU
10. The essential content(s) in each entry of a page table is / are
(A) Virtual page number
(B) Page frame number
(C) Both virtual page number and page frame number
(D) Access right information
11. What is the number of swaps required to sort n elements using selection sort, in
the worst case?
(A) (n) ? (B) (n log n) ? (C)
2
(n ) ? (D)
2
(n log n) ?
12. S aSa bSb a b ? ;The language generated by the above grammar over the
alphabet {a,b} is the set of
(A) All palindromes.
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes.
13. Which of the following statement(s) is / are correct regarding Bellman-Ford
shortest path algorithm?
P.  Always finds a negative weighted cycle, if one exists.
Q.  Finds whether any negative weighted cycle is reachable from the source.
(A)  P only   (B)  Q only
(C)  both P and Q   (D)  Neither P nor Q
14. Let
A
p be a problem that belongs to the class NP. Then which one of the
following is TRUE?
(A) There is no polynomial time algorithm for
A
p .
(B) If
A
p can be solved deterministically in polynomial time, then P = NP.
(C) If
A
p is NP-hard, then it is NP-complete.
(D)
A
p may be undecidable.
15. Which one of the following languages over the alphabet {0,1} is described by the
regular expression: (0+1)*0(0+1)*0(0+1)*?
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.
CS? GATE Paper 2009
16. Which one of the following is FALSE?
(A) There is unique minimal DFA for every regular language
(B) Every NFA can be converted to an equivalent PDA.
(C) Complement of every context-free language is recursive.
(D) Every nondeterministic PDA can be converted to an equivalent deterministic
PDA.
17. Match all items in Group 1 with correct options from those given in Group 2.
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
(A) P-4. Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4, S-3
18. Consider the program below:
# include < stdio.h >
int fun(int n, int * f_p) {
int t, f;
if (n <= 1) {
*f_p = 1;
return 1;
}
t = fun (n-1, f_p);
f = t+*f_p;
*f_p = t;
return f;
}
int main() {
int x = 15;
printf ("%d\ n", fun(5,& x));
return 0;
}
The value printed is
(A) 6  (B) 8 (C) 14 (D) 15
19. The coupling between different modules of a software is categorized as follows:
I.  Content coupling II. Common coupling
III. Control coupling IV Stamp coupling
V. Data coupling
Coupling between modules can be ranked in the order of strongest (least
desirable) to weakest (most desirable) as follows:
(A) I-II-III-IV-V (B) V-IV-III-II-I (C) I-III-V -II-IV (D) IV-II-V -III-I
CS? GATE Paper 2009
20. Consider the HTML table definition given below:
table border=1>
<tr> <td rowspan=2> ab </td>
<td colspan=2> cd </td>
</tr>
<tr> <td> ef </td>
<td rowspan=2> gh </td>
</tr>
<tr> <td colspan=2> ik </td>
</tr>
</table>
<
The number of rows in each column and the number of columns in each row are:
(A) 2,2,3 and 2,3,2 (B) 2,2,3 and 2,2,3
(C) 2,3,2 and 2,3,2 (D) 2,3,2 and 2,2,3
Q. No. 21 – 56 Carry Two Marks Each
21. An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The
probability that the face value is odd is 90% of the probability that the face value
is even. The probability of getting any even numbered face is the same.
If the probability that the face is even given that it is greater than 3 is 0.75,
which one of the following options is closest to the probability that the face value
exceeds 3?
(A) 0.453 (B) 0.468 (C) 0.485 (D) 0.492
22. For the composition table of a cyclic group shown below
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
Which one of the following choices is correct?
(A) a, b are generators (B) b, c are generators
(C) c, d are generators (D) d, a are generators
23. Which one of the following is the most appropriate logical formula to represent
the statement? “Gold and silver ornaments are precious”.
The following notations are used:
G(x): x is a gold ornament
S(x): x is a silver ornament
P(x): x is precious
(A) ( ) ( ) ( ) ( ) ( )
x P x G x S x ? ? ? (B) ( ) ( ) ( ) ( )
( )
x G x S x P x ? ? ?
(C) ( ) ( ) ( ) ( )
( )
x G x S x P x ? ? ? (D) ( ) ( ) ( ) ( )
( )
x G x S x P x ? ? ?
CS? GATE Paper 2009
24. The binary operation ? is defined as follows
Which one of the following is equivalent to P Q ? ?
(A) Q P ¬ ¬
(B) P Q ¬
(C) P Q ¬
(D) P Q ¬ ¬
25. ( ) ( )
/ 4
0
1 tanx / 1 tanx dx
p
- +
?
evaluates  to
(A) 0 (B) 1 (C) ln 2 (D)
1
ln 2
2
26. Consider the following well-formed formulae:
I.  ( ) ( )
x P x ¬? II. ( ) ( )
x P x ¬? III. ( ) ( )
x P x ¬? ¬ IV. ( ) ( )
x P x ¬? ¬
Which of the above are equivalent?
(A) I and III (B) I and IV (C) II and III (D) II and IV
27. Given the following state table of an FSM with two states A and B, one input and
one output:
Present
State A
Present
State B
Input
Next
State A
Next
State B
Output
0 0 0 0 0 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1
If the initial state is A = 0, B=0, what is the minimum length of an input string
which will take the machine to the state A=0, B=1 with Output=1?
(A) 3 (B) 4 (C) 5 (D) 6
28. Consider a 4 stage pipeline processor. The number of cycles needed by the four
instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:
S1 S2 S3 S4
I1 2 1 1 1
I2 1 3 2 2
I3 2 1 1 3
I4 1 2 2 2
P Q P?Q
T T T
T F T
F T F
F F T
```

## GATE Computer Science Engineering(CSE) 2024 Mock Test Series

151 docs|216 tests

## FAQs on Gate (CS) 2009 Paper without Solution - GATE Computer Science Engineering(CSE) 2024 Mock Test Series - Computer Science Engineering (CSE)

 1. What is the significance of the Gate (CS) 2009 Paper in computer science?
Ans. The Gate (CS) 2009 Paper is a widely recognized examination in the field of computer science. It serves as a benchmark for evaluating the knowledge and aptitude of individuals seeking admission to postgraduate programs or employment opportunities in computer science-related fields.
 2. How can I access the Gate (CS) 2009 Paper without solutions?
Ans. You can access the Gate (CS) 2009 Paper without solutions through various online platforms. Many educational websites and forums provide previous year question papers for free. You can also check official Gate websites or refer to books specifically designed for Gate preparation that include previous year papers.
 3. What topics are covered in the Gate (CS) 2009 Paper?
Ans. The Gate (CS) 2009 Paper covers a wide range of topics in computer science. It includes subjects like algorithms, data structures, programming languages, computer networks, operating systems, databases, theory of computation, and more. It is essential to have a comprehensive understanding of these topics to perform well in the examination.
 4. Are there any specific strategies or tips to excel in the Gate (CS) 2009 Paper?
Ans. Yes, there are several strategies that can help you excel in the Gate (CS) 2009 Paper. It is advisable to thoroughly understand the syllabus and exam pattern. Develop a study plan and allocate sufficient time to each subject. Practice solving previous year papers and take mock tests to enhance your time management and problem-solving skills. Seek guidance from experienced mentors or join coaching institutes if necessary.
 5. How can the Gate (CS) 2009 Paper benefit my career in computer science?
Ans. Clearing the Gate (CS) 2009 Paper with a good score can open numerous career opportunities in the field of computer science. It serves as a qualifying exam for admission to prestigious postgraduate programs like M.Tech/M.E. in reputed institutes. Many public sector undertakings (PSUs) and government organizations also consider Gate scores for recruitment. Additionally, it can enhance your profile when applying for job positions in top companies, as it showcases your knowledge and competence in the field of computer science.

## GATE Computer Science Engineering(CSE) 2024 Mock Test Series

151 docs|216 tests

### Up next

 Explore Courses for Computer Science Engineering (CSE) exam

### Top Courses for Computer Science Engineering (CSE)

Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;