Gate1997
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?
0.3  
0.25  
0.35  
0.4 
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 
converge to 1  
converge to √2  
converge to  √2  
not converge 
Question 4 
Singly linked list  
Doubly linked list  
Circular doubly linked list  
Array implementation of list 
Question 5 
A – 2 B – 4 C – 1 D – 3  
A – 3 B – 4 C – 1 D – 2  
A – 3 B – 4 C – 2 D – 1  
A – 4 B – 1 C – 2 D – 3 
Quick sort  Divide and Conquer
Minimum weight Spanning tree  Greedy
Connected components  DepthFirst search
Question 6 
‘⊕’ is left associative while ‘*’ is right associative  
Both ‘⊕’ and ‘*’ is left associative  
‘⊕’ is right associative while ‘*’ is left associative  
None of the above 
⊕ is left associative.
* is right associative.
Question 7 
An operator stack  
An operand stack  
An operand stack and an operator stack  
A parse tree

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 compiler using static memory allocation can be written for L  
A compiler cannot be written for L; an interpreter must be used  
A compiler using dynamic memory allocation can be written for L  
None of the above 
Question 9 
test a condition during the execution of the expanded program  
to expand certain model statements depending upon the value of a condition during the execution of the expanded program  
to implement recursion  
to expand certain model statements depending upon the value of a condition during the process of macro expansion 
Question 10 
that support recursion  
that support dynamic data structures  
that use dynamic scope rules  
None of the above 
Question 12 
0000H  
0075H  
003CH  
0034H 
→ 60 in hexa decimal is 003CH.
Question 13 
to synchronize receiver for receiving every byte  
to synchronize receiver for receiving a sequence of bytes  
a parity bit  
to synchronize receiver for receiving the last byte 
Question 14 
A – 4 B – 3 C – 1 D – 2  
A – 2 B – 1 C – 3 D – 4
 
A – 4 B – 3 C – 2 D – 1  
A – 2 B – 3 C – 4 D – 1 
Cache → High speed RAM
Interrupt I/O → Printer
Condition code register → ALU
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,*)?
(Z,*) is a monoid  
(Z,*) is an Abelian group  
(Z,*) is a group  
None of the above 
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 
(p ∨ q) → p  
p ∨ (q → p)  
p ∨ (p → q)  
p → (p → q) 
Question 18 
2  
3  
0  
1 
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 
Set of all strings over Σ  
Set of all languages over Σ  
Set of all regular languages over Σ  
Set of all languages over Σ accepted by Turing machines 
Question 20 
will always be to the page used in the previous page reference  
is likely to be to one of the pages used in the last few page references  
will always be to one of the pages existing in memory  
will always lead to a page fault 
(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 – 3 B – 4 C – 2 D – 1  
A – 4 B – 3 C – 2 D – 1  
A – 2 B – 4 C – 1 D – 3  
A – 3 B – 4 C – 3 D – 2 
Batch processing  FIFO
Time sharing  Round Robin
Interrupt processing  LIFO
Question 22 
implies changing the name of a file  
can be employed to use an existing file as input file for a program  
implies connection 2 programs through a pipe  
None of the above

Question 23 
ignores the interrupt  
always changes state of interrupted process after processing the interrupt  
always resumes execution of interrupted process after processing the interrupt
 
may change state of interrupted process to 'blocked’ and schedule another process

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 
reduces page I/O  
decreases the degree of multiprogramming  
implies excessive page I/O  
improve the system performance 
Question 25 
helps avoid unnecessary writes on a paging device  
helps maintain LRU information  
allows only read on a page  
None of the above 
Question 26 
6  
10  
12  
5.5 
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 = (a_{ij}) be an nrowed square matrix and I_{12} be the matrix obtained by interchanging the first and second rows of the nrowed Identify matrix. Then AI_{12} is such that its first
row is the same as its second row
 
row is the same as the second row of A  
column is the same as the second column of A  
row is all zero 
So, we can see that column 1 and 2 got interchanged.
Question 28 
0, hf(0), h(f(0) + f(h)) and h(f(0) + f(h) = f(2h))  
0, 0 h^{2}f(0) and 2h^{2}f(0) + f(h)  
0, 0, h^{2}f(0) 3h^{2}f(0)  
0, 0, hf(0) + h^{2}f(0) and hf(0) + h^{2}f(0) + hf(h) 
Question 29 
1  
2  
3  
4 
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) = ax^{2} + 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 = 11 = 4
p(3) = 20 ⇒ 9a+3b+c = 20
⇒ 2712+5 = 20
⇒ 20 = 20, True
Hence, minimum degree it can have.
Question 30 
5 3 1 2 4 7 8 6  
5 3 1 2 6 4 8 7  
5 3 2 4 1 6 7 8  
5 3 1 2 4 7 6 8 
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Question 31 
T(n) = O(n)  
T(n) = O(log n)  
None of the above 
Question 32 
nonincreasing order  
nondecreasing order  
strictly increasing order  
strictly decreasing order 
Question 33 
x or A, y, x of B and z in S1 and x of B, y and i in S2
 
x or B, y and z in S1 and x of B, i and z in S2  
x or B, z and y in S1 and x of A, i and y in S2
 
None of the above 
Question 34 
‘op’ is ’+’ or ‘*’  
‘op’ is ’↑’ or ‘*’  
‘op’ is ’↑’ or ‘+’  
not possible to evaluate without storing 
(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 36 
xz is a minterm of f  
xz is an implicant of f  
y is a prime implicant of f 
Question 38 
9  
5  
8  
None of the above 
So, no. of bits required
⌈log_{2} (3)⌉ = 2
(b) This is a horizontal microprogramming 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 40 
Σ9,10  
Σ9  
Σ1,8,9  
Σ8,10,15 
Since, f_{1} and f_{2} are in canonical sum of products form, f_{1}⋅f_{2} will only contain their common terms that is f_{1}⋅f_{2} = Σ8.
Now,
Σ8 + f_{3} = Σ8,9
So, f_{3}= Σ9
Question 41 
n!  
n+2  
n  
1 
So for every a_{i}, a_{j} we have to add either (a_{i}, a_{j}) or (a_{j}, a_{i} 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 
8  
4  
12  
25 
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 
15  
16  
24  
4 
Question 44 
0*(1+0)*  
0*1010*  
0*1*01  
0(10+1)* 
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 45 
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps  
Equivalence of two given Turing machines  
Language accepted by a given finite state machine is not empty  
Language generated by a context free grammar is non empty 
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 
{w⊂w^{R}w ∈ {a,b}*}  
{ww^{R}w ∈ {a,b,c}*}  
{a^{n}b^{n}c^{n}n ≥ 0}  
{ww is a palindrome over {a,b,c}} 
(B) ww^{R}, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {a^{n}b^{n}c^{n}  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 
3  
5  
4  
6 
Question 48 
1  
2  
3  
None of the above 
repeat
{
V(mutex)
C.S.
V(mutex)
}
forever
Now, let me say P_{1} is in CS then P_{1} is in CS
then P_{10} comes and executes CS (upon mutex).
Now, P_{2} comes (down on mutex).
Now P_{10} moves out of CS (again binary semaphore will be 1).
Now P_{3} comes (down on mutex).
Now P_{10} comes (upon mutex).
Now P_{4} comes (down mutex).
⁞ So, if we take P_{10} 'in' and 'out' of CS recursively, all 10 processes can be in CS at same time using binary semaphore only.
Question 49 
in first normal form but not in second normal form  
in second normal form but not in third normal form  
in third normal form  
None of the above 
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 
None of (a), (b), (c) or (d) can cause its violation  
All of (a), (b), (c) and (d) can cause its violation  
Both (a) and (d) can cause its violation  
Both (b) and (c) can cause its violation

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 〈S_{4}, __, __〉 is not allowed.
(C) Delete from R: may cause violation. For example, deletion of tuple 〈S_{2}, __, __〉 will cause violation as there is entry of S_{2} in the foreign key table.
(D) Delete from S: will cause no violation as it does not result inconsistency.