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

 Page 1


?CS-Paper Code-B? GATE 2011 
Q. No. 1 – 25 Carry One Mark Each 
1. The simplified SOP (Sum of Product) form of the Boolean expression
( ) ( ) ( )
P Q R . P Q R . P Q R + + + + + + is
(A) 
( )
PQ R + (B) 
( )
P QR + (C) 
( )
PQ R + (D) ( ) PQ R +
Answer: - (B) 
Exp: - 
 
( )( )
f P R P Q = + +
P QR = +
Alternate method 
( ) ( ) ( ) ( ) ( ) ( )
+ + + + + + = + + + + + + P Q R . P Q R . P Q R P Q R . P Q R . P Q R
( ) ( )
( )
P QR P QR P QR P Q R R P QR P Q P QR P Q QR
P Q R P Q R
= + + = + + = + = +
= + = +
2. Which one of the following circuits is NOT equivalent to a 2-input XNOR
(exclusive NOR) gate?
(A)  (B)  
(C)  (D)  
Answer: - (D) 
Exp: - All options except option ‘D’ gives EX-NOR gates 
3. The minimum number of D flip-flops needed to design a mod-258 counter is
(A) 9 (B) 8 (C) 512 (D) 258
Answer: - (A) 
Exp: - 
n
2 258 n 9 = ? =
4. A thread is usually defined as a ‘light weight process’ because an operating 
system (OS) maintains smaller data structures for a thread than for a process. In 
relation to this, which of the followings is TRUE? 
QR
P
1
0 1 1 1
00 01 11 10
Page 2


?CS-Paper Code-B? GATE 2011 
Q. No. 1 – 25 Carry One Mark Each 
1. The simplified SOP (Sum of Product) form of the Boolean expression
( ) ( ) ( )
P Q R . P Q R . P Q R + + + + + + is
(A) 
( )
PQ R + (B) 
( )
P QR + (C) 
( )
PQ R + (D) ( ) PQ R +
Answer: - (B) 
Exp: - 
 
( )( )
f P R P Q = + +
P QR = +
Alternate method 
( ) ( ) ( ) ( ) ( ) ( )
+ + + + + + = + + + + + + P Q R . P Q R . P Q R P Q R . P Q R . P Q R
( ) ( )
( )
P QR P QR P QR P Q R R P QR P Q P QR P Q QR
P Q R P Q R
= + + = + + = + = +
= + = +
2. Which one of the following circuits is NOT equivalent to a 2-input XNOR
(exclusive NOR) gate?
(A)  (B)  
(C)  (D)  
Answer: - (D) 
Exp: - All options except option ‘D’ gives EX-NOR gates 
3. The minimum number of D flip-flops needed to design a mod-258 counter is
(A) 9 (B) 8 (C) 512 (D) 258
Answer: - (A) 
Exp: - 
n
2 258 n 9 = ? =
4. A thread is usually defined as a ‘light weight process’ because an operating 
system (OS) maintains smaller data structures for a thread than for a process. In 
relation to this, which of the followings is TRUE? 
QR
P
1
0 1 1 1
00 01 11 10
?CS-Paper Code-B? GATE 2011 
(A) On per-thread basis, the OS maintains only CPU register state 
(B) The OS does not maintain a separate stack for each thread 
(C) On per-thread basis, the OS does not maintain virtual memory state 
(D) On per thread basis, the OS maintains only scheduling and accounting 
information 
Answer: - (A) 
5. K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs? 
(A) K4 is planar while Q3 is not (B) Both K4 and Q3 are planar 
(C) Q3 is planar while K4 is not (D) Neither K4 not Q3 is planar 
Answer: - (B) 
Exp: - 
? Both K
4
 and Q
3
 are planar
6. If the difference between the expectation of the square of random variable
( )
2
E X ? ?
? ?
 and the square of the expectation of the random variable
( )
2
E X ? ?
? ?
 is
denoted by R then 
(A) R 0 = (B) R<0 (C) R 0 = (D) R>0 
Answer: - (C) 
7. The lexical analysis for a modern computer language such as Java needs the
power of which one of the following machine models in a necessary and sufficient
sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
K4 Q3
4
K
3
Q
Page 3


?CS-Paper Code-B? GATE 2011 
Q. No. 1 – 25 Carry One Mark Each 
1. The simplified SOP (Sum of Product) form of the Boolean expression
( ) ( ) ( )
P Q R . P Q R . P Q R + + + + + + is
(A) 
( )
PQ R + (B) 
( )
P QR + (C) 
( )
PQ R + (D) ( ) PQ R +
Answer: - (B) 
Exp: - 
 
( )( )
f P R P Q = + +
P QR = +
Alternate method 
( ) ( ) ( ) ( ) ( ) ( )
+ + + + + + = + + + + + + P Q R . P Q R . P Q R P Q R . P Q R . P Q R
( ) ( )
( )
P QR P QR P QR P Q R R P QR P Q P QR P Q QR
P Q R P Q R
= + + = + + = + = +
= + = +
2. Which one of the following circuits is NOT equivalent to a 2-input XNOR
(exclusive NOR) gate?
(A)  (B)  
(C)  (D)  
Answer: - (D) 
Exp: - All options except option ‘D’ gives EX-NOR gates 
3. The minimum number of D flip-flops needed to design a mod-258 counter is
(A) 9 (B) 8 (C) 512 (D) 258
Answer: - (A) 
Exp: - 
n
2 258 n 9 = ? =
4. A thread is usually defined as a ‘light weight process’ because an operating 
system (OS) maintains smaller data structures for a thread than for a process. In 
relation to this, which of the followings is TRUE? 
QR
P
1
0 1 1 1
00 01 11 10
?CS-Paper Code-B? GATE 2011 
(A) On per-thread basis, the OS maintains only CPU register state 
(B) The OS does not maintain a separate stack for each thread 
(C) On per-thread basis, the OS does not maintain virtual memory state 
(D) On per thread basis, the OS maintains only scheduling and accounting 
information 
Answer: - (A) 
5. K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs? 
(A) K4 is planar while Q3 is not (B) Both K4 and Q3 are planar 
(C) Q3 is planar while K4 is not (D) Neither K4 not Q3 is planar 
Answer: - (B) 
Exp: - 
? Both K
4
 and Q
3
 are planar
6. If the difference between the expectation of the square of random variable
( )
2
E X ? ?
? ?
 and the square of the expectation of the random variable
( )
2
E X ? ?
? ?
 is
denoted by R then 
(A) R 0 = (B) R<0 (C) R 0 = (D) R>0 
Answer: - (C) 
7. The lexical analysis for a modern computer language such as Java needs the
power of which one of the following machine models in a necessary and sufficient
sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
K4 Q3
4
K
3
Q
?CS-Paper Code-B? GATE 2011 
(D) Turing machine 
Answer: - (A) 
Exp: - Lexical Analysis is implemented by finite automata 
8. Let the page fault service time be 10ms in a computer with average memory
access time being 20ns. If one page fault is generated for every 10
6
 memory
accesses, what is the effective access time for the memory?
(A) 21ns (B) 30ns (C) 23ns (D) 35ns 
Answer: - (B) 
Exp: - P = page fault rate 
EA = p × page fault service time 
( )
6
6 6
1 p Memory access time
1 1
10 10 1 20 29.9ns
10 10
+ - ×
? ?
= × × + - × ?
? ?
? ?
9. Consider a hypothetical processor with an instruction of type LW R1, 20(R2),
which during execution reads a 32-bit word from memory and stores it in a 32-bit
register R1. The effective address of the memory location is obtained by the
addition of constant 20 and the contents of register R2. Which of the following
best reflects the addressing mode implemented by this instruction for the
operand in memory?
(A) Immediate Addressing (B) Register Addressing 
(C) Register Indirect Scaled Addressing (D) Base Indexed Addressing
Answer: - (D) 
Exp: - Here 20 will act as base and content of R
2
 will be index 
10. What does the following fragment of C-program print?
( )
char c "GATE2011";
char *p =c;
printf "%s", p+p 3 p 1 ;
= ? ?
? ?
- ? ? ? ?
? ? ? ?
(A) GATE2011 (B) E2011 (C) 2011 (D) 011 
Answer: - (C) 
Page 4


?CS-Paper Code-B? GATE 2011 
Q. No. 1 – 25 Carry One Mark Each 
1. The simplified SOP (Sum of Product) form of the Boolean expression
( ) ( ) ( )
P Q R . P Q R . P Q R + + + + + + is
(A) 
( )
PQ R + (B) 
( )
P QR + (C) 
( )
PQ R + (D) ( ) PQ R +
Answer: - (B) 
Exp: - 
 
( )( )
f P R P Q = + +
P QR = +
Alternate method 
( ) ( ) ( ) ( ) ( ) ( )
+ + + + + + = + + + + + + P Q R . P Q R . P Q R P Q R . P Q R . P Q R
( ) ( )
( )
P QR P QR P QR P Q R R P QR P Q P QR P Q QR
P Q R P Q R
= + + = + + = + = +
= + = +
2. Which one of the following circuits is NOT equivalent to a 2-input XNOR
(exclusive NOR) gate?
(A)  (B)  
(C)  (D)  
Answer: - (D) 
Exp: - All options except option ‘D’ gives EX-NOR gates 
3. The minimum number of D flip-flops needed to design a mod-258 counter is
(A) 9 (B) 8 (C) 512 (D) 258
Answer: - (A) 
Exp: - 
n
2 258 n 9 = ? =
4. A thread is usually defined as a ‘light weight process’ because an operating 
system (OS) maintains smaller data structures for a thread than for a process. In 
relation to this, which of the followings is TRUE? 
QR
P
1
0 1 1 1
00 01 11 10
?CS-Paper Code-B? GATE 2011 
(A) On per-thread basis, the OS maintains only CPU register state 
(B) The OS does not maintain a separate stack for each thread 
(C) On per-thread basis, the OS does not maintain virtual memory state 
(D) On per thread basis, the OS maintains only scheduling and accounting 
information 
Answer: - (A) 
5. K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs? 
(A) K4 is planar while Q3 is not (B) Both K4 and Q3 are planar 
(C) Q3 is planar while K4 is not (D) Neither K4 not Q3 is planar 
Answer: - (B) 
Exp: - 
? Both K
4
 and Q
3
 are planar
6. If the difference between the expectation of the square of random variable
( )
2
E X ? ?
? ?
 and the square of the expectation of the random variable
( )
2
E X ? ?
? ?
 is
denoted by R then 
(A) R 0 = (B) R<0 (C) R 0 = (D) R>0 
Answer: - (C) 
7. The lexical analysis for a modern computer language such as Java needs the
power of which one of the following machine models in a necessary and sufficient
sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
K4 Q3
4
K
3
Q
?CS-Paper Code-B? GATE 2011 
(D) Turing machine 
Answer: - (A) 
Exp: - Lexical Analysis is implemented by finite automata 
8. Let the page fault service time be 10ms in a computer with average memory
access time being 20ns. If one page fault is generated for every 10
6
 memory
accesses, what is the effective access time for the memory?
(A) 21ns (B) 30ns (C) 23ns (D) 35ns 
Answer: - (B) 
Exp: - P = page fault rate 
EA = p × page fault service time 
( )
6
6 6
1 p Memory access time
1 1
10 10 1 20 29.9ns
10 10
+ - ×
? ?
= × × + - × ?
? ?
? ?
9. Consider a hypothetical processor with an instruction of type LW R1, 20(R2),
which during execution reads a 32-bit word from memory and stores it in a 32-bit
register R1. The effective address of the memory location is obtained by the
addition of constant 20 and the contents of register R2. Which of the following
best reflects the addressing mode implemented by this instruction for the
operand in memory?
(A) Immediate Addressing (B) Register Addressing 
(C) Register Indirect Scaled Addressing (D) Base Indexed Addressing
Answer: - (D) 
Exp: - Here 20 will act as base and content of R
2
 will be index 
10. What does the following fragment of C-program print?
( )
char c "GATE2011";
char *p =c;
printf "%s", p+p 3 p 1 ;
= ? ?
? ?
- ? ? ? ?
? ? ? ?
(A) GATE2011 (B) E2011 (C) 2011 (D) 011 
Answer: - (C) 
?CS-Paper Code-B? GATE 2011 
11. A max-heap is a heap where the value of each parent is greater than or equal to
the value of its children. Which of the following is a max-heap?
(A)  (B)  
(C)  (D)  
Answer: - (B) 
Exp: - Heap is a complete binary tree 
12. An algorithm to find the length of the longest monotonically increasing sequence
of numbers in an array A 0 :n 1 - ? ?
? ?
 is given below.
Let L
i
 denote the length of the longest monotonically increasing sequence starting
at index i in the array
Initialize L
n-1
 =1
For all i such that 0 i n 2 = = -
[] [ ]
{
i 1
i
1 L if A i A i 1
L
1  Otherwise
+
+ < +
=
Finally the length of the longest monotonically increasing sequence is
( )
0 1 n 1
Max L ,L ,...,L
-
. Which of the following statements is TRUE?
(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and
bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Answer: - (A) 
13. Let P be a regular language and Q be a context free language such that Q P. ?
(For example, let P be the language represented by the regular expression p*q*
and Q be
{ }
?
n n
p q |n N ). Then which of the following is ALWAYS regular? 
(A) P Q n (B) - P Q (C) * P ? - (D) * Q ? -
10
6 8
4 2 5
1
10
6 8
4 2 5 1
10
6 5
4
1
8
2
5
8 2
1 10 4 6
Page 5


?CS-Paper Code-B? GATE 2011 
Q. No. 1 – 25 Carry One Mark Each 
1. The simplified SOP (Sum of Product) form of the Boolean expression
( ) ( ) ( )
P Q R . P Q R . P Q R + + + + + + is
(A) 
( )
PQ R + (B) 
( )
P QR + (C) 
( )
PQ R + (D) ( ) PQ R +
Answer: - (B) 
Exp: - 
 
( )( )
f P R P Q = + +
P QR = +
Alternate method 
( ) ( ) ( ) ( ) ( ) ( )
+ + + + + + = + + + + + + P Q R . P Q R . P Q R P Q R . P Q R . P Q R
( ) ( )
( )
P QR P QR P QR P Q R R P QR P Q P QR P Q QR
P Q R P Q R
= + + = + + = + = +
= + = +
2. Which one of the following circuits is NOT equivalent to a 2-input XNOR
(exclusive NOR) gate?
(A)  (B)  
(C)  (D)  
Answer: - (D) 
Exp: - All options except option ‘D’ gives EX-NOR gates 
3. The minimum number of D flip-flops needed to design a mod-258 counter is
(A) 9 (B) 8 (C) 512 (D) 258
Answer: - (A) 
Exp: - 
n
2 258 n 9 = ? =
4. A thread is usually defined as a ‘light weight process’ because an operating 
system (OS) maintains smaller data structures for a thread than for a process. In 
relation to this, which of the followings is TRUE? 
QR
P
1
0 1 1 1
00 01 11 10
?CS-Paper Code-B? GATE 2011 
(A) On per-thread basis, the OS maintains only CPU register state 
(B) The OS does not maintain a separate stack for each thread 
(C) On per-thread basis, the OS does not maintain virtual memory state 
(D) On per thread basis, the OS maintains only scheduling and accounting 
information 
Answer: - (A) 
5. K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs? 
(A) K4 is planar while Q3 is not (B) Both K4 and Q3 are planar 
(C) Q3 is planar while K4 is not (D) Neither K4 not Q3 is planar 
Answer: - (B) 
Exp: - 
? Both K
4
 and Q
3
 are planar
6. If the difference between the expectation of the square of random variable
( )
2
E X ? ?
? ?
 and the square of the expectation of the random variable
( )
2
E X ? ?
? ?
 is
denoted by R then 
(A) R 0 = (B) R<0 (C) R 0 = (D) R>0 
Answer: - (C) 
7. The lexical analysis for a modern computer language such as Java needs the
power of which one of the following machine models in a necessary and sufficient
sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
K4 Q3
4
K
3
Q
?CS-Paper Code-B? GATE 2011 
(D) Turing machine 
Answer: - (A) 
Exp: - Lexical Analysis is implemented by finite automata 
8. Let the page fault service time be 10ms in a computer with average memory
access time being 20ns. If one page fault is generated for every 10
6
 memory
accesses, what is the effective access time for the memory?
(A) 21ns (B) 30ns (C) 23ns (D) 35ns 
Answer: - (B) 
Exp: - P = page fault rate 
EA = p × page fault service time 
( )
6
6 6
1 p Memory access time
1 1
10 10 1 20 29.9ns
10 10
+ - ×
? ?
= × × + - × ?
? ?
? ?
9. Consider a hypothetical processor with an instruction of type LW R1, 20(R2),
which during execution reads a 32-bit word from memory and stores it in a 32-bit
register R1. The effective address of the memory location is obtained by the
addition of constant 20 and the contents of register R2. Which of the following
best reflects the addressing mode implemented by this instruction for the
operand in memory?
(A) Immediate Addressing (B) Register Addressing 
(C) Register Indirect Scaled Addressing (D) Base Indexed Addressing
Answer: - (D) 
Exp: - Here 20 will act as base and content of R
2
 will be index 
10. What does the following fragment of C-program print?
( )
char c "GATE2011";
char *p =c;
printf "%s", p+p 3 p 1 ;
= ? ?
? ?
- ? ? ? ?
? ? ? ?
(A) GATE2011 (B) E2011 (C) 2011 (D) 011 
Answer: - (C) 
?CS-Paper Code-B? GATE 2011 
11. A max-heap is a heap where the value of each parent is greater than or equal to
the value of its children. Which of the following is a max-heap?
(A)  (B)  
(C)  (D)  
Answer: - (B) 
Exp: - Heap is a complete binary tree 
12. An algorithm to find the length of the longest monotonically increasing sequence
of numbers in an array A 0 :n 1 - ? ?
? ?
 is given below.
Let L
i
 denote the length of the longest monotonically increasing sequence starting
at index i in the array
Initialize L
n-1
 =1
For all i such that 0 i n 2 = = -
[] [ ]
{
i 1
i
1 L if A i A i 1
L
1  Otherwise
+
+ < +
=
Finally the length of the longest monotonically increasing sequence is
( )
0 1 n 1
Max L ,L ,...,L
-
. Which of the following statements is TRUE?
(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and
bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Answer: - (A) 
13. Let P be a regular language and Q be a context free language such that Q P. ?
(For example, let P be the language represented by the regular expression p*q*
and Q be
{ }
?
n n
p q |n N ). Then which of the following is ALWAYS regular? 
(A) P Q n (B) - P Q (C) * P ? - (D) * Q ? -
10
6 8
4 2 5
1
10
6 8
4 2 5 1
10
6 5
4
1
8
2
5
8 2
1 10 4 6
?CS-Paper Code-B? GATE 2011 
Answer: - (C) 
Exp: - 
*
P S - is the complement of P so it is always regular,
since regular languages are closed under complementation 
14. In a compiler, keywords of a language are recognized during 
(A) parsing of the program (B) the code generation 
(C) the lexical analysis of the program (D) dataflow analysis 
Answer: - (C) 
Exp: - Any identifier is also a token so it is recognized in lexical Analysis 
15. A layer-4 firewall (a device that can look at all protocol headers up to the
transport layer) CANNOT
(A) block entire HTTP traffic during 9:00PM and 5:00AM
(B) block all ICMP traffic
(C) stop incoming traffic from a specific IP address but allow outgoing traffic to
the same IP address 
(D) block TCP traffic from a specific user on a multi-user system during 9:00PM 
and 5:00AM 
Answer: - (A) 
Exp: - Since it is a layer 4 firewall it cannot block application layer protocol like HTTP. 
16. If two fair coins are flipped and at least one of the outcomes is known to be a
head, what is the probability that both outcomes are heads?
(A) 1/3 (B) 1/4 (C) 1/2 (D) 2/3
Answer: - (A) 
Exp: - Sample space = { } HH,HT, TH
Required probability 
1
3
=
17. Consider different activities related to email.
m1: Send an email from a mail client to a mail server
m2: Download an email from mailbox server to a mail client
m3: Checking email in a web browser
Which is the application level protocol used in each activity?
(A) m1:HTTP  m2:SMTP m3:POP (B) m1:SMTP m2:FTP m3:HTTP 
(C) m1: SMTP m2: POP m3: HTTP (D) m1: POP m2: SMTP m3:IMAP 
Answer: - (C) 
Exp: - Sending an email will be done through user agent and message transfer agent by 
SMTP, downloading an email from mail box is done through POP, checking email 
in a web browser is done through HTTP