Gate (CS) 2006 Paper without Solution - Notes | Study GATE Computer Science Engineering(CSE) 2023 Mock Test Series - Computer Science Engineering (CSE)

 Page 1


?EC?Test ID: 00  All India Mock GATE Test Series     
Q.1 – Q.20 Carry One Mark Each 
1. Consider the polynomial ( )
2 2
0 1 2 3
, p x a a x a x a x = + + + where 0, .
i
a i ? ? The
minimum number of multiplications needed to evaluate pon an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set
of all subsets of W. The number of functions from Z to E is:
(A)
2
xy
Z
(B) 2
xy
Z×
(C)
2
x y
Z
+
(D) 2
xyz
3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false? 
(A) It is not closed 
(B) 2 does not have an inverse 
(C) 3 does not have an inverse 
(D) 8 does not have an inverse 
4. A relation R is defined on ordered pairs of integers as follows:
( ) ( ) , , x y R u v if  and . x u y v < > Then R is:
(A) Neither a Partial Order nor an Equivalence Relation 
(B) A Partial Order but not a Total Order 
(C) A Total Order 
(D) An Equivalence Relation  
5. For which one of the following reasons does Internet Protocol (IP) use the time-
 to-live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time 
(B) Discard packets that reach later than that time 
(C) Prevent packets from looping indefinitely  
(D) Limit the time for which a packet gets queued in intermediate routers. 
6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units
and arrive at times 0, 2 and 6, respectively. How many context switches are
Page 2


?EC?Test ID: 00  All India Mock GATE Test Series     
Q.1 – Q.20 Carry One Mark Each 
1. Consider the polynomial ( )
2 2
0 1 2 3
, p x a a x a x a x = + + + where 0, .
i
a i ? ? The
minimum number of multiplications needed to evaluate pon an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set
of all subsets of W. The number of functions from Z to E is:
(A)
2
xy
Z
(B) 2
xy
Z×
(C)
2
x y
Z
+
(D) 2
xyz
3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false? 
(A) It is not closed 
(B) 2 does not have an inverse 
(C) 3 does not have an inverse 
(D) 8 does not have an inverse 
4. A relation R is defined on ordered pairs of integers as follows:
( ) ( ) , , x y R u v if  and . x u y v < > Then R is:
(A) Neither a Partial Order nor an Equivalence Relation 
(B) A Partial Order but not a Total Order 
(C) A Total Order 
(D) An Equivalence Relation  
5. For which one of the following reasons does Internet Protocol (IP) use the time-
 to-live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time 
(B) Discard packets that reach later than that time 
(C) Prevent packets from looping indefinitely  
(D) Limit the time for which a packet gets queued in intermediate routers. 
6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units
and arrive at times 0, 2 and 6, respectively. How many context switches are
?EC?Test ID: 00  All India Mock GATE Test Series     
needed if the operating system implements a shortest remaining time first 
scheduling algorithm? Do not count the context switches at time zero and at the 
end. 
(A) 1 
(B) 2 
(C) 3 
(D) 4 
7. Consider the following grammar.
* S S E
S E
E F E
E F
F id
?
?
? +
?
?
Consider the following ( ) 0 LR items corresponding to the grammar above.
(i) *. S S E ?
(ii) . E F E ? +
(iii) . E F E ? +
Given the items above, which two of them will appear in the same set in the 
canonical sets-of-items for the grammar? 
(A) (i) and (ii) 
(B) (ii) and (iii) 
(C) (i) and (iii) 
(D) None of the above  
8. You are given a free running clock with a duty cycle of 50% and a digital
waveform f which changes only at the negative edge of the clock. Which one of
the following circuits (using clocked D flip-flops) will delay the phase of f by
180°?
(A)
(B) 
f 
clk 
D 
Q 
D Q 
f 
clk 
D 
D Q 
Q 
Page 3


?EC?Test ID: 00  All India Mock GATE Test Series     
Q.1 – Q.20 Carry One Mark Each 
1. Consider the polynomial ( )
2 2
0 1 2 3
, p x a a x a x a x = + + + where 0, .
i
a i ? ? The
minimum number of multiplications needed to evaluate pon an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set
of all subsets of W. The number of functions from Z to E is:
(A)
2
xy
Z
(B) 2
xy
Z×
(C)
2
x y
Z
+
(D) 2
xyz
3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false? 
(A) It is not closed 
(B) 2 does not have an inverse 
(C) 3 does not have an inverse 
(D) 8 does not have an inverse 
4. A relation R is defined on ordered pairs of integers as follows:
( ) ( ) , , x y R u v if  and . x u y v < > Then R is:
(A) Neither a Partial Order nor an Equivalence Relation 
(B) A Partial Order but not a Total Order 
(C) A Total Order 
(D) An Equivalence Relation  
5. For which one of the following reasons does Internet Protocol (IP) use the time-
 to-live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time 
(B) Discard packets that reach later than that time 
(C) Prevent packets from looping indefinitely  
(D) Limit the time for which a packet gets queued in intermediate routers. 
6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units
and arrive at times 0, 2 and 6, respectively. How many context switches are
?EC?Test ID: 00  All India Mock GATE Test Series     
needed if the operating system implements a shortest remaining time first 
scheduling algorithm? Do not count the context switches at time zero and at the 
end. 
(A) 1 
(B) 2 
(C) 3 
(D) 4 
7. Consider the following grammar.
* S S E
S E
E F E
E F
F id
?
?
? +
?
?
Consider the following ( ) 0 LR items corresponding to the grammar above.
(i) *. S S E ?
(ii) . E F E ? +
(iii) . E F E ? +
Given the items above, which two of them will appear in the same set in the 
canonical sets-of-items for the grammar? 
(A) (i) and (ii) 
(B) (ii) and (iii) 
(C) (i) and (iii) 
(D) None of the above  
8. You are given a free running clock with a duty cycle of 50% and a digital
waveform f which changes only at the negative edge of the clock. Which one of
the following circuits (using clocked D flip-flops) will delay the phase of f by
180°?
(A)
(B) 
f 
clk 
D 
Q 
D Q 
f 
clk 
D 
D Q 
Q 
?EC?Test ID: 00  All India Mock GATE Test Series     
(C) 
(D) 
9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal).
Which one of the following is a legal program counter (all values in decimal)?
(A) 400
(B) 500
(C) 600
(D) 700
10. In a binary max heap containing n numbers, the smallest element can be found
in time
(A) ( ) O n
(B) ( ) log O n
(C) ( ) loglog O n
(D) ( ) 1 O
11. Consider a weighted complete graph G on the vertex set { }
1 2
, ,....,
n
? ? ? such that
the weight of the edge 
( )
, is 2 - .
i j
i j ? ? The weight of a minimum spanning tree 
of G is: 
(A) 1 n-
(B) 2 2 n-
(C) 
2
n ? ?
? ?
? ?
(D) 
2
n
12. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it
runs in linear time, the data structure to be used is:
(A) Queue
f 
clk 
D 
D Q 
Q 
f 
clk 
D 
Q 
D Q 
Page 4


?EC?Test ID: 00  All India Mock GATE Test Series     
Q.1 – Q.20 Carry One Mark Each 
1. Consider the polynomial ( )
2 2
0 1 2 3
, p x a a x a x a x = + + + where 0, .
i
a i ? ? The
minimum number of multiplications needed to evaluate pon an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set
of all subsets of W. The number of functions from Z to E is:
(A)
2
xy
Z
(B) 2
xy
Z×
(C)
2
x y
Z
+
(D) 2
xyz
3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false? 
(A) It is not closed 
(B) 2 does not have an inverse 
(C) 3 does not have an inverse 
(D) 8 does not have an inverse 
4. A relation R is defined on ordered pairs of integers as follows:
( ) ( ) , , x y R u v if  and . x u y v < > Then R is:
(A) Neither a Partial Order nor an Equivalence Relation 
(B) A Partial Order but not a Total Order 
(C) A Total Order 
(D) An Equivalence Relation  
5. For which one of the following reasons does Internet Protocol (IP) use the time-
 to-live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time 
(B) Discard packets that reach later than that time 
(C) Prevent packets from looping indefinitely  
(D) Limit the time for which a packet gets queued in intermediate routers. 
6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units
and arrive at times 0, 2 and 6, respectively. How many context switches are
?EC?Test ID: 00  All India Mock GATE Test Series     
needed if the operating system implements a shortest remaining time first 
scheduling algorithm? Do not count the context switches at time zero and at the 
end. 
(A) 1 
(B) 2 
(C) 3 
(D) 4 
7. Consider the following grammar.
* S S E
S E
E F E
E F
F id
?
?
? +
?
?
Consider the following ( ) 0 LR items corresponding to the grammar above.
(i) *. S S E ?
(ii) . E F E ? +
(iii) . E F E ? +
Given the items above, which two of them will appear in the same set in the 
canonical sets-of-items for the grammar? 
(A) (i) and (ii) 
(B) (ii) and (iii) 
(C) (i) and (iii) 
(D) None of the above  
8. You are given a free running clock with a duty cycle of 50% and a digital
waveform f which changes only at the negative edge of the clock. Which one of
the following circuits (using clocked D flip-flops) will delay the phase of f by
180°?
(A)
(B) 
f 
clk 
D 
Q 
D Q 
f 
clk 
D 
D Q 
Q 
?EC?Test ID: 00  All India Mock GATE Test Series     
(C) 
(D) 
9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal).
Which one of the following is a legal program counter (all values in decimal)?
(A) 400
(B) 500
(C) 600
(D) 700
10. In a binary max heap containing n numbers, the smallest element can be found
in time
(A) ( ) O n
(B) ( ) log O n
(C) ( ) loglog O n
(D) ( ) 1 O
11. Consider a weighted complete graph G on the vertex set { }
1 2
, ,....,
n
? ? ? such that
the weight of the edge 
( )
, is 2 - .
i j
i j ? ? The weight of a minimum spanning tree 
of G is: 
(A) 1 n-
(B) 2 2 n-
(C) 
2
n ? ?
? ?
? ?
(D) 
2
n
12. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it
runs in linear time, the data structure to be used is:
(A) Queue
f 
clk 
D 
D Q 
Q 
f 
clk 
D 
Q 
D Q 
?EC?Test ID: 00  All India Mock GATE Test Series     
(B) Stack 
(C) Heap 
(D) B-Tree 
13. A scheme for storing binary trees in an array X is as follows. Indexing of X starts
at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left
child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to
store any binary tree on n vertices the minimum size of X should be
(A)
2
log n
(B) n
(C) 2 1 n+
(D) 2 1
n
- 
14. Which one of the following in place sorting algorithms needs the minimum
number of swaps?
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort
15. Consider the following C-program fragment in which , and n i j are integer
variables.
( ) for i = n, j = 0; i > 0; i /= 2, j +=i ;
Let ( ) val j denote the value stored in the variable j after termination of the
for loop. Which one of the following is true? 
(A) ( ) ( ) log val j n ? =
(B) ( )
( )
val j n ? =
(C) ( ) ( ) val j n ? =
(D) ( ) ( ) log val j n n ? =
16. Let S be an NP-complete problem and Q and R be two other problems not known
to be in NP. Q is polynomial time reducible to S and S is polynomial-time
reducible to R. Which one of the following statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
Page 5


?EC?Test ID: 00  All India Mock GATE Test Series     
Q.1 – Q.20 Carry One Mark Each 
1. Consider the polynomial ( )
2 2
0 1 2 3
, p x a a x a x a x = + + + where 0, .
i
a i ? ? The
minimum number of multiplications needed to evaluate pon an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set
of all subsets of W. The number of functions from Z to E is:
(A)
2
xy
Z
(B) 2
xy
Z×
(C)
2
x y
Z
+
(D) 2
xyz
3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given
below are four plausible reasons. Which one of them is false? 
(A) It is not closed 
(B) 2 does not have an inverse 
(C) 3 does not have an inverse 
(D) 8 does not have an inverse 
4. A relation R is defined on ordered pairs of integers as follows:
( ) ( ) , , x y R u v if  and . x u y v < > Then R is:
(A) Neither a Partial Order nor an Equivalence Relation 
(B) A Partial Order but not a Total Order 
(C) A Total Order 
(D) An Equivalence Relation  
5. For which one of the following reasons does Internet Protocol (IP) use the time-
 to-live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time 
(B) Discard packets that reach later than that time 
(C) Prevent packets from looping indefinitely  
(D) Limit the time for which a packet gets queued in intermediate routers. 
6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units
and arrive at times 0, 2 and 6, respectively. How many context switches are
?EC?Test ID: 00  All India Mock GATE Test Series     
needed if the operating system implements a shortest remaining time first 
scheduling algorithm? Do not count the context switches at time zero and at the 
end. 
(A) 1 
(B) 2 
(C) 3 
(D) 4 
7. Consider the following grammar.
* S S E
S E
E F E
E F
F id
?
?
? +
?
?
Consider the following ( ) 0 LR items corresponding to the grammar above.
(i) *. S S E ?
(ii) . E F E ? +
(iii) . E F E ? +
Given the items above, which two of them will appear in the same set in the 
canonical sets-of-items for the grammar? 
(A) (i) and (ii) 
(B) (ii) and (iii) 
(C) (i) and (iii) 
(D) None of the above  
8. You are given a free running clock with a duty cycle of 50% and a digital
waveform f which changes only at the negative edge of the clock. Which one of
the following circuits (using clocked D flip-flops) will delay the phase of f by
180°?
(A)
(B) 
f 
clk 
D 
Q 
D Q 
f 
clk 
D 
D Q 
Q 
?EC?Test ID: 00  All India Mock GATE Test Series     
(C) 
(D) 
9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal).
Which one of the following is a legal program counter (all values in decimal)?
(A) 400
(B) 500
(C) 600
(D) 700
10. In a binary max heap containing n numbers, the smallest element can be found
in time
(A) ( ) O n
(B) ( ) log O n
(C) ( ) loglog O n
(D) ( ) 1 O
11. Consider a weighted complete graph G on the vertex set { }
1 2
, ,....,
n
? ? ? such that
the weight of the edge 
( )
, is 2 - .
i j
i j ? ? The weight of a minimum spanning tree 
of G is: 
(A) 1 n-
(B) 2 2 n-
(C) 
2
n ? ?
? ?
? ?
(D) 
2
n
12. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it
runs in linear time, the data structure to be used is:
(A) Queue
f 
clk 
D 
D Q 
Q 
f 
clk 
D 
Q 
D Q 
?EC?Test ID: 00  All India Mock GATE Test Series     
(B) Stack 
(C) Heap 
(D) B-Tree 
13. A scheme for storing binary trees in an array X is as follows. Indexing of X starts
at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left
child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to
store any binary tree on n vertices the minimum size of X should be
(A)
2
log n
(B) n
(C) 2 1 n+
(D) 2 1
n
- 
14. Which one of the following in place sorting algorithms needs the minimum
number of swaps?
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort
15. Consider the following C-program fragment in which , and n i j are integer
variables.
( ) for i = n, j = 0; i > 0; i /= 2, j +=i ;
Let ( ) val j denote the value stored in the variable j after termination of the
for loop. Which one of the following is true? 
(A) ( ) ( ) log val j n ? =
(B) ( )
( )
val j n ? =
(C) ( ) ( ) val j n ? =
(D) ( ) ( ) log val j n n ? =
16. Let S be an NP-complete problem and Q and R be two other problems not known
to be in NP. Q is polynomial time reducible to S and S is polynomial-time
reducible to R. Which one of the following statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
?EC?Test ID: 00  All India Mock GATE Test Series     
17. An element in an array X is called a leader if it is greater than all elements to the
right of it in X. The best algorithm to find all leaders in an array
(A) Solves it in linear time using a left to right pass of the array
(B) Solves it in linear time using a right to left pass of the array
(C) Solves it using divide and conquer in time ( ) log n n ?
(D) Solves it in time 
( )
2
n ?
18. We are given a set { }
1
,...... where 2.
i
n i
X x x x = = A sample S X ? is drawn by 
selecting each 
i
x independently with probability 
1
.
2
i
p = The expected value of the 
smallest number in sample S is: 
(A) 
1
n
(B) 2 
(C) n
(D) n 
19. Let 
{ } { }
1 2
0 1 0 , 0 , 0 1 0 , 0 ,
n m n m n m n m m
L n m L n m
+ + +
= = = = and 
{ }
3
0 1 0 , 0 .
n m n m n m
L n m
+ + +
= = Which of these languages are NOT context free? 
(A) 
1
L only 
(B) 
3
L only 
(C) 
1 2
 and L L
(D) 
2 3
 and L L
20. Consider the following log sequence of two transactions on a bank account, with
initial balance 12000,  that transfer 2000 to a mortgage payment and then apply
a 5% interest.
1. T1 start
2. T1 B old=1200 new=10000
3. T1 M old=0 new=2000
4. T1 commit
5. T2 start
6. T2 B old=10000 new=10500
7. T2 commit
Suppose the database system crashes just before log record 7 is written. When 
the system is restarted, which one statement is true of the recovery procedure? 
(A) We must redo log record 6 to set B to 10500 
(B) We must undo log record 6 to set B to 10000 and then redo log records 2 
and 3