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

 A S1 and S2 are both true B S1 is true, S2 is false C S1 is false, S2 is true D S1 and S2 are both false
Engineering-Mathematics       Linear-Algebra
Question 1 Explanation: 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?

 A R1 and R2 are equivalence relations, R3 and R4 are not B R1 and R3 are equivalence relations, R2 and R4 are not C R1 and R4 are equivalence relations, R2 and R3 are not D R1, R2, R3 and R4 are all equivalence relations
Engineering-Mathematics       Sets-And-Relation
Question 2 Explanation:
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?

 A F1 is satisfiable, F2 is valid B F1 unsatisfiable, F2 is satisfiable C F1 is unsatisfiable, F2 is valid D F1 and F2 are both satisfiable
Engineering-Mathematics       Propositional-Logic
Question 3 Explanation: F1 is satisfiable; F2 is valid.
 Question 4

Consider the following two statements:

S1: {02n|n≥1|} is a regular language
S2: {0m1n0m+n|m≥1 and n≥1|} is a regular language

Which of the following statements is correct?

 A Only S1 is correct B Only S2 is correct C Both S1 and S2 are correct D None of S1 and S2 is correct
Theory-of-Computation       Regular Languge
Question 4 Explanation:
For S1 we can construct DFA. S1 represents the string contains even no. of 0's. So S1 is regular.
For S2, DFA is not possible which is not regular.
 Question 5

Which of the following statements is true?

 A If a language is context free it can always be accepted by a deterministic push-down automaton B The union of two context free languages is context free C The intersection of two context free languages is context free D The complement of a context free language is context free
Theory-of-Computation       Properties-of-Languages
Question 5 Explanation:
Context free languages closed under Union, concatenation and kleen star. But not close under intersection and complementation.
 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

 A N2 B 2N C 2N D N!
Theory-of-Computation       Finite-Automata
Question 6 Explanation:
If NFA contains N, then possible number of states in possible DFA is 2N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
 Question 7

More than one word is put in one cache block to

 A exploit the temporal locality of reference in a program B exploit the spatial locality of reference in a program C reduce the miss penalty D none of the above
Computer-Organization       Cache
Question 7 Explanation:
Spatial locality refers to the use of data elements within relatively close storage locations. To exploit the spatial locality, more than one word are put into cache block.
The temporal locality refers to reuse of data elements with a smaller regular intervals.
 Question 8

Which of the following statements is false?

 A Virtual memory implements the translation of a program’s address space into physical memory address space B Virtual memory allows each program to exceed the size of the primary memory C Virtual memory increases the degree of multiprogramming D Virtual memory reduces the context switching overhead
Operating-Systems       Virtual Memory
Question 8 Explanation:
In a system with virtual memory context switch includes extra overhead in switching of address spaces.
 Question 9

A low memory can be connected to 8085 by using

 A INTER B C HOLD D READY
Computer-Organization       Microprocessor
Question 9 Explanation:
Communication is only possible when READY signal is set. So a low memory can be connected to 8085 by using READY signal.
 Question 10

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

 A It cannot have subroutine call instruction B It can have subroutine call instruction, but no nested subroutine calls C Nested subroutine calls are possible, but interrupts are not D All sequences of subroutine calls and also interrupts are possible
Computer-Organization       Subroutines
Question 10 Explanation:
If stack pointer register is not available then activation records in the stack cannot be created. So it cannot have subroutine call instruction.
 Question 11

Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map? A xy+y'z B wx'y'+xy+xz C w'x+y'z+xy D xz+y
Digital-Logic-Design       K-Map
Question 11 Explanation: ⇒ y'z + xy
 Question 12

A processor needs software interrupt to

 A test the interrupt system of the processor B implement co-routines C obtain system services which need execution of privileged instructions D return from subroutine
Computer-Organization       Interrupt
Question 12 Explanation:
To execute privileged instructions, system services can be obtained using software interrupt.
 Question 13

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

 A a hardware interrupt is needed B a software interrupt is needed C a privileged instruction (which does not generate an interrupt) is needed D a non-privileged instruction (which does not generate an interrupt is needed
Computer-Organization       Interrupt
Question 13 Explanation:
For switching between privileged to non-privileged area, non-privileged instruction is used, without interrupt.
 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?

 A O(n) B O(n log n) C O(n2) D O(n!)
Algorithms        Sorting
Question 14 Explanation:
In worst case Randomized quicksort execution time complexity is same as quicksort.
 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

 A i-1 B ⌊i/2⌋ C ⌈i/2⌉ D (i+1)/2
Data-Structures       Heap-Tree
Question 15 Explanation:
Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1
 Question 16

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

 A f(n) = O(g(n) and g(n) ≠ O(f(n)) B g(n) = O(f(n) and f(n) ≠ O(g(n)) C f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) D f(n) = O(g(n)) and g(n) = O(f(n))
Algorithms        Time-Complexity
Question 16 Explanation:
f(n) = n2logn; 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

 A Assembly B Parsing C Relocation D Symbol resolution
Compiler-Design       Run-Time-Environments
Question 17 Explanation:
Relocation can change the assigned address of data and code in the program.
There are 17 questions to complete.

Register Now