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

 Page 1


GATE CS - 1991
SECTION - A 
1. Fill in the blanks:
(i) For the digital in figure, the expression for the output f is _________ 
(ii) In interleaved memory organization, consecutive words are stored in 
consecutive memory modules in ________ interleaving, whereas consecutive 
words are stored within the module in ________ interleaving. 
(iii) Consider the number given by the decimal expression: 
3 2
16 * 9 16 *7 16 *5 3 + + + 
The number of 1’s in the unsigned binary representation of the number is 
________. 
(iv) Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 
8087 CPU is operated ________. 
(v) When two 4-bit binary number 
3 2 1 0 3 2 1 0
 and A a a a a B b b b b = = are multiplied, 
the digit 
1
c of the product C is given by _________ 
(vi) Consider the following PASCAL program segment: 
if i mode 2 = 0 then 
 while i > = 0 do 
 begin 
 i:=i div 2; 
 if i mod 2 < > 0 do then i:=i – 1 
else i:=i – 2 
end 
An appropriate loop-invariant for the while-loop is ______ 
(vii) The minimum number of comparisons required to sort 5 elements is _____ 
a b 
x 
y 
f 
Page 2


GATE CS - 1991
SECTION - A 
1. Fill in the blanks:
(i) For the digital in figure, the expression for the output f is _________ 
(ii) In interleaved memory organization, consecutive words are stored in 
consecutive memory modules in ________ interleaving, whereas consecutive 
words are stored within the module in ________ interleaving. 
(iii) Consider the number given by the decimal expression: 
3 2
16 * 9 16 *7 16 *5 3 + + + 
The number of 1’s in the unsigned binary representation of the number is 
________. 
(iv) Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 
8087 CPU is operated ________. 
(v) When two 4-bit binary number 
3 2 1 0 3 2 1 0
 and A a a a a B b b b b = = are multiplied, 
the digit 
1
c of the product C is given by _________ 
(vi) Consider the following PASCAL program segment: 
if i mode 2 = 0 then 
 while i > = 0 do 
 begin 
 i:=i div 2; 
 if i mod 2 < > 0 do then i:=i – 1 
else i:=i – 2 
end 
An appropriate loop-invariant for the while-loop is ______ 
(vii) The minimum number of comparisons required to sort 5 elements is _____ 
a b 
x 
y 
f 
GATE CS - 1991
  
(viii) The weighted external path length of the binary tree in figure is _____ 
(ix) If the binary tree in figure is traversed in inorder, then the order in which the 
nodes will be visited is ______ 
(x) Consider the following recursive definition of fib: 
fib (n) : = if n = 0 then 1 
 else if n = 1 than 1 
 else fib (n – 1) + fib ( n – 2) 
The number of times fib is called (including the first call) for an evaluation of 
fib (7) is ___________ 
(xi) The arithmetic expression : ( ) * / ** a b c d e f + - is to be evaluated on a two-
address machine, where each operands, the number of registers required to 
evaluate this expression is ______. The number of memory access of 
operand is __________. 
(xii) A given set of processes can be implemented by using only 
parbegin/parend statement, if the precedence graph of these processes is 
________ 
(xiii) The number of integer-triples (i.j.k) with 1 = i.j.k = 300 such that i + j + k is 
divisible by 3 is ________ 
(xiv) If the longest chain in a partial order is of length n then the partial order 
can be written as a ______ of n antichains. 
(xv) The maximum number of possible edges in an undirected graph with a 
vertices and k components is ________. 
15 
9 
10 
7 
5 
4 
2 
1 
4 
6 
7 
3 
5 
2 
8 
Page 3


GATE CS - 1991
SECTION - A 
1. Fill in the blanks:
(i) For the digital in figure, the expression for the output f is _________ 
(ii) In interleaved memory organization, consecutive words are stored in 
consecutive memory modules in ________ interleaving, whereas consecutive 
words are stored within the module in ________ interleaving. 
(iii) Consider the number given by the decimal expression: 
3 2
16 * 9 16 *7 16 *5 3 + + + 
The number of 1’s in the unsigned binary representation of the number is 
________. 
(iv) Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 
8087 CPU is operated ________. 
(v) When two 4-bit binary number 
3 2 1 0 3 2 1 0
 and A a a a a B b b b b = = are multiplied, 
the digit 
1
c of the product C is given by _________ 
(vi) Consider the following PASCAL program segment: 
if i mode 2 = 0 then 
 while i > = 0 do 
 begin 
 i:=i div 2; 
 if i mod 2 < > 0 do then i:=i – 1 
else i:=i – 2 
end 
An appropriate loop-invariant for the while-loop is ______ 
(vii) The minimum number of comparisons required to sort 5 elements is _____ 
a b 
x 
y 
f 
GATE CS - 1991
  
(viii) The weighted external path length of the binary tree in figure is _____ 
(ix) If the binary tree in figure is traversed in inorder, then the order in which the 
nodes will be visited is ______ 
(x) Consider the following recursive definition of fib: 
fib (n) : = if n = 0 then 1 
 else if n = 1 than 1 
 else fib (n – 1) + fib ( n – 2) 
The number of times fib is called (including the first call) for an evaluation of 
fib (7) is ___________ 
(xi) The arithmetic expression : ( ) * / ** a b c d e f + - is to be evaluated on a two-
address machine, where each operands, the number of registers required to 
evaluate this expression is ______. The number of memory access of 
operand is __________. 
(xii) A given set of processes can be implemented by using only 
parbegin/parend statement, if the precedence graph of these processes is 
________ 
(xiii) The number of integer-triples (i.j.k) with 1 = i.j.k = 300 such that i + j + k is 
divisible by 3 is ________ 
(xiv) If the longest chain in a partial order is of length n then the partial order 
can be written as a ______ of n antichains. 
(xv) The maximum number of possible edges in an undirected graph with a 
vertices and k components is ________. 
15 
9 
10 
7 
5 
4 
2 
1 
4 
6 
7 
3 
5 
2 
8 
GATE CS - 1991
  
2. Match the pairs in the following questions by writing the corresponding letters
only.
(i) 
(A) IEEE 488 (P) specifies the interface for connecting a single device 
(B) IEEE 796 (Q) specifies the bus standard for connecting a computer to other 
devices including CPU’s 
(C) IEEE 696 (R) specifies the standard for an instrumentation bus 
(D) RS232-C (S) specifies the bus standard for the “backplane” bus called multibus. 
(ii) For the 8086 microprocessor: 
(iii) 
(A) Buddy system (P) Run-time type specification 
(B) Interpretation (Q) Segmentation  
(C) Pointer type (R) Memory allocation 
(D) Virtual memory (S) Garbage collection 
(iv) 
(A) The number distinct binary trees with n nodes 
(P) 
!
2
n
(B) The number of binary strings of length of 2n with an equal number 
of 0’s and 1’s  
(Q) 
3n
n
? ?
? ?
? ?
(C) The number of even permutations of n objects 
(R) 
2n
n
? ?
? ?
? ?
(D) The number of binary strings of length 6m which are palindromes 
with 2n 0’s. 
(S) 
1 2
1
n
n n
? ?
? ?
+
? ?
(A) RQ/GT (P) Used by processor for holding the bus for consecutive instruction 
cycles.  
(B) LOCK (Q) Used for extending the memory or I/O cycle times 
(C) HOLD (R) Used for getting hold of processor bus in minimum bus mode 
(D) READY (S) Used for requesting processor bus in minimum bus mode. 
Page 4


GATE CS - 1991
SECTION - A 
1. Fill in the blanks:
(i) For the digital in figure, the expression for the output f is _________ 
(ii) In interleaved memory organization, consecutive words are stored in 
consecutive memory modules in ________ interleaving, whereas consecutive 
words are stored within the module in ________ interleaving. 
(iii) Consider the number given by the decimal expression: 
3 2
16 * 9 16 *7 16 *5 3 + + + 
The number of 1’s in the unsigned binary representation of the number is 
________. 
(iv) Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 
8087 CPU is operated ________. 
(v) When two 4-bit binary number 
3 2 1 0 3 2 1 0
 and A a a a a B b b b b = = are multiplied, 
the digit 
1
c of the product C is given by _________ 
(vi) Consider the following PASCAL program segment: 
if i mode 2 = 0 then 
 while i > = 0 do 
 begin 
 i:=i div 2; 
 if i mod 2 < > 0 do then i:=i – 1 
else i:=i – 2 
end 
An appropriate loop-invariant for the while-loop is ______ 
(vii) The minimum number of comparisons required to sort 5 elements is _____ 
a b 
x 
y 
f 
GATE CS - 1991
  
(viii) The weighted external path length of the binary tree in figure is _____ 
(ix) If the binary tree in figure is traversed in inorder, then the order in which the 
nodes will be visited is ______ 
(x) Consider the following recursive definition of fib: 
fib (n) : = if n = 0 then 1 
 else if n = 1 than 1 
 else fib (n – 1) + fib ( n – 2) 
The number of times fib is called (including the first call) for an evaluation of 
fib (7) is ___________ 
(xi) The arithmetic expression : ( ) * / ** a b c d e f + - is to be evaluated on a two-
address machine, where each operands, the number of registers required to 
evaluate this expression is ______. The number of memory access of 
operand is __________. 
(xii) A given set of processes can be implemented by using only 
parbegin/parend statement, if the precedence graph of these processes is 
________ 
(xiii) The number of integer-triples (i.j.k) with 1 = i.j.k = 300 such that i + j + k is 
divisible by 3 is ________ 
(xiv) If the longest chain in a partial order is of length n then the partial order 
can be written as a ______ of n antichains. 
(xv) The maximum number of possible edges in an undirected graph with a 
vertices and k components is ________. 
15 
9 
10 
7 
5 
4 
2 
1 
4 
6 
7 
3 
5 
2 
8 
GATE CS - 1991
  
2. Match the pairs in the following questions by writing the corresponding letters
only.
(i) 
(A) IEEE 488 (P) specifies the interface for connecting a single device 
(B) IEEE 796 (Q) specifies the bus standard for connecting a computer to other 
devices including CPU’s 
(C) IEEE 696 (R) specifies the standard for an instrumentation bus 
(D) RS232-C (S) specifies the bus standard for the “backplane” bus called multibus. 
(ii) For the 8086 microprocessor: 
(iii) 
(A) Buddy system (P) Run-time type specification 
(B) Interpretation (Q) Segmentation  
(C) Pointer type (R) Memory allocation 
(D) Virtual memory (S) Garbage collection 
(iv) 
(A) The number distinct binary trees with n nodes 
(P) 
!
2
n
(B) The number of binary strings of length of 2n with an equal number 
of 0’s and 1’s  
(Q) 
3n
n
? ?
? ?
? ?
(C) The number of even permutations of n objects 
(R) 
2n
n
? ?
? ?
? ?
(D) The number of binary strings of length 6m which are palindromes 
with 2n 0’s. 
(S) 
1 2
1
n
n n
? ?
? ?
+
? ?
(A) RQ/GT (P) Used by processor for holding the bus for consecutive instruction 
cycles.  
(B) LOCK (Q) Used for extending the memory or I/O cycle times 
(C) HOLD (R) Used for getting hold of processor bus in minimum bus mode 
(D) READY (S) Used for requesting processor bus in minimum bus mode. 
GATE CS - 1991
  
3. Choose the correct alternatives (more than one may be correct) and write the
corresponding letters only:
(i) The advantages of CMOS technology over a MOS is:
(a) lower power dissipation
(b) greater speed
(c) smaller chip size
(d) fewer masks for fabrication
(e) none of the above
(ii) Advantage of synchronous sequential circuits over asynchronous ones is: 
(a) faster operation   
(b) ease of avoiding problems due to hazards  
(c) lower hardware requirement  
(d) better noise immunity  
(e) none of the above  
(iii) The total size of address space is a virtual memory systems is limited by 
(a) the length of MAR 
(b) the available secondary storage  
(c) the available main memory 
(d) all of the above  
(e) none of the above 
(iv) The TRAP interrupt mechanism of the 8085 microprocessor: 
(a) executes an instruction supplied by an external device through the INTA 
signal 
(b) executes an instruction from memory location 20H 
(c) executes a NOP 
(d) none of the above  
(v) The ALE line of an 8085 microprocessor is used to: 
(a) latch the output of an I/O instruction into an external latch  
(b) deactivate the chip-select signal from memory devices 
(c) latch the 8 bits of address lines AD7-AD0 into an external latch  
(d) find the interrupt enable status of the TRAP interrupt  
(e) None of the above  
Page 5


GATE CS - 1991
SECTION - A 
1. Fill in the blanks:
(i) For the digital in figure, the expression for the output f is _________ 
(ii) In interleaved memory organization, consecutive words are stored in 
consecutive memory modules in ________ interleaving, whereas consecutive 
words are stored within the module in ________ interleaving. 
(iii) Consider the number given by the decimal expression: 
3 2
16 * 9 16 *7 16 *5 3 + + + 
The number of 1’s in the unsigned binary representation of the number is 
________. 
(iv) Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 
8087 CPU is operated ________. 
(v) When two 4-bit binary number 
3 2 1 0 3 2 1 0
 and A a a a a B b b b b = = are multiplied, 
the digit 
1
c of the product C is given by _________ 
(vi) Consider the following PASCAL program segment: 
if i mode 2 = 0 then 
 while i > = 0 do 
 begin 
 i:=i div 2; 
 if i mod 2 < > 0 do then i:=i – 1 
else i:=i – 2 
end 
An appropriate loop-invariant for the while-loop is ______ 
(vii) The minimum number of comparisons required to sort 5 elements is _____ 
a b 
x 
y 
f 
GATE CS - 1991
  
(viii) The weighted external path length of the binary tree in figure is _____ 
(ix) If the binary tree in figure is traversed in inorder, then the order in which the 
nodes will be visited is ______ 
(x) Consider the following recursive definition of fib: 
fib (n) : = if n = 0 then 1 
 else if n = 1 than 1 
 else fib (n – 1) + fib ( n – 2) 
The number of times fib is called (including the first call) for an evaluation of 
fib (7) is ___________ 
(xi) The arithmetic expression : ( ) * / ** a b c d e f + - is to be evaluated on a two-
address machine, where each operands, the number of registers required to 
evaluate this expression is ______. The number of memory access of 
operand is __________. 
(xii) A given set of processes can be implemented by using only 
parbegin/parend statement, if the precedence graph of these processes is 
________ 
(xiii) The number of integer-triples (i.j.k) with 1 = i.j.k = 300 such that i + j + k is 
divisible by 3 is ________ 
(xiv) If the longest chain in a partial order is of length n then the partial order 
can be written as a ______ of n antichains. 
(xv) The maximum number of possible edges in an undirected graph with a 
vertices and k components is ________. 
15 
9 
10 
7 
5 
4 
2 
1 
4 
6 
7 
3 
5 
2 
8 
GATE CS - 1991
  
2. Match the pairs in the following questions by writing the corresponding letters
only.
(i) 
(A) IEEE 488 (P) specifies the interface for connecting a single device 
(B) IEEE 796 (Q) specifies the bus standard for connecting a computer to other 
devices including CPU’s 
(C) IEEE 696 (R) specifies the standard for an instrumentation bus 
(D) RS232-C (S) specifies the bus standard for the “backplane” bus called multibus. 
(ii) For the 8086 microprocessor: 
(iii) 
(A) Buddy system (P) Run-time type specification 
(B) Interpretation (Q) Segmentation  
(C) Pointer type (R) Memory allocation 
(D) Virtual memory (S) Garbage collection 
(iv) 
(A) The number distinct binary trees with n nodes 
(P) 
!
2
n
(B) The number of binary strings of length of 2n with an equal number 
of 0’s and 1’s  
(Q) 
3n
n
? ?
? ?
? ?
(C) The number of even permutations of n objects 
(R) 
2n
n
? ?
? ?
? ?
(D) The number of binary strings of length 6m which are palindromes 
with 2n 0’s. 
(S) 
1 2
1
n
n n
? ?
? ?
+
? ?
(A) RQ/GT (P) Used by processor for holding the bus for consecutive instruction 
cycles.  
(B) LOCK (Q) Used for extending the memory or I/O cycle times 
(C) HOLD (R) Used for getting hold of processor bus in minimum bus mode 
(D) READY (S) Used for requesting processor bus in minimum bus mode. 
GATE CS - 1991
  
3. Choose the correct alternatives (more than one may be correct) and write the
corresponding letters only:
(i) The advantages of CMOS technology over a MOS is:
(a) lower power dissipation
(b) greater speed
(c) smaller chip size
(d) fewer masks for fabrication
(e) none of the above
(ii) Advantage of synchronous sequential circuits over asynchronous ones is: 
(a) faster operation   
(b) ease of avoiding problems due to hazards  
(c) lower hardware requirement  
(d) better noise immunity  
(e) none of the above  
(iii) The total size of address space is a virtual memory systems is limited by 
(a) the length of MAR 
(b) the available secondary storage  
(c) the available main memory 
(d) all of the above  
(e) none of the above 
(iv) The TRAP interrupt mechanism of the 8085 microprocessor: 
(a) executes an instruction supplied by an external device through the INTA 
signal 
(b) executes an instruction from memory location 20H 
(c) executes a NOP 
(d) none of the above  
(v) The ALE line of an 8085 microprocessor is used to: 
(a) latch the output of an I/O instruction into an external latch  
(b) deactivate the chip-select signal from memory devices 
(c) latch the 8 bits of address lines AD7-AD0 into an external latch  
(d) find the interrupt enable status of the TRAP interrupt  
(e) None of the above  
GATE CS - 1991
  
(vi) Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph 
G with vertices and m edges has the time complexity of: 
(a) 
( )
2
O n
(b) ( ) O mn
(c) ( ) O m n +
(d) ( ) log O m n 
(e) 
( )
2
O m
(vii) The following sequence of operations is performed on a stack: 
PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, 
PUSH (20), POP  
The sequence of values popped out is: 
(a) 20, 10, 20, 10, 20 
(b) 20, 20, 10, 10, 20 
(c) 10, 20, 20, 10, 20 
(d) 20, 20, 10, 20, 10 
(viii) Consider the following Pascal function: 
function X (M:integer) : integer; 
var i:integer; 
begin 
 i = 0; 
 while i*i<M do i; =i+1 
 X;=i 
end 
The function call X(N), if N is positive, will return 
(a) 
( )
N
(b) 
( )
1 N +
(c) N
? ?
? ?
 
(d) 1 N
? ?
+
? ?
(e) None of the above 
(ix) A “link editor” is a program that: 
(a) matches the parameters of the macro-definition with locations of the 
parameters of the macro call