## 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.

True.
| |

False. |

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.

True | |

False |

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?

True | |

False |

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.

True | |

False |

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.

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.

True | |

False |

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.

True | |

False |

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.

True | |

False |

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.

True | |

False |

Question 8 Explanation:

Regular language is closed under reversal.

Question 9 |

All subsets of regular sets are regular.

True | |

False |

Question 9 Explanation:

a*b* is regular but its subset a

^{n}b^{n}is not regular.Question 10 |

A minimal DFA that is equiavlent to an NDFA with n nodes has always 2

^{n}states.True | |

False |

Question 10 Explanation:

A minimal DFA is equivalent to a NDFA with n nodes has atmost 2

^{n}states and does not have always 2^{n}states.Question 11 |

The intersection of two CFL's is also a CFL.

True | |

False |

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.

True | |

False |

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:

4 | |

17 | |

256 | |

65,536 |

Question 13 Explanation:

Total no. of Boolean functions which can be realized with four variables is:

Question 14 |

1111 1111 0000 0000 | |

1111 0000 1111 000 | |

1111 0001 0011 010 | |

1010 1010 1010 1010 |

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 Q

From the above table Q

So, answer is (C).

So we can draw below table to get the output Q

_{3}.From the above table Q

_{3}that is output is 1111 0001 0011 010.So, answer is (C).

Question 16 |

The most relevant addressing mode to write position-independent codes is:

Direct mode | |

Indirect mode | |

Relative mode | |

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

Is faster than a hard-wired control unit. | |

Facilitates easy implementation of new instruction. | |

Is useful when very small programs are to be run. | |

Usually refers to the control unit of a microprocessor. |

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:

The dynamic range is large. | |

The precision is high. | |

The smallest number is represented by all zeros. | |

Overflow is avoided. |

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:

Halts for a predetermined time. | |

Hands over control of address bus and data bus to the interrupting device. | |

Branches off to the interrupt service routine immediately. | |

Branches off to the interrupt service routine after completion of the current instruction. |

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

2 microseconds | |

2 milliseconds | |

50 milliseconds | |

500 milliseconds |

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:

The code generator. | |

The code optimiser. | |

The lexical analyser. | |

The syntax analyser. |

Question 21 Explanation:

Lexical analyzer phase checks every character of text to identify tokens.

Question 22 |

A context-free grammar is ambiguous if:

The grammar contains useless non-terminals. | |

It produces more than one parse tree for some sentence. | |

Some production has two non terminals side by side on the right-hand side. | |

None of the above. |

Question 22 Explanation:

An ambiguous grammar produces more than one parse tree for some string.

Question 23 |

FORTRAN is a:

Regular language. | |

Context-free language. | |

Context-senstive language. | |

None of the above. |

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.

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

Bottom-up parser. | |

Top-down parser. | |

Back tracking parser. | |

None of the above. |

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

One pointer. | |

Two pointers. | |

Multiple pointers. | |

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.

p → next = q → next

q → next = p

So, two pointers modifications.

Question 26 |

A critical region is

One which is enclosed by a pair of P and V operations on semaphores. | |

A program segment that has not been proved bug-free. | |

A program segment that often causes unexpected system crashes. | |

A program segment where shared resources are accessed. |

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:

Somewhat slower compilation | |

A program that is easier to understand | |

An incorrect program | |

None of the above |

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 t

_{1}and t_{2}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?t _{1} = t_{2} | |

t _{1} > t_{2} | |

t _{1} < t_{2} | |

t _{1} = t_{2} + 5 log 5 |

Question 28 Explanation:

Since both are in sorted order and no. of elements in second list is greater.

Question 29 |

3, 6 | |

6, 7 | |

3, 7 | |

None of the above. |

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 |

3, 6 | |

6, 7 | |

3, 7 | |

None of the above |

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?

ax + bcy = 0 | |

ax ^{2} + cy^{2} = 21 | |

abx + a ^{2}y ≥ 15 | |

xy + ax ≥ 20 |

Question 31 Explanation:

A) It is an equality.

B) Is not linear.

C) It is linear inequality.

D) Not linear.

B) Is not linear.

C) It is linear inequality.

D) Not linear.

Question 32 |

All complex roots | |

At least one real root | |

Four pairs of imaginary roots | |

None of the above |

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.

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

The rows are linearly independent | |

The columns are linearly independent | |

The row are linearly dependent | |

None of the above |

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.

Hence, C is the correct option.

Question 34 |

If f(x

_{i}) ⋅ f(x_{i+1}) < 0 thenThere must be a root of f(x) between x _{i} and x_{i+1}. | |

There need not be a root of f(x) between x _{i} and x_{i+1}. | |

There fourth derivative of f(x) with respect to x vanishes at x _{i}. | |

The fourth derivative of f(x) with respect to x vanishes at x _{i+1}. |

Question 34 Explanation:

As f(x

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 x

Definitely f(x) will cut the x-axis. So there will definitely be a root of f(x) between x

_{i}) ⋅ f(x_{i+1}) < 0means 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 x

_{i}≤ x ≤ x_{i+1}.Definitely f(x) will cut the x-axis. So there will definitely be a root of f(x) between x

_{i}and x_{i+1}.
There are 34 questions to complete.