## Descriptive

 Question 1

 A Theory Explantion is given below.
Database-Management-System       Descriptive       Gate-2002
 Question 2

 A Theory Explanation is given below.
Operating-Systems       Descriptive       Gate-2002
 Question 3

 A Theory Explanation is given below.
Operating-Systems       Descriptive       Gate-2002
 Question 4

 A Theory Exolanation is given below.
Operating-Systems       Descriptive       Gate-2002
 Question 5

 A Theory Explanation is given below.
Compiler-Design       Descriptive       Gate-2002
 Question 6

 A Theory Explanation is given below.
Theory-of-Computation       Descriptive       Gate-2000
Question 6 Explanation:
(a) From the question based on possibilities:
L = (0+1)* - (0+1)* (00+11) (0+1)*

(b) i≤j as S→aSAb
There will be always for one a in left and minimum one b in right and A→bA|X can generate any no. of b's including Null, if A is X then i=j and if A is generate any b then j>i. So the condition i≤j is true.
 Question 7

 A Theory Explanation is given below.
Theory-of-Computation       Descriptive       Gate-2000
Question 7 Explanation:
(a)

(b)
 Question 8

 A Theory Explanation is given below.
Digital-Logic-Design       Descriptive       Gate-2000
 Question 9

 A Theory Explanation is given below.
Computer-Organization       Descriptive       Gate-2000
Question 9 Explanation:
Note: Out of syllabus.
 Question 10

 A Theory Explanation is given below.
Computer-Organization       Descriptive       Gate-2000
Question 10 Explanation:
Note: Out of syllabus.
 Question 11

 A Theory Explanation is given below.
Data-Structures       Descriptive       Gate-2000
Question 11 Explanation:
(a) Enqueue → push
Dequeue → reverse, pop, reverse
(b) (i) After evaluating 5 2 * 3 4 +
Sol:
7(3+4) 10(5*2)
(ii) After evaluating 5 2 * 3 4 + 5 2
Sol:
25(5*5) 7(3+4) 10(5*2)
(iii) At the end of evaluation
Sol: 80
 Question 12

 A Theory Explanation is given below.
Engineering-Mathematics       Descriptive       Gate-2000
 Question 13

 A Theory Explanation is given below.
Algorithms        Descriptive       Gate-2000
Question 13 Explanation:
(a) (1) f[n-2] != 0
(2) f[n-2];
(3) f[n-2] = +;
(b) The time complexity of the resulting program when computing fib(n) is Θ(n).
 Question 14

 A Theory Explanation is given below.
Programming       Descriptive       Gate-2000
Question 14 Explanation:
Note: Out of syllabus.
 Question 15

 A Theory Explanation is given below.
Computer-Organization       Descriptive       Gate-2000
Question 15 Explanation:
(a) Since it is said that the instruction after branch is not fetched till the branch instruction is completed. So CPI for branch instruction is 5. And for normal instruction CPI is 1.
So total execution time
= (0.2×5 + 0.8×1) × 2ns
= 3.6 ns
(b) Total branch instructions are 20% as given in previous part. In which 80% are conditional and in which 50% of the conditional branch is taken. So total conditional branch instruction which is taken is
50% of 80% of 20%
0.5×0.8×0.2 = 0.08
And 20% of total branch instruction are not conditional means for that branch is necessarily taken. So total unconditional branch instruction is,
0.2×0.2 = 0.04
Hence, total branch instruction which is taken is,
0.08+0.04 = 0.12
Now lets calculate total execution time,
= (0.12×5 + 0.88×1) × 2ns
= 2.96 ns
 Question 16

 A Theory Explanation is given below.
Data Structures        Descriptive       Gate-2000
Question 16 Explanation:
(a) At set(7) ⇒ count = 1
then q[1] = 7; p[7] = 1
At set(3) ⇒ count = 2
then q[2] = 3; p[3] = 2
At set[9] ⇒ count = 3
then q[3] = 9; p[9] = 3;
(b) "The first count elements of array q contains value i such that set (i) has been called".
(c) If set(i) has not been celled for some i, then regardless of what p[i] contains, when we call is set(i) then
if (q[p[i]] ≠ i)
return false;
Will always execute, because if set(i) is not called then p[i]≠count(any) and for then same count q[count]≠i.
So if statement will be true and will return false.
 Question 17

 A Theory Explanation is given below.
Algorithms        Descriptive       Gate-2000
Question 17 Explanation:
(a) Since swaps are done between adjacent elements only. So this is nothing but Bubble sort.
In Bubble sort maximum no. of swap is done when the elements are in non-increasing order, i.e.,
{2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0}
Pass 1 - 9 swaps
Pass 2 - 9 swaps
Pass 3 - 9 swaps
Pass 4 - 4 swaps
Pass 5 - 4 swaps
Pass 6 - 4 swaps
Pass 7 - 4 swaps
Pass 8 - 4 swaps
Pass 9 - 0 swaps
Pass 10 - 0 swaps
Pass 11 - 0 swaps
Total swaps = 47
(b) Same as part (a)
(a)

While traversing the tree we will get value,
E.val = 12
(b) While traversing the parse tree we will get 10 Reductions.
 Question 18

 A Theory Explanation is given below.
Compiler-Design       Descriptive       Gate-2000
 Question 19

 A Theory Explantion is given below.
Engineering-Mathematics       Descriptive       Gate-2001
 Question 20

 A Theory Explanation is given below.
Digital-Logic-Design       Descriptive       Gate-2001
Question 20 Explanation:
(a)
The function is self dual because
→ There is no mutually exclusive pair.
→ No. of minterms = No. of maxterms
(b)
Write Minimal POS.
 Question 21

 A Theory Explanation is given below.
Operating-Systems       Descriptive       Gate-2001
 Question 22
 A Theory Explanation is given below.
Database-Management-System       Descriptive       Gate-2001
There are 22 questions to complete.