Courses

# Computer Science and Information Technology (CS) 1991 GATE Paper without solution GATE Notes | EduRev

## Computer Science Engineering (CSE) : Computer Science and Information Technology (CS) 1991 GATE Paper without solution GATE Notes | EduRev

``` 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
(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
(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
(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
(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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## GATE Past Year Papers for Practice (All Branches)

380 docs|127 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;