Gate1996
Question 1 
Let A and B be sets and let A^{c} and B^{c} denote the complements of the sets A and
B. The set (A – B) ∪ (B  A) ∪ (A∩B) is equal to
A ∪ B  
A^{c} ∪ B^{c}  
A ∩ B  
A^{c} ∩ B^{c} 
Question 1 Explanation:
(A – B) ∪ (B  A) ∪ (A∩B)
(A  B) = 1
(B  A) = 2
(A∩B) = 3
A∪B = (1∪2∪3)
(A – B) ∪ (B  A) ∪ (A∩B) = 1∪2∪3 = (A∪B)
(A  B) = 1
(B  A) = 2
(A∩B) = 3
A∪B = (1∪2∪3)
(A – B) ∪ (B  A) ∪ (A∩B) = 1∪2∪3 = (A∪B)
Question 2 
Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y.
Number of edge as in the Hasse diagram of (X,≤) is
3  
4  
9  
None of the above 
Question 2 Explanation:
No. of edges = 4
Question 3 
Suppose X and Y are sets and X Y and are their respective cardinalities. It is given that there are exactly 97 functions from X to Y. from this one can conclude that
X = 1, Y = 97  
X = 97, Y = 1  
X = 97, Y = 97  
None of the above 
Question 3 Explanation:
From the given information we can write,
Y^{X} = 97
→ Option A only satisfies.
Y^{X} = 97
→ Option A only satisfies.
Question 4 
Which of the following statements is false?
The set of rational numbers is an abelian group under addition.  
The set of integers in an abelian group under addition.  
The set of rational numbers form an abelian group under multiplication.  
The set of real numbers excluding zero in an abelian group under multiplication.

Question 4 Explanation:
Rational number consists of number '0'. If 0 is present in a set inverse is not possible under multiplication.
Question 5 
Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is
Question 5 Explanation:
1  no. 6 on both dice
1  (5/6 × 5/6) = 1  (25/36) = 11/36
1  (5/6 × 5/6) = 1  (25/36) = 11/36
Question 6 
The formula used to compute an approximation for the second derivative of a function f at a point X_{0} is
Question 6 Explanation:
The formula which is used to compute the second derivation of a function f at point X is
Question 7 
Let Ax = b be a system of linear equations where A is an m × n matrix and b is a m × 1 column vector and X is a n × 1 column vector of unknows. Which of the following is false?
The system has a solution if and only if, both A and the augmented matrix [A b] have the same rank.
 
If m < n and b is the zero vector, then the system has infinitely many solutions.  
If m = n and b is nonzero vector, then the system has a unique solution.  
The system will have only a trivial solution when m = n, b is the zero vector and rank (A) = n. 
Question 7 Explanation:
→ It belongs to linear nonhomogeneous equations. So by having m=n, we can't say that it will have unique solution.
→ Solution can be depends on rank of matrix A and matrix [A B].
→ If rank[A] = rank[A B] then it can have solution otherwise no solution.
→ Solution can be depends on rank of matrix A and matrix [A B].
→ If rank[A] = rank[A B] then it can have solution otherwise no solution.
Question 8 
(i) and (ii)  
(ii) and (iii)  
(i) and (iii)  
(iii) and (iv) 
Question 8 Explanation:
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
In these two, we have any no. of 0's as well as null.
Question 9 
Which of the following statements is false?
The Halting problem of Turing machines is undecidable.  
Determining whether a contextfree grammar is ambiguous is undecidbale.  
Given two arbitrary contextfree grammars G1 and G2 it is undecidable whether L(G1) = L(G2).  
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2). 
Question 9 Explanation:
Equivalenceof regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1^{st} for CSL and REC.
→ None for RE.
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1^{st} for CSL and REC.
→ None for RE.
Question 10 
Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?
L = {xx has an equal number of a's and b's } is regular  
L = {a^{n}b^{n}n≥1} is regular  
L = {xx has more a's and b's} is regular  
L = {a^{m}b^{n}m ≥ 1, n ≥ 1} is regular 
Question 10 Explanation:
L = {a^{m}b^{n}m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Here, m and n are independent.
So 'L' Is Regular.
Question 12 
(ii) and (iii) are true  
(i) and (ii) are true  
(iii) and (iv) are true  
(ii) and (iv) are true 
Question 12 Explanation:
(i) FIFO computation efficiently supported by queues.
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer: A
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer: A
Question 13 
An advantage of chained hash table (external hashing) over the open addressing
scheme is
Worst case complexity of search operations is less?  
Space used is less  
Deletion is easier  
None of the above 
Question 13 Explanation:
In chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing can be postponed for longer time.
Question 14 
1  
3  
7  
8 
Question 14 Explanation:
a, b, c are going to unbalance.
Question 15 
Which of the following sequences denotes the post order traversal sequence of
the tree of question 14?
f e g c d b a  
g c b d a f e  
g c d b f e a  
f e d g c b a 
Question 15 Explanation:
Postorder:
Left → Right → Root
g c d b f e a
Left → Right → Root
g c d b f e a
Question 16 
Relative mode of addressing is most relevant to writing
coroutines  
position – independent code  
shareable code  
interrupt handlers 
Question 16 Explanation:
The main advantage of PC relative addressing is that code may be position independent, i.e., it can be loaded anywhere in memory without the need to adjust any address.
Question 17 
1, 2, 1, 2  
2, 1, 2, 1  
2, 1, 1, 2  
1, 2, 2, 2 
Question 17 Explanation:
The functionalities from pass 1 and pass 2 are:
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Question 18 
a batch operating system  
an operating system with a preemptive scheduler  
an operating system with a nonpreemptive scheduler  
a uniprogrammed operating system 
Question 18 Explanation:
Transaction from running → ready present.
So this is preemptive.
So this is preemptive.
Question 19 
A critical section is a program segment
which should run in a certain specified amount of time  
which avoids deadlocks  
where shared resources are accessed  
which must be enclosed by a pair of semaphore operations, P and V

Question 19 Explanation:
In CS, share resources are accessed.
Question 20 
Which of the following is an example of spooled device?
A line printer used to print the output of a number of jobs.  
A terminal used to enter input data to a running program.  
A secondary storage device in a virtual memory sytem.  
A graphic display device. 
Question 20 Explanation:
Example of spooled device is a line printer used to print the output of a number of jobs.
Question 21 
A ROM is sued to store the table for multiplication of two 8bit unsigned integers.
The size of ROM required is
256 × 16  
64 K × 8  
4 K × 16  
64 K × 16 
Question 21 Explanation:
When we multiply the two 8 bit numbers result will reach upto 16 bits. So we require 16 bits for each multiplication output.
No. of results possibe = 2^{8} × 2^{8} = 2^{16} = 64K
Then total size of ROM = 64K × 16
No. of results possibe = 2^{8} × 2^{8} = 2^{16} = 64K
Then total size of ROM = 64K × 16
Question 22 
Number of machine cycles required for RET instruction in 8085 microprocessor is
1  
2  
3  
5 
Question 22 Explanation:
1 for instruction fetch.
2 for stack operation.
Total no. of cycles = 2+1 = 3
2 for stack operation.
Total no. of cycles = 2+1 = 3
Question 23 
Both’s algorithm for integer multiplication gives worst performance when the
multiplier pattern is
101010 …..1010  
100000 …..0001  
111111 …..1111  
011111 …..1110 
Question 23 Explanation:
When the pairs 01 (or) 10 occur frequently in the multiplier. In that case Booth multiplication gives worst performance.
Question 24 
For the daisy chain scheme of connecting I/O devices, which of the following statements is true?
It gives nonuniform priority to various devices.  
It gives uniform priority to all devices.  
It is only useful for connecting slow devices to a processor device.  
It requires a separate interrupt pin on the processor for each device.

Question 24 Explanation:
Daisy chaining technique tells the processor in which order the interrupt should be handle by providing priority devices.
→ In this all devices connected serially.
→ High priority devices placed first, followed by low priority devices.
→ In this all devices connected serially.
→ High priority devices placed first, followed by low priority devices.
Question 25 
0 to 1  
0.5 to 1  
2^{23} to 0.5  
0.5 to (12^{23}) 
Question 25 Explanation:
Maximum value of mantissa will be 23, is where a decimal point is assumed before first 1. So the value is 1  2^{23}.
Question 26 
Let R denotes the set of real numbers. Let f: R×R → R×R be a bijective function defined by f(x, y) = (x+y, xy). the inverse function of f is given by
Question 26 Explanation:
Question 27 
Let R be a nonempty relation on a collection of sets defined by A R B if and only if A ∩ B = ф. Then, (pick the true statement)
R is reflexive and transitive  
R is symmetric and not transitive  
R is an equivalence relation  
R is not reflexive and not symmetric 
Question 27 Explanation:
Let A = {1, 2, 3} and B = {4, 5} and C = {1, 6, 7}
Now,
A ∩ B = ф
& B ∩ C = ф
But A ∩ B ≠ ф
So, R is not transitive.
A ∩ B = A, so R is not reflexive.
If A ∩ B = ф
then definitely B ∩ A = ф.
Hence, R is symmetric.
So, option (B) is true.
Now,
A ∩ B = ф
& B ∩ C = ф
But A ∩ B ≠ ф
So, R is not transitive.
A ∩ B = A, so R is not reflexive.
If A ∩ B = ф
then definitely B ∩ A = ф.
Hence, R is symmetric.
So, option (B) is true.
Question 28 
Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.
((x → y) ∧ x) → y  
((x → y) ∧ (x ∧ y)) → x  
(x → (x ∨ ψ))  
((x ∨ y) ↔ (x → y) 
Question 28 Explanation:
When x = F and y = F
then option (D) will be False.
then option (D) will be False.
Question 29 
Which one of the following is false?
The set of all bijective functions on a finite set forms a group under function composition.
 
The set {1, 2, ……., p–1} forms a group under multiplication mod p where p is a prime number.  
The set of all strings over a finite alphabet forms a group under concatenation.  
A subset s ≠ ф of G is a subgroup of the group 
Question 29 Explanation:
Option (C) is False because string concatatieon operation is monoid(doesn't have inverse to become a group).
Question 30 
Question 30 Explanation:
Note: Out of syllabus.
Question 31 
if a = b or θ = nπ, is an integer  
always  
never  
if a cos θ ≠ b sin θ

Question 31 Explanation:
Question 32 
The probability that top and bottom cards of a randomly shuffled deck are both aces in
Question 32 Explanation:
E_{1} : First card being ace
E_{2} : Last card being ace
Note that E_{1} and E_{2} are dependent events, i.e., probability of last card being ace if first is ace will be lesser than the probability of last card being ace if first card is not ace.
So, probability of first card being ace = 4/52
Probability of last card being ace given that first card is ace is,
P(E_{2} / E_{1}) = 3/51
∴ P(E_{1} and E_{2}) = P(E_{1}) ⋅ P(E_{2} / E_{1}) = 4/52 * 3/51
E_{2} : Last card being ace
Note that E_{1} and E_{2} are dependent events, i.e., probability of last card being ace if first is ace will be lesser than the probability of last card being ace if first card is not ace.
So, probability of first card being ace = 4/52
Probability of last card being ace given that first card is ace is,
P(E_{2} / E_{1}) = 3/51
∴ P(E_{1} and E_{2}) = P(E_{1}) ⋅ P(E_{2} / E_{1}) = 4/52 * 3/51
Question 33 
If L_{1} and L_{2} are context free languages and R a regular set, one of the languages
below is not necessarily a context free language. Which one?
L_{1}, L_{2}  
L_{1} ∩ L_{2}  
L_{1} ∩ R  
L_{1} ∪ L_{2} 
Question 33 Explanation:
Context free languages are not closed under intersection.
Question 34 
the set of all binary strings with unequal number of 0’s and 1’s  
the set of all binary strings including the null string
 
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
 
None of the above 
Question 34 Explanation:
(B) is the answer. Because for any binarystring of 0's and 1's we can append another string to make it contain equal no. of 0's and 1's, i.e., any string over {0,1} is a prefix of a string in L.
Question 35 
the sentence if a then if b then c:=d  
the left most and right most derivations of the sentence if a then if b then c:=d give rise top different parse trees  
the sentence if a then if b then c:=d else c:=f has more than two parse trees  
the sentence if a then if then c:=d else c:=f has two parse trees 
Question 35 Explanation:
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:
Parse tree 2:
"if a then if b then c:=d else c:=f".
Parse tree 1:
Parse tree 2:
Question 36 
0  
1  
2  
3 
Question 36 Explanation:
Lets draw first heap from given sequence,
Question 37 
O(n)  
O(log n)  
None of the above 
Question 37 Explanation:
Apply Master's theorem.
Question 38 
The average number of key comparisons done on a successful sequential search
in list of length n is
Question 38 Explanation:
Total comparisons required
= No. of comparisons if element present in 1^{st} position + No. of comparisons if element present in 2^{nd} position + ............. + No. of comparisons if element present in n^{th} position
= 1 + 2 + 3 + ... + n
= n(n+1)/2
Since there are n elements in the list, so average no. of comparisons
= Total comparisons/Total no. of elements
= (n(n+1)/2)/n
= n+1/2
= No. of comparisons if element present in 1^{st} position + No. of comparisons if element present in 2^{nd} position + ............. + No. of comparisons if element present in n^{th} position
= 1 + 2 + 3 + ... + n
= n(n+1)/2
Since there are n elements in the list, so average no. of comparisons
= Total comparisons/Total no. of elements
= (n(n+1)/2)/n
= n+1/2
Question 39 
(4, 7)  
(7, 4)  
(8, 3)  
(3, 8) 
Question 39 Explanation:
50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
Question 40 
C_{1} < C_{2}  
C_{1} > C_{2}  
C_{1} = C_{2}  
we cannot say anything for arbitrary n. 
Question 40 Explanation:
Both are the worst cases of Quick sort, i.e., either the elements are already in increasing order or the elements are already in decreasing order.
So, option is (C) is correct.
So, option is (C) is correct.
Question 41 
(ii) only  
(i) only  
both (i) and (ii)  
None of the above 
Question 41 Explanation:
If M2 macro is called with X=0, then it will go into an infinite loop.
Question 42 
A – 3 B – 4 C – 1 D – 2  
A – 4 B – 3 C – 1 D – 2  
A – 4 B – 3 C – 2 D – 1  
A – 3 B – 4 C – 2 D – 1 
Question 42 Explanation:
Each time a subroutine is called its activation record is created.
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
Question 43 
A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for
151  
181  
231  
541 
Question 43 Explanation:
200 and 260 are already hold by some other processes. Now we have to model the partition in such a way so that smallest allocation request could be denied. So, we can do the division as,
So, smallest allocation request which can be denied is 181 KB.
So, smallest allocation request which can be denied is 181 KB.
Question 44 
A solution to the Dining Philosophers Problem which avoids deadlock is
ensure that all philosophers pick up the left fork before the right fork  
ensure that all philosophers pick up the right fork before the left fork  
ensure that one particular philosopher picks up the left fork before the right fork, and that all other philosophers pick up the right fork before the left fork  
None of the above 
Question 44 Explanation:
In the Dining philosopher problem, each philosopher needs exactly two chopsticks to eat food but the problem is: each philosopher is going to take one chopstick at a time, which is placed at its righthand side or at its lefthand side, but remember all should choose in the same manner like if first one chooses in a clockwise manner then each one should choose in clockwise, this type of picking cause, a circular waiting loop because each one is depending on other. This is also called as circular waiting and it leads to deadlock.
To avoid this, atleast one philosopher should choose its first chopstick in different way so that circular loop is not formed.
To avoid this, atleast one philosopher should choose its first chopstick in different way so that circular loop is not formed.
Question 45 
Four jobs to be executed on a single processor system arrive at time 0^{+} in the order A, B, C, D. their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is
10  
4  
8  
9 
Question 45 Explanation:
Time quantum is 1 unit.
∴ Completion time of A is 9 unit.
∴ Completion time of A is 9 unit.
Question 46 
Binary of Hex conversion
 
Binary to BCD conversion  
Binary to grey code conversion
 
Binary to radix12 conversion

Question 46 Explanation:
Here ф means 0.
Whenever, b_{2} = b_{3} = 1, then only 0100, i.e., 4 is added to the given binary number. Lets write all possibilities for b.
Note that the last 4 combinations leads to b_{3} and b_{2} as 1. So, in these combinations only 0010 will be added.
1100 is 12
1101 is 13
1110 is 14
1111 is 15
in binary unsigned number system.
1100 + 0100 = 10000
1101 + 0100 = 10001, and so on.
This is conversion to radix 12.
Whenever, b_{2} = b_{3} = 1, then only 0100, i.e., 4 is added to the given binary number. Lets write all possibilities for b.
Note that the last 4 combinations leads to b_{3} and b_{2} as 1. So, in these combinations only 0010 will be added.
1100 is 12
1101 is 13
1110 is 14
1111 is 15
in binary unsigned number system.
1100 + 0100 = 10000
1101 + 0100 = 10001, and so on.
This is conversion to radix 12.
Question 48 
4  
3  
2  
1 
Question 48 Explanation:
3 states are required in the minimized machine states B and C can be combined as follows:
Question 50 
A micro program control unit is required to generate a total of 25 control signals.
Assume that during any microinstruction, at most two control signals are active.
Minimum number of bits required in the control word to generate the required
control signals will be
2  
2.5  
10  
12 
Question 50 Explanation:
To generate 1 out of 25 different control signals we need 5 bits. But at any time atmost 2 signals can be active. So control word length
= 5+5
= 10 bits
= 5+5
= 10 bits
There are 50 questions to complete.