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 callRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

380 docs|127 tests