## GATE 2001

Question 1 |

Consider the following statements:

- S1: The sum of two singular n × n matrices may be non-singular

S2: The sum of two n × n non-singular matrices may be singular.

Which of the following statements is correct?

S1 and S2 are both true | |

S1 is true, S2 is false | |

S1 is false, S2 is true | |

S1 and S2 are both false |

Question 2 |

Consider the following relations:

- R1(a,b) iff (a+b) is even over the set of integers

R2(a,b) iff (a+b) is odd over the set of integers

R3(a,b) iff a.b > 0 over the set of non-zero rational numbers

R4(a,b) iff |a-b| <= 2 over the set of natural numbers

Which of the following statements is correct?

R1 and R2 are equivalence relations, R3 and R4 are not | |

R1 and R3 are equivalence relations, R2 and R4 are not | |

R1 and R4 are equivalence relations, R2 and R3 are not | |

R1, R2, R3 and R4 are all equivalence relations |

__R1__:

a+a = 2a

The set (a,a) is reflexive.

The set representation (a,a), (b,b) is also Symmetric.

The set representation is Transitive.

So, this is Equivalence.

__R2__:

a+a ≠ 2a

The (a,a) is non-reflexive.

__R3__:

a⋅a>0 → Reflexive

a⋅b>0 and b⋅a>0 → Symmetric

a⋅b>0, b⋅c>0 then c⋅a>0 → Transitive

The relation R3 is equivalence relation.

__R4__:

|a - a| ≤ 2, which is not possible, not Reflexive.

R1 & R3 are equivalence, R2 & R4 are not.

Question 3 |

Consider two well-formed formulas in prepositional logic

F1: P ⇒ ¬P F2: (P⇒¬P)∨(¬P⇒P)

Which of the following statements is correct?

F1 is satisfiable, F2 is valid | |

F1 unsatisfiable, F2 is satisfiable | |

F1 is unsatisfiable, F2 is valid | |

F1 and F2 are both satisfiable |

F1 is satisfiable; F2 is valid.

Question 4 |

Consider the following two statements:

- S1: {0

^{2n}|n≥1|} is a regular language

S2: {0

^{m}1

^{n}0

^{m+n}|m≥1 and n≥1|} is a regular language

Which of the following statements is correct?

Only S1 is correct | |

Only S2 is correct | |

Both S1 and S2 are correct | |

None of S1 and S2 is correct |

For S2, DFA is not possible which is not regular.

Question 5 |

Which of the following statements is true?

If a language is context free it can always be accepted by a deterministic push-down automaton | |

The union of two context free languages is context free | |

The intersection of two context free languages is context free | |

The complement of a context free language is context free |

Question 6 |

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

N ^{2} | |

2 ^{N} | |

2N | |

N! |

^{N}.

If NFA have two states {1}{2} = 2

Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 2

^{2}= 2

^{N}

Question 7 |

More than one word is put in one cache block to

exploit the temporal locality of reference in a program | |

exploit the spatial locality of reference in a program | |

reduce the miss penalty | |

none of the above |

The temporal locality refers to reuse of data elements with a smaller regular intervals.

Question 8 |

Which of the following statements is false?

Virtual memory implements the translation of a program’s address space into physical memory address space | |

Virtual memory allows each program to exceed the size of the primary memory | |

Virtual memory increases the degree of multiprogramming | |

Virtual memory reduces the context switching overhead |

Question 9 |

A low memory can be connected to 8085 by using

INTER | |

HOLD | |

READY |

Question 10 |

Suppose a processor does not have any stack pointer register. Which of the following statements is true?

It cannot have subroutine call instruction | |

It can have subroutine call instruction, but no nested subroutine calls | |

Nested subroutine calls are possible, but interrupts are not | |

All sequences of subroutine calls and also interrupts are possible |

Question 11 |

Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map?

xy+y'z | |

wx'y'+xy+xz | |

w'x+y'z+xy | |

xz+y |

⇒ y'z + xy

Question 12 |

A processor needs software interrupt to

test the interrupt system of the processor | |

implement co-routines | |

obtain system services which need execution of privileged instructions | |

return from subroutine |

Question 13 |

A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged

a hardware interrupt is needed | |

a software interrupt is needed | |

a privileged instruction (which does not generate an interrupt) is needed | |

a non-privileged instruction (which does not generate an interrupt is needed |

Question 14 |

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

O(n) | |

O(n log n) | |

O(n ^{2}) | |

O(n!) |

Question 15 |

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

i-1 | |

⌊i/2⌋ | |

⌈i/2⌉ | |

(i+1)/2 |

Left Child is at index: 2i

Right child is at index: 2*i+1

Question 16 |

Let f(n) = n^{2}logn and g(n) = n(logn)^{10} be two positive functions of n. Which of the following statements is correct?

f(n) = O(g(n) and g(n) ≠ O(f(n)) | |

g(n) = O(f(n) and f(n) ≠ O(g(n)) | |

f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) | |

f(n) = O(g(n)) and g(n) = O(f(n)) |

^{2}logn; g(n) = n(logn)

^{10}

Cancel nlogn from f(n), g(n)

f(n) = n; g(n) = (logn)

^{9}

n is too large than (logn)

^{9}

So f(n)! = O(g(n)) and g(n) = O(f(n))

Question 17 |

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

Assembly | |

Parsing | |

Relocation | |

Symbol resolution |