Let’s Learn about GATE CSE 1991 Previous-Year Questions.
PART - A [ 74 Marks ]
1. Fill in the blanks:
( 15 x 2 = 30 )
(i) For the digital circuit in figure, the expression for the output 1 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:
163 * 9 + 162 * 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 A = a3a2a1a0 and B = b3b2b1b0 are multiplied, thedigit C1 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 mode 2 <> 0 do 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:
fib (n): = if n = 0 then 1
else if n = 1 then 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 operand is either a register or a memory location,
With the minimum number of memory accesses of operands, the number of registers required to evaluate this expression is ______. The number of memory accesses of operands 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 ________.
2. Match the pairs in the following questions by writing the corresponding letters only.
(4 x 2 = 8)
(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 |