Gate 1991 CS Computer Science Question Paper

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:
16 *9 16 *7 16 *5 3 + + +   3 2
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 A a a a a B b b b b = = and  are multiplied,
3 2 1 0 3 2 1 0 the digit c of the product C is given by _________
1
(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 _____

(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:
(xi)
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 ___________
( ) a b c d e f + - * / ** is to be evaluated on a two-
(xi) The arithmetic expression :
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
statement, if the precedence graph of these processes is parbegin/parend
________
(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 ________.

Match the pairs in the following questions by writing the corresponding letters 2only.
(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:

(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.

(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) ! n 2
(B) The number of binary strings of length of 2n with an equal number
˜ ' 3n
(Q) of 0's and 1's         ÷
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 (S)
with 2n 0's.         1 2 ˜ ' n
÷
n n + 1 «

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 spa ce 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 ignal
(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

(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) O n  2
( )
(b) O mn
( )
(c) O m n +
( )
(d) O m n log
( )
(e) O m 2

(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