Tags:- gate,gate 2011,gate papers,gate cs papers,gate answer key,gate cs 1991 answer key,gate cs 1991 paper,gate papers solution,gate mock papers,gate test papers,gate test series

GATE CS - 1991
SECTION – A
1. Fill in the blanks:
(i) For the digital in figure, the expression for the output f is _________









Solution

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^3*9 + 16^2*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=a0 a1 a2 a3 B=b0 b1 b2 b3 are multiplied,
the digit 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 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:

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

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 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(mlogn)
(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

(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
(b) matches external names of one program with their location in other programs
(c) matches the parameters of subroutine definition with the location of parameters of subroutine call.
(d) acts as link between text editor and the user
(e) acts as a link between compiler and user program.

(x) Indicate all the true statements from the following:
(a) Recursive descent parsing cannot be used for grammar with left recursion.
(b) The intermediate form the representing expressions which is best suited for code optimization is the post fix form.
(c) A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation.
(d) Although C does not support call by name parameter passing, the effect can be correctly simulated in C.
(e) No feature of Pascal violates strong typing in Pascal.

(xi) Indicate all the false statements from the statements given below:
(a) The amount of virtual memory available is limited by the availability of secondary storage.
(b) Any implementation of a critical section requires the use of an indivisible machine-instruction, such as test-and-set.
(c) The LRU page replacement policy may cause hashing for some type of programs.
(d) The best fit techniques for memory allocation ensures the memory will never be fragmented.

(xii) If F1,F2,F3 are propositional formulae such that F1^F2-->F3 and F1^F1-->~F2 Are both tautologies, then which of thefollowing is true:
(a) Both F1 and F2 are tautologies
(b) The conjunction F1^F2 is not satisfiable
(c) Neither is tautologous
(d) Neither is satisfiable
(e) None of the above

(xiv)Which one of the following is the strongest correct statement about a finite language over some finite alphabet ?

(a) It could be undecidable
(b) It is Turing-machine recognizable
(c) It is a context-sensitive language
(d) It is a regular language
(e) None of the above

0 comments

Post a Comment

Popular Posts

Followers

SUBSCRIBE

Enter your email address:

Delivered by FeedBurner

Powered by FeedBurner

I heart FeedBurner