## Gate-1991

 Question 1

 A Out of syllabus.
Digital-Logic-Design       Circuits
 Question 2
In interleaved memory organization, consecutive words are stored in consecutive memory modules in ________ interleaving, whereas consecutive words are stored within the module in ________ interleaving.
 A low order, high order
Computer-Organization       Memory-Organization
Question 2 Explanation:
→ Consecutive words in consecutive memory modules in low order interleaving as the lower order bits determine the module.
→ Consecutive words in same memory module in high order interleaving as the higher order bits determine the module.
 Question 3

 A 9
Digital-Logic-Design       Number-Systems
Question 3 Explanation:
Hexadecimal representation of a given no. is,
(9753)16
It's binary representation is,
1001011101010011
∴ The no. of 1's is 9.
 Question 4
Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 8087 CPU is operated ________.
 A Out of syllabus.
Computer-Organization       Microprocessor
 Question 5
When two 4-bit binary number A = a3a2a1a0 and B = b3b2b1b0 are multiplied, the digit c1 of the product C is given by _________
 A c1 = b1a0 ⊕ a1b0
Digital-Logic-Design       Number-Systems
Question 5 Explanation:

⇒ c1 = b1a0 ⊕ a1b0
 Question 6

 A PASCAL is out of syllabus.
Programming       PASCAL-Programming
 Question 7
The minimum number of comparisons required to sort 5 elements is _____
 A 7
Algorithms       Sorting
Question 7 Explanation:
Minimum no. of comparisons
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
 Question 8

 A 144
Algorithms       Binary-Trees
Question 8 Explanation:
 Question 9

 A 4, 1, 6, 7, 3, 2, 5, 8
Algorithms       Tree Traversals
Question 9 Explanation:
Inorder traversal is
(Left, Root, Right)
So, the order will be
4, 1, 6, 7, 3, 2, 5, 8
 Question 10

 A 41
Programming       Recursion
Question 10 Explanation:
The recurrence relation for the no. of calls is
T(n) = T(n-1) + T(n-2) + 2
T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)
T(2) = 2
T(3) = 4
T(4) = 8
T(5) = 14
T(6) = 24
T(7) = 40
Counting the initial call, we get
40+1 = 41
 Question 11
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 __________.
 A 3 , 4
Compiler-Design       Operands
Question 11 Explanation:
** is used for exponentiation.
So, in total 3 registers are required and 6 memory operations in total to fetch all operands.
 Question 12
A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ________
 A properly nested.
Compiler-Design       Precedence-Graph
Question 12 Explanation:
A given set of processes canf th be implemented by using only parbegin/parends statement, if the presedence graph of these processes is properly nested.
 Question 13
The number of integer-triples (i.j.k) with 1 ≤ i.j.k ≤ 300 such that i + j + k is divisible by 3 is ________
 A Fill in the blanks.
Engineering-Mathematics       Linear-Algebra
 Question 14
If the longest chain in a partial order is of length n then the partial order can be written as a ______ of n antichains.
 A disjoint
Engineering-Mathematics       Set-Theory
Question 14 Explanation:
Suppose the length of the longest chain in a partial order is n. Then the elements in the poset can be partitioned into a disjoint antichains.
 Question 15
The maximum number of possible edges in an undirected graph with a vertices and k components is ________.
 A (n-k)(n-k+1)/2
Engineering-Mathematics       Graph-Theory
Question 15 Explanation:
N vertices and K components.
To get maximum, take one vertex each for each component, except last component.
Now, k-1 components have 1 vertex each and so on edges.
The last component has (n-(k-1)) vertices. So make the last component complete, i.e., it has n-(n-1)C2
= (n-k)(n-k+1)/2
= maximum no. of edges
 Question 16

 A Out of syllabus.
Computer-Networks       General
 Question 17

 A Out of syllabus.
Computer-Organization       Microprocessor
 Question 18

 A A-R, B-P, C-S, D-Q
Operating-Systems       General
Question 18 Explanation:
A-R
B-P
C-S
D-Q
Buddy system: The buddy system is a technique to allocate the memory by dividing the memory into partitions to try to satisfy a memory request as suitably as possible.
Interpretation: Runtime.
Pointer type: Garbage collector dereference the dangling pointer.
Virtual memory: Segmentation.
 Question 19

 A A-S, B-R, C-P, D-Q
Algorithms       General
 Question 20
 A lower power dissipation B greater speed C smaller chip size D fewer masks for fabrication E none of the above
Computer-Organization       CMOS
Question 20 Explanation:
Note: Out of syllabus.
 Question 21
 A faster operation B ease of avoiding problems due to hazards C lower hardware requirement D better noise immunity E none of the above
Digital-Logic-Design       Sequential-Circuits
Question 21 Explanation:
In synchronization, there is a less chance of hazards but it can increase the delay. Then the advantage is ease of avoiding problems due to hazards.
 Question 22
 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 F Both A and B
Operating-Systems       Virtual Memory
Question 22 Explanation:
Virtual memory is independent of size of main memory and depends on available secondary storage.
MAR can hold the address that is generated from CPU and limits the total virtual memory address space.
 Question 23
 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
Computer-Organization       Microprocessor
Question 23 Explanation:
Note: Out of syllabus.
 Question 24

 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
Computer-Organization       Microprocessor
Question 24 Explanation:
Note: Out of syllabus.
 Question 25

 A O(n2) B O(mn) C O(m+n) D O(m logn) E O(m2) F B, D and E
Algorithms       Time-Complexity
Question 25 Explanation:
Though the edges are sorted still due to finding union operation complexity is O(m log n).
→ Where m is no. of edges and n is number of vertices then n = O(m2)
→ O(m logn) < O(mn)
 Question 26

 A 20, 10, 20, 10, 20 B 20, 20, 10, 10, 20 C 10, 20, 20, 10, 20 D 20, 20, 10, 20, 10
Algorithms       Stacks
Question 26 Explanation:
PUSH(10), PUSH(20), POP = 20 (i)
→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)
→ PUSH(10), PUSH(10), POP = 10 (iii)
→ PUSH(10), POP = 10 (iv)
→ PUSH(20)
→ PUSH(20), POP = 20 (v)
20, 20, 10, 10, 20
 Question 27

 A B C D E None of the above
Programming       PASCAL-Programming
Question 27 Explanation:
Note: Out of syllabus.
 Question 28

 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.
Question 28 Explanation:
Linked editor can be able to perform
1) external symbol resolution
2) relocation
 Question 29

 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. F A and D
Compiler-Design       Parsers
Question 29 Explanation:
(A) It is true. Left recursive grammar if used directly in recursive descent parsing causes an infinite loop. So, left recursion must be removed before giving to a recursive descent parser.
(B) False.
(C) It is false. The language can have dynamic data types which required dynamically growing memory when data type size increases.
(D) Is true and using macro we can do this.
(E) Out of syllabus now.
 Question 30

 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. E B and D
Operating-Systems       Virtual Memory
Question 30 Explanation:
(A) Is true.
(B) Is false, because one of the solution is Peterson's solution which is purely software based solution without use of hardware.
(C) Is true.
(D) False, memory can get fragmented with best fit technique.
 Question 31

 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
Engineering-Mathematics       Prepositional-Logic
Question 31 Explanation:
For the propositional formula A→B to be tautology the T→F condition should never arise.
So, in option (B) it is saying that F< sub>1 ∧ F2 is not satisfiable means F1 ∧ F2 is always false.
And False → anything is always true.
 Question 32

 A L(s) ⊆ L(r) and L(s) ⊆ L(t) B L(r) ⊆ L(s) and L(s) ⊆ L(t) C L(s) ⊆ L(t) and L(s) ⊆ L(r) D L(t) ⊆ L(s) and L(s) ⊆ L(r) E None of the above F A and C
Theory-of-Computation       Regular-Expressions
Question 32 Explanation:
L(s) ⊆ L(r), because 'r' generates all strings which 's' does but 'r' also generates '101' which 's' does not generate.
L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.
 Question 33

 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 F B, C and D
Theory-of-Computation       General
Question 33 Explanation:
(B), (C) and (D) are true. But the strongest answer would be (D), a regular language. Because every finite language is a regular language.
And, regular language ⊂ context-free ⊂ context-sensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.
There are 33 questions to complete.