## GATE 1987

Question 1 |

In a microprocessor-based system, if a bus (DMA) request and an interrupt request arrive simultaneously, the microprocessor attends first to the bus request.

True. | |

False. |

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 3 |

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?

True | |

False |

Question 4 |

The union of two equivalence relations is also an equivalence relation.

True | |

False |

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 6 |

Every infinite cyclic group is isomorphic to the infinite cyclic group of integers under addition.

True | |

False |

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 |

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 9 |

All subsets of regular sets are regular.

True | |

False |

^{n}b

^{n}is not regular.

Question 10 |

A minimal DFA that is equivalent to an NDFA with n nodes has always 2^{n} states.

True | |

False |

^{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 12 |

A is recursive if both A and its complement are accepted by Turing machines.

True | |

False |

Question 13 |

The total number of Boolean functions which can be realized with four variables is:

4 | |

17 | |

256 | |

65,536 |

2

^{24}= 2

^{16}= 65,536

Question 14 |

The above circuit produces the output sequence:

1111 1111 0000 0000 | |

1111 0000 1111 000 | |

1111 0001 0011 010 | |

1010 1010 1010 1010 |

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 15 |

The output F of the below multiplexer circuit can be represented by

A⊕B⊕C | |

A⊕B | |

Question 16 |

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

Direct mode | |

Indirect mode | |

Relative mode | |

Indexed mode |

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 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 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 20 |

The refreshing rate of dynamic RAMs is in the range of

2 microseconds | |

2 milliseconds | |

50 milliseconds | |

500 milliseconds |

Question 21 |

In a compiler the module the checks every character of the source text is called:

The code generator. | |

The code optimizer. | |

The lexical analyser. | |

The syntax analyser. |

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 23 |

FORTRAN is a:

Regular language. | |

Context-free language. | |

Context-sensitive language. | |

None of the above. |

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 25 |

In a circular linked list organisation, insertion of a record involves modification of

One pointer. | |

Two pointers. | |

Multiple pointers. | |

No pointer. |

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 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 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 29 |

Study the following program written in a block-structured language:

Var x, y:interger; procedure P(n:interger); begin x:=(n+2)/(n-3); end; procedure Q Var x, y:interger; begin x:=3; y:=4; P(y); Write(x) __(1) end; begin x:=7; y:=8; Q; Write(x); __(2) end.

What will be printed by the write statements marked (1) and (2) in the program if the variables are statically scoped?

3, 6 | |

6, 7 | |

3, 7 | |

None of the above. |

Question 30 |

For the program given below what will be printed by the write statements marked (1) and (2) in the program if the variables are dynamically scoped?

Var x, y:interger; procedure P(n:interger); begin x := (n+2)/(n-3); end; procedure Q Var x, y:interger; begin x:=3; y:=4; P(y); Write(x); __(1) end; begin x:=7; y:=8; Q; Write(x); __(2) end.

3, 6 | |

6, 7 | |

3, 7 | |

None of the above |

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 |

B) Is not linear.

C) It is linear inequality.

D) Not linear.

Question 32 |

The equation

7x^{7}+ 14x^{6}+ 12x^{5}+ 12x^{3}+ 10x^{2}+ 5x + 7 = 0 has

All complex roots | |

At least one real root | |

Four pairs of imaginary roots | |

None of the above |

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 |

Hence, C is the correct option.

Question 34 |

If f(x_{i}) ⋅ f(x_{i+1}) < 0 then

There 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}. |

_{i}) ⋅ f(x

_{i+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 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}.