Gate (CS) 2006 Paper without Solution

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

 Download, print and study this document offline
``` 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
```

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

55 docs|215 tests

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

 1. What is the CS Gate exam?
Ans. The CS Gate exam, also known as the Computer Science Gate exam, is a national level examination conducted in India for admission to postgraduate programs in computer science and related fields. It tests the candidate's knowledge and understanding of various subjects in computer science.
 2. What is the significance of the Gate exam for CS students?
Ans. The Gate exam holds significant importance for CS students as it serves as a qualifying exam for admission to prestigious institutions for higher education, such as the Indian Institutes of Technology (IITs) and the National Institutes of Technology (NITs). It also acts as a gateway for various job opportunities in the government and private sectors.
 3. How can I apply for the CS Gate exam?
Ans. To apply for the CS Gate exam, you need to visit the official website of the conducting body and complete the online application process. The application form usually requires personal details, academic information, and the selection of the preferred exam center. You will also need to upload scanned copies of your photograph and signature.
 4. What are the eligibility criteria for the CS Gate exam?
Ans. The eligibility criteria for the CS Gate exam include having a bachelor's degree in engineering/technology or a master's degree in computer science or related subjects. The qualifying degree should be from a recognized university/institution. There is no age limit for appearing in the Gate exam.
 5. How should I prepare for the CS Gate exam?
Ans. To prepare for the CS Gate exam, it is essential to have a thorough understanding of the core concepts in computer science. Start by creating a study schedule and allocate sufficient time for each subject. Utilize standard textbooks, reference materials, and online resources for studying. Solve previous year question papers and take mock tests to improve time management and assess your preparation level.

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

55 docs|215 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
Related Searches

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;