## GATE-1987

 Question 1
In a microprocessor-based system, if a bus (DMA) request and an interrupt request arrive sumultaneously, the microprocessor attends first to the bus request.
 A True. B False.
Computer-Organization       Modes-of-Transfer
Question 1 Explanation:
The HOLD input has a higher priority than the INTR or NMI interrupt inputs.
 Question 2
Data transfer between a microprocessor and an I/O device is usually faster in memory-mapped-I/O scheme than in I/O-mapped - I/O scheme.
 A True B False
Computer-Organization       I/O-Handling
Question 2 Explanation:
Memory mapped I/0 runs faster than I/0 mapped I/O.
 Question 3
It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?
 A True B False
Data-Structures       Binary-Trees
Question 3 Explanation:
To construct binary tree uniquely we need either inorder and postorder or inorder and preorder.
 Question 4
The union of two equivalence relations is also an equivalence relation.
 A True B False
Engineering-Mathematics       Sets-And-Relation
Question 4 Explanation:
Equivalence relation should satisfy Reflexive, Symmetric and Transitive property.
Reflexive ∪ Reflexive = Reflexive
Symmetric ∪ Symmetric = Symmetric
Transitive ∪ Transitive ≠ Transitive
Since Transitivity does not satisfy union, so union of two equivalence relation is not an equivalence relation.
 Question 5
There is a linear-time algorithm for testing the planarity of finite graphs.
 A True B False
Data-Structures       Graphs
Question 5 Explanation:
Yes, Linear time algorithm is there for testing the planarity of finite graphs.
 Question 6
Every infinite cyclic group is isomorphic to the infinite cyclic group of intergers under addition.
 A True B False
Engineering-Mathematics       Sets-And-Relation
Question 6 Explanation:
True, every infinite cyclic group is isomorphic to the infinite cyclic group of integers under addition.
 Question 7
If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.
 A True B False
Data-Structures       Binary-Trees
Question 7 Explanation:

In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.
 Question 8
Regularity is preserved under the operation of string reversal.
 A True B False
Theory-of-Computation       Regular-Language
Question 8 Explanation:
Regular language is closed under reversal.
 Question 9
All subsets of regular sets are regular.
 A True B False
Theory-of-Computation       Regular-Language
Question 9 Explanation:
a*b* is regular but its subset anbn is not regular.
 Question 10
A minimal DFA that is equiavlent to an NDFA with n nodes has always 2n states.
 A True B False
Theory-of-Computation       Finite-Automata
Question 10 Explanation:
A minimal DFA is equivalent to a NDFA with n nodes has atmost 2n states and does not have always 2n states.
 Question 11
The intersection of two CFL's is also a CFL.
 A True B False
Theory-of-Computation       Context-Free-Language
Question 11 Explanation:
Context free language is not closed under intersection.
 Question 12
A is recursive if both A and its complement are accepted by Turing machines.
 A True B False
Theory-of-Computation       Turing Machines
Question 12 Explanation:
If A is decidable, then A and A' are accepted by Turing machine.
 Question 13
The total number of Boolean functions which can be realised with four variables is:
 A 4 B 17 C 256 D 65,536
Digital-Logic-Design       Boolean-Functions
Question 13 Explanation:
Total no. of Boolean functions which can be realized with four variables is:
 Question 14

 A 1111 1111 0000 0000 B 1111 0000 1111 000 C 1111 0001 0011 010 D 1010 1010 1010 1010
Digital-Logic-Design       Sequential-Circuits
Question 14 Explanation:
Let us suppose initially output of all JK flip flop is 1.
So we can draw below table to get the output Q3.

From the above table Q3 that is output is 1111 0001 0011 010.
 Question 15

 A B A⊕B⊕C C A⊕B D
Digital-Logic-Design       Multiplexer
Question 15 Explanation:
 Question 16
The most relevant addressing mode to write position-independent codes is:
 A Direct mode B Indirect mode C Relative mode D Indexed mode
Question 16 Explanation:
Relative mode since we can just change the content of base register, if we wish to relocate.
 Question 17
A microprogrammed control unit
 A Is faster than a hard-wired control unit. B Facilitates easy implementation of new instruction. C Is useful when very small programs are to be run. D Usually refers to the control unit of a microprocessor.
Computer-Organization       Micro-Programmed-Control-Unit
Question 17 Explanation:
In micro-programmed control unit we can add new instruction by changing the content of control memory.
 Question 18
The exponent of a floating-point number is represented in excess-N code so that:
 A The dynamic range is large. B The precision is high. C The smallest number is represented by all zeros. D Overflow is avoided.
Digital-Logic-Design       Number-Systems
Question 18 Explanation:
To avoid extra work, excess-N code is used so that all exponent can be represented in positive numbers, starting with 0.
 Question 19
On receiving an interrupt from a I/O device the CPU:
 A Halts for a predetermined time. B Hands over control of address bus and data bus to the interrupting device. C Branches off to the interrupt service routine immediately. D Branches off to the interrupt service routine after completion of the current instruction.
Computer-Organization       Interrupt
Question 19 Explanation:
On receiving an interrupt from a I/O device the CPU branches off to the interrupt service routine after completion of the current instruction.
 Question 20
The refreshing rate of dynamic RAMs is in the range of
 A 2 microseconds B 2 milliseconds C 50 milliseconds D 500 milliseconds
Digital-Logic-Design       DRAM
Question 20 Explanation:
During a 2 millisecond interval all dynamic RAM memory is refreshed.
 Question 21
In a compiler the module the checks every character of the source text is called:
 A The code generator. B The code optimiser. C The lexical analyser. D The syntax analyser.
Compiler-Design       Compilers
Question 21 Explanation:
Lexical analyzer phase checks every character of text to identify tokens.
 Question 22
A context-free grammar is ambiguous if:
 A The grammar contains useless non-terminals. B It produces more than one parse tree for some sentence. C Some production has two non terminals side by side on the right-hand side. D None of the above.
Theory-of-Computation       Contest-Free-Grammar
Question 22 Explanation:
An ambiguous grammar produces more than one parse tree for some string.
 Question 23
FORTRAN is a:
 A Regular language. B Context-free language. C Context-senstive language. D None of the above.
Theory-of-Computation       Identify-Class-Language
Question 23 Explanation:
Due to presence of some features FORTRAN cannot be handled by PDA.
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.
 Question 24
An operator precedence parser is a
 A Bottom-up parser. B Top-down parser. C Back tracking parser. D None of the above.
Compiler-Design       Parsers
Question 24 Explanation:
An operator precedence parser is a Bottom-up parser.
 Question 25
In a circular linked list oraganisation, insertion of a record involves modification of
 A One pointer. B Two pointers. C Multiple pointers. D No pointer.
Question 25 Explanation:
Suppose we have to insert node p after node q then
p → next = q → next
q → next = p
So, two pointers modifications.
 Question 26
A critical region is
 A One which is enclosed by a pair of P and V operations on semaphores. B A program segment that has not been proved bug-free. C A program segment that often causes unexpected system crashes. D A program segment where shared resources are accessed.
Operating-Systems       Process-Synchronization
Question 26 Explanation:
A critical region is a program segment where shared resources are accessed.
 Question 27
Using longer identifiers in a program will necessarily lead to:
 A Somewhat slower compilation B A program that is easier to understand C An incorrect program D None of the above
Compiler-Design       Compilers
Question 27 Explanation:
Lexical analyzer will take more time to recognize the longer identifiers.
 Question 28
Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1] respectively. Which of the following holds?
 A t1 = t2 B t1 > t2 C t1 < t2 D t1 = t2 + 5 log 5
Algorithms        Sorting
Question 28 Explanation:
Since both are in sorted order and no. of elements in second list is greater.
 Question 29

 A 3, 6 B 6, 7 C 3, 7 D None of the above.
Programming       Programming
Question 29 Explanation:
First procedure Q is called from the main procedure. Q has local variables x and y with values 3 and 4 respectively. This local variable y (value 4) is being parsed to procedure P during call, and received in local variable n inside procedure P. Now as P does not have any local definition for variable x, it will assign the evaluated value of (n+2)/(n-3), i.e., (4+2)/(4-3)=6 to the global variable x, which was previously 7. After the call of procedure P, procedure Q writes the value of local variable x which is still 3. Lastly, the main procedure writes the value of global variable x, which has been changed to 6 inside procedure P. So, the output will be 3, 6.
 Question 30

 A 3, 6 B 6, 7 C 3, 7 D None of the above
Programming       Programming
Question 30 Explanation:
The same sequence of statements will be executed using dynamic scoping. However, as there is no local definition of variable x in procedure P, it will consider the recent definition in the calling sequence, as P is being called from procedure Q, definition of x from Q will be changed to 6 from 3. Now, when Q writes local variables x, 6 will be printed. The write global variable x from main procedure will print 7 (as value of the global variable x has not been changed). So, the output will be 6, 7.
 Question 31
If a, b and c are constants, which of the following is a linear inequality?
 A ax + bcy = 0 B ax2 + cy2 = 21 C abx + a2y ≥ 15 D xy + ax ≥ 20
Engineering-Mathematics       Linear-Equation
Question 31 Explanation:
A) It is an equality.
B) Is not linear.
C) It is linear inequality.
D) Not linear.
 Question 32

 A All complex roots B At least one real root C Four pairs of imaginary roots D None of the above
Engineering-Mathematics       Polynomials
Question 32 Explanation:
Since, the polynomial has highest degree 7. So there are 7 roots possible for it.
Now suppose if an imaginary number a+bi is also root of this polynomial. That means there must be even number of complex root possible because, they occur in pair.
A) All complex root.
This is not possible. The polynomial has 7 roots and as I mention a polynomial should have been number of complex root and 7 is not even. So this option is wrong.
B) At last one real root.
This is possible. Since polynomial has 7 roots and only even number of complex root is possible, that means this polynomial has max 6 complex roots and hence minimum one real root. So, this option is correct.
C) Four pairs of imaginary roots.
4 pair means 8 complex root. But this polynomial can have atmost 7 roots. So, this option is also wrong.
 Question 33
A square matrix is singular whenever
 A The rows are linearly independent B The columns are linearly independent C The row are linearly dependent D None of the above
Engineering-Mathematics       Linear-Algebra
Question 33 Explanation:
When the rows are linearly dependent the determinant of the matrix becomes 0 hence in that case it will become singular matrix.
Hence, C is the correct option.
 Question 34
If f(xi) ⋅ f(xi+1) < 0 then
 A There must be a root of f(x) between xi and xi+1. B There need not be a root of f(x) between xi and xi+1. C There fourth derivative of f(x) with respect to x vanishes at xi. D The fourth derivative of f(x) with respect to x vanishes at xi+1.
Engineering-Mathematics       Polynomials
Question 34 Explanation:
As f(xi) ⋅ f(xi+1) < 0
means one of them is positive and one of them is negative, as their multiplication is negative.
So, when you draw the graph for f(x) where xi ≤ x ≤ xi+1.
Definitely f(x) will cut the x-axis. So there will definitely be a root of f(x) between xi and xi+1.
There are 34 questions to complete.