Gate-1997

Question 1

The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow?

A
0.3
B
0.25
C
0.35
D
0.4
Question 1 Explanation: 
P(Today) = 0.5
P(Tomorrow) = 0.6
P(T∪To) = 0.7
P(T∩To) = P(T) + P(To) - P(T∪To)
= 0.5 + 0.6 - 0.07
= 1.1 - 0.7
= 0.4
Question 2
The Newton-Raphson method is used to find the root of the equation x2 − 2 = 0. If the iterations are started form –1, the iterations will
A
converge to -1
B
converge to √2
C
converge to - √2
D
not converge
Question 2 Explanation: 
Question 3
       
A
11
B
-48
C
0
D
-24
Question 3 Explanation: 
Determinant of given matrix = 6×2×4×(-1) = -48
Question 4
The concatenation of two lists is to be performed on O(1) time. Which of the following implementations of a list should be used?
A
Singly linked list
B
Doubly linked list
C
Circular doubly linked list
D
Array implementation of list
Question 4 Explanation: 
In circular doubly linked list concatenation of two lists is to be performed on O(1) time.
Question 5
 
A
A – 2 B – 4 C – 1 D – 3
B
A – 3 B – 4 C – 1 D – 2
C
A – 3 B – 4 C – 2 D – 1
D
A – 4 B – 1 C – 2 D – 3
Question 5 Explanation: 
All pairs shortest path - Dynamic Programming
Quick sort - Divide and Conquer
Minimum weight Spanning tree - Greedy
Connected components - Depth-First search
Question 6
 
A
‘⊕’ is left associative while ‘*’ is right associative
B
Both ‘⊕’ and ‘*’ is left associative
C
‘⊕’ is right associative while ‘*’ is left associative
D
None of the above
Question 6 Explanation: 

⊕ is left associative.
* is right associative.
Question 7
Which of the following is essential for converting an infix expression to the postfix form efficiently?
A
An operator stack
B
An operand stack
C
An operand stack and an operator stack
D
A parse tree
Question 7 Explanation: 
An operator stack ⇒ Infix to (Postfix or Prefix)
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
Question 8

A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which one of the following is true?

A
A compiler using static memory allocation can be written for L
B
A compiler cannot be written for L; an interpreter must be used
C
A compiler using dynamic memory allocation can be written for L
D
None of the above
Question 8 Explanation: 
Compiler is use dynamic memory allocation then the memory will be allocated to an array at runtime.
Question 9
The conditional expansion facility of macro processor is provided to
A
test a condition during the execution of the expanded program
B
to expand certain model statements depending upon the value of a condition during the execution of the expanded program
C
to implement recursion
D
to expand certain model statements depending upon the value of a condition during the process of macro expansion
Question 9 Explanation: 
Macro is expanded during the process of Macro expansion.
Question 10
Heap allocation is required for languages
A
that support recursion
B
that support dynamic data structures
C
that use dynamic scope rules
D
None of the above
Question 10 Explanation: 
Heap allocation is required for languages that support dynamic data structures.
Question 11
   
A
B
x
C
0
D
1
Question 11 Explanation: 
Question 12
RST 7.5 interrupt in 8085 microprocessor executes service routing from interrupt vector location
A
0000H
B
0075H
C
003CH
D
0034H
Question 12 Explanation: 
RST7.5 then location is = 7.5*8 = 60 (8085 is 8 bit processor)
→ 60 in hexa decimal is 003CH.
Question 13
Purpose of a start bit in RS 232 serial communication protocol is
A
to synchronize receiver for receiving every byte
B
to synchronize receiver for receiving a sequence of bytes
C
a parity bit
D
to synchronize receiver for receiving the last byte
Question 13 Explanation: 
RS-232 needs a start before each byte transmission for synchronization.
Question 14
 
A
A – 4 B – 3 C – 1 D – 2
B
A – 2 B – 1 C – 3 D – 4
C
A – 4 B – 3 C – 2 D – 1
D
A – 2 B – 3 C – 4 D – 1
Question 14 Explanation: 
DMA I/O → Disk
Cache → High speed RAM
Interrupt I/O → Printer
Condition code register → ALU
Question 15
 
A
proportional to N
B
proportional to log N
C
a constant
D
None of the above
Question 16

Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by n*m = maximum (n,m). which of the following statements is true for (Z,*)?

A
(Z,*) is a monoid
B
(Z,*) is an Abelian group
C
(Z,*) is a group
D
None of the above
Question 16 Explanation: 
Semigroup - Closed and associative
Monoid - Closed, Associative and has an identity
Group - Monoid with inverse
Abelian group - Group with commutative property
Go through with given:
Closure: Yes.
(m*n = max(m,n)) output is either m or n whichever is maximum since m,n belongs z. The result of the binary operation also belongs to z. So given is satisfying closure property.
Associative: Yes.
The output is max among the elements and it is associative.
Identity: No.
We don't have single unique element for all the elements which is less than all the elements.
Given one is semigroup only.
Question 17
Which of the following propositions is a tautology?
A
(p ∨ q) → p
B
p ∨ (q → p)
C
p ∨ (p → q)
D
p → (p → q)
Question 17 Explanation: 
Question 18
 
A
2
B
3
C
0
D
1
Question 18 Explanation: 
g, c, d are the complements of e.
No. of complements = 3
e∨g = a and e∧g = f
e∨c = a and e∧c = f
e∨d = a and e∧d = f
Question 19
Given Σ = {a,b}, which one of the following sets is not countable?
A
Set of all strings over Σ
B
Set of all languages over Σ
C
Set of all regular languages over Σ
D
Set of all languages over Σ accepted by Turing machines
Question 19 Explanation: 
Uncountable: Set of all languages over Σ is uncountable.
Question 20
Locality of reference implies that the page reference being made by a process
A
will always be to the page used in the previous page reference
B
is likely to be to one of the pages used in the last few page references
C
will always be to one of the pages existing in memory
D
will always lead to a page fault
Question 20 Explanation: 
Locality of reference is also called as principle of locality. There are three different principle of locality:
(1) Temporal locality
(2) Spatial locality
(3) Sequential locality
→ In programs related data are stored in consecutive locations and loops in same locations are used repeatedly.
Question 21
 
A
A – 3 B – 4 C – 2 D – 1
B
A – 4 B – 3 C – 2 D – 1
C
A – 2 B – 4 C – 1 D – 3
D
A – 3 B – 4 C – 3 D – 2
Question 21 Explanation: 
Disk scheduling - SCAN
Batch processing - FIFO
Time sharing - Round Robin
Interrupt processing - LIFO
Question 22
I/O redirection
A
implies changing the name of a file
B
can be employed to use an existing file as input file for a program
C
implies connection 2 programs through a pipe
D
None of the above
Question 22 Explanation: 
Redirection is known as capturing output from a file, command, program (or) even code block within a script and sending it as input to another file, command, program (or) script.
Question 23
When an interrupt occurs, an operating system
A
ignores the interrupt
B
always changes state of interrupted process after processing the interrupt
C
always resumes execution of interrupted process after processing the interrupt
D
may change state of interrupted process to 'blocked’ and schedule another process
Question 23 Explanation: 
Option A: Based on the priority.
Option B: Not always.
Option C: Not always. If some high priority interrupt comes during execution of current interrupt then it fails.
Option D: It is True always.
Question 24
Thrashing
A
reduces page I/O
B
decreases the degree of multiprogramming
C
implies excessive page I/O
D
improve the system performance
Question 24 Explanation: 
Thrashing implies excessive page I/O.
Question 25
Dirty bit for a page in a page table
A
helps avoid unnecessary writes on a paging device
B
helps maintain LRU information
C
allows only read on a page
D
None of the above
Question 25 Explanation: 
The dirty bit allows for a performance optimization i.e., Dirty bit for a page in a page table helps to avoid unnecessary writes on a paging device.
Question 26
What is the maximum value of the function f(x) = 2x2 - 2x + 6 in the interval [0,2]?
A
6
B
10
C
12
D
5.5
Question 26 Explanation: 
For f(x) to be maximum
f'(x) = 4x - 2 = 0
⇒ x = 1/2
So at x = 1/2, f(x) is an extremum (either maximum or minimum).
f(2) = 2(2)2 - 2(2) + 6 = 10
f(1/2) = 2 × (1/2)2 - 2 × 1/2 + 6 = 5.5
f(0) = 6
So, the maximum value is at x=2 which is 10 as there are no other extremum for the given function.
Question 27

Let a = (aij) be an n-rowed square matrix and I12 be the matrix obtained by interchanging the first and second rows of the n-rowed Identify matrix. Then AI12 is such that its first

A
row is the same as its second row
B
row is the same as the second row of A
C
column is the same as the second column of A
D
row is all zero
Question 27 Explanation: 
Let A be 3×3 matrix and I12 be matrix obtained by interchanging the first and second rows of the 3-rowed Identity matrix.

So, we can see that column 1 and 2 got interchanged.
Question 28
Using a forward Euler method to solve y′′(t) = f(t), y(0), y′′(0) = 0 with a step size of h, we obtain the following values of y in the first four iterations:
A
0, hf(0), h(f(0) + f(h)) and h(f(0) + f(h) = f(2h))
B
0, 0 h2f(0) and 2h2f(0) + f(h)
C
0, 0, h2f(0) 3h2f(0)
D
0, 0, hf(0) + h2f(0) and hf(0) + h2f(0) + hf(h)
Question 28 Explanation: 
Note: Out of syllabus.
Question 29
A polynomial p(x) is such that p(0) = 5, p(1) = 4, p(2) = 9 and p(3) = 20. The minimum degree it can have is
A
1
B
2
C
3
D
4
Question 29 Explanation: 
Lets take p(x) = ax + b
p(0) = 5 ⇒ b = 5
p(1) = 4 ⇒ a+b = 4 ⇒ a = -1
p(2) = 9 ⇒ 40+b = 9 ⇒ -4+5 = 9, which is false.
So degree 1 is not possible.
Lets take p(x) = ax2 + bx +c
p(0) = 5 ⇒ c = 5
p(1) = 4 ⇒ a+b+c = 4 ⇒ a+b = -1 -----(1)
p(2) = 9 ⇒ 4a+2b+c = 9 ⇒ 2a+b = 2 -----(2)
(2) - (1)
⇒ a = 3, b = -1-1 = -4
p(3) = 20 ⇒ 9a+3b+c = 20
⇒ 27-12+5 = 20
⇒ 20 = 20, True
Hence, minimum degree it can have.
Question 30
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?
A
5 3 1 2 4 7 8 6
B
5 3 1 2 6 4 8 7
C
5 3 2 4 1 6 7 8
D
5 3 1 2 4 7 6 8
Question 30 Explanation: 
Preorder traversal means (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.
Question 31
 
A
B
T(n) = O(n)
C
T(n) = O(log n)
D
None of the above
Question 31 Explanation: 
Apply Master's theorem.
Question 32
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
A
non-increasing order
B
non-decreasing order
C
strictly increasing order
D
strictly decreasing order
Question 32 Explanation: 
In stack last element pushed should be popped first. And in priority queue Q, minimum element is given the highest priority. So whenever we will call DELETEMIN(Q), it will pop the elementwith min value. So we can conclude that the minimum element should be inserted last or the insertion should be in decreasing order. And also it should be in strictly decreasing order, because for two elements with equal value the priority queue will pick any of one randomly which should not be the case in the stack.
Question 33
     
A
x or A, y, x of B and z in S1 and x of B, y and i in S2
B
x or B, y and z in S1 and x of B, i and z in S2
C
x or B, z and y in S1 and x of A, i and y in S2
D
None of the above
Question 33 Explanation: 
Note: Out of syllabus.
Question 34
 
A
‘op’ is ’+’ or ‘*’
B
‘op’ is ’↑’ or ‘*’
C
‘op’ is ’↑’ or ‘+’
D
not possible to evaluate without storing
Question 34 Explanation: 
Lets say, the expression is one of the below:
(a*b)*c + d
(a*b)*c * d
(a*b)*c ∧ d
In any case, brackets has the highest priority always. So I have to compute brackets first. Now, for + and *, I can do the rest of the operation and save results in the same register. But for exponentiation, I have to store the result of a*b, then do the computation of c∧d, then multiply these two results.
Hence, (A) is correct.
Question 35

A
60
B
100
C
600
D
10000
Question 35 Explanation: 
Note: Out of syllabus.
Question 36
 
A
B
xz is a minterm of f
C
xz is an implicant of f
D
y is a prime implicant of f
Question 36 Explanation: 
In sum of terms,any term is an implicant because it implies the function. So xz is an implicant and hence 'C' is the answer.
Question 37
 
A
7AH
B
80H
C
50H
D
22H
Question 37 Explanation: 
Note: Out of syllabus.
Question 38
 
A
9
B
5
C
8
D
None of the above
Question 38 Explanation: 
(a) This is a vertical microprogramming because at any given time atmost one microoperations will be activated.
So, no. of bits required
⌈log2 (3)⌉ = 2
(b) This is a horizontal micro-programming because at any given time atmost six microoperations will be activated.
So, no. of bits required = 6
So, total minimum no. of bits required = 6+2 = 8
Question 39
   
A
10
B
8
C
5
D
6
Question 39 Explanation: 
Question 40
 
A
Σ9,10
B
Σ9
C
Σ1,8,9
D
Σ8,10,15
Question 40 Explanation: 
f = f1⋅f2 + f3
Since, f1 and f2 are in canonical sum of products form, f1⋅f2 will only contain their common terms that is f1⋅f2 = Σ8.
Now,
Σ8 + f3 = Σ8,9
So, f3= Σ9
Question 41
 
A
n!
B
n+2
C
n
D
1
Question 41 Explanation: 
To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently between any ai and aj, there is no relation.
So for every ai, aj we have to add either (ai, aj) or (aj, ai in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways. So answer is (A).
Question 42
Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i - j| = 8 or |i - j| = 12. The number of connected components in G is  
A
8
B
4
C
12
D
25
Question 42 Explanation: 
From the description, it is clear that vertices are connected as follows:
1 — 9 — 17 — ......... — 97
2 — 10 — 18 — ......... — 98
3 — 11 — 19 — ......... — 99
4 — 12 — 20 — ......... — 100
5 — 13 — 21 — ......... — 93
6 — 14 — 22 — ......... — 94
7 — 15 — 23 — ......... — 95
8 — 16 — 24 — ......... — 96
We have covered all vertices using 8 vertex sets considering only |i - j| = 8. Using |i - j| = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
Question 43
The number of equivalence relations of the set {1,2,3,4} is
A
15
B
16
C
24
D
4
Question 43 Explanation: 
The no. of equivalence relation with 4 elements is 15.
Question 44
Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
A
0*(1+0)*
B
0*1010*
C
0*1*01
D
0(10+1)*
Question 44 Explanation: 
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 45
Which one of the following is not decidable?
A
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
Question 45 Explanation: 
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 46
 
A
{w⊂wR|w ∈ {a,b}*}
B
{wwR|w ∈ {a,b,c}*}
C
{anbncn|n ≥ 0}
D
{w|w is a palindrome over {a,b,c}}
Question 46 Explanation: 
(A) w⊂wR, can be realized using DPDA because we know the center of the string that is c here.
(B) wwR, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {anbncn | n ≥ 0} is CSL.
(D) {w | w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
Question 47
An operating system contains 3 user processes each requiring 2 units of resource R. the minimum number of units of r such that no deadlocks will ever arise is
A
3
B
5
C
4
D
6
Question 47 Explanation: 
For the system to cause deadlock give each process 1 resource less than they require. Since in this case they require 2 resource each, so just give them 1 resource each. So if at max if 3 resource will be available then there can be deadlock. So by adding one more resource deadlock will never occur. So in total minimum 4 resources are required so that deadlock will never occur.
Question 48

A
1
B
2
C
3
D
None of the above
Question 48 Explanation: 
Since the both code (i.e., P1 to P9 and P10) can be executed any number of times and code for P10 is
repeat
{
V(mutex)
C.S.
V(mutex)
}
forever
Now, let me say P1 is in CS then P1 is in CS
then P10 comes and executes CS (upon mutex).
Now, P2 comes (down on mutex).
Now P10 moves out of CS (again binary semaphore will be 1).
Now P3 comes (down on mutex).
Now P10 comes (upon mutex).
Now P4 comes (down mutex).
⁞ So, if we take P10 'in' and 'out' of CS recursively, all 10 processes can be in CS at same time using binary semaphore only.
Question 49
     
A
in first normal form but not in second normal form
B
in second normal form but not in third normal form
C
in third normal form
D
None of the above
Question 49 Explanation: 
Candidate key is ab.
Since all a, b, c, d are atomic. So the relation is in 1NF.
Checking the FD's
a → c
b → d
We can see that there is partial dependencies. So it is not 2NF.
So answer is option (A).
Question 50
 
A
None of (a), (b), (c) or (d) can cause its violation
B
All of (a), (b), (c) and (d) can cause its violation
C
Both (a) and (d) can cause its violation
D
Both (b) and (c) can cause its violation
Question 50 Explanation: 
Let take example:

Here 'd' is the foreign key of S and let 'a' is the primary key of R.
(A) Insertion into R: will cause no violation.
(B) Insertion into S: may cause violation because there may not be entry of the tuple in relation R. Example entry of 〈S4, __, __〉 is not allowed.
(C) Delete from R: may cause violation. For example, deletion of tuple 〈S2, __, __〉 will cause violation as there is entry of S2 in the foreign key table.
(D) Delete from S: will cause no violation as it does not result inconsistency.
There are 50 questions to complete.