## Gate-2000

 Question 1
The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from some same suit is
 A 3 B 8 C 9 D 12
Engineering-Mathematics       Combinatorics
Question 1 Explanation:
No. of cards = 52
No. of suits = 4(P)
Apply pigeon hole principal.
Then number of pigeons= n
floor [(n-1)/P] + 1 = 3
floor [(n-1)/P] = 2
floor [(n-1)] =8
floor (n) = 8 + 1
n ≥ 9
Minimum no. of cards, n = 9
 Question 2

 A 0 B n -1 C n2 - 3n + 2 D
Engineering-Mathematics       Linear-Algebra
Question 2 Explanation:
Let us consider n=5 then we get

Add ith row and jth column if we zero, apply to all row and their corresponding column the total becomes zero.
 Question 3

 A 4 B 0 C 15 D 20
Engineering-Mathematics       Linear-Algebra
Question 3 Explanation:
The value of the determinant is 2 * 1 * 2 * 1 = 4
 Question 4
Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
 A S ⊂ T B T ⊂ S C S = T D S ∩ T = ɸ
Theory-of-Computation       Regular-Expressions
Question 4 Explanation:
If we draw DFA for language S and T it will represent same.
 Question 5

 A L = 0+ B L is regular but not 0+ C L is context free but not regular D L is not context free
Theory-of-Computation       Identify-Class-Language
Question 5 Explanation:
The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0+.
 Question 6
The number 43 in 2’s complement representation is
 A 01010101 B 11010101 C 00101011 D 10101011
Digital-Logic-Design       Number-Systems
Question 6 Explanation:
Positive integers are represented in its normal binary form while negative numbers are represented in its 2′s complement form. Binary representation of 43 is 00101011.
 Question 7
To put the 8085 microprocessor in the wait state
 A lower the HOLD input B lower the READY input C raise the HOLD input D raise the READY input
Computer-Organization       Microprocessor
Question 7 Explanation:
If ready pin is high the microprocessor will complete the operation and proceeds for the next operation. If ready pin is low the microprocessor will wait until it goes high.
 Question 8
Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-pipelined but identical CPU, we can say that
 A T1 ≤ T2 B T1 ≥ T2 C T1 < T2 D T1 is T2 plus the time taken for one instruction fetch cycle
Computer-Organization       Pipelining
Question 8 Explanation:
PIPELINING SYSTEM:
Pipelining is an implementation technique where multiple instructions are overlapped in execution. It has a high throughput (amount of instructions executed per unit time). In pipelining, many instructions are executed at the same time and execution is completed in fewer cycles. The pipeline is filled by the CPU scheduler from a pool of work which is waiting to occur. Each execution unit has a pipeline associated with it, so as to have work pre-planned. The efficiency of pipelining system depends upon the effectiveness of CPU scheduler.
NON- PIPELINING SYSTEM:
All the actions (fetching, decoding, executing of instructions and writing the results into the memory) are grouped into a single step. It has a low throughput.
Only one instruction is executed per unit time and execution process requires more number of cycles. The CPU scheduler in the case of non-pipelining system merely chooses from the pool of waiting work when an execution unit gives a signal that it is free. It is not dependent on CPU scheduler.
 Question 9
The 8085 microprocessor responds to the present of an interrupt
 A as soon as the TRAP pin becomes ‘high’ B by checking the TRAP pin for ‘high’ status at the end of each instruction each C by checking the TRAP pin for ‘high’ status at the end of the execution of each instruction D by checking the TRAP pin for ‘high’ status at regular intervals
Computer-Organization       Microprocessor
Question 9 Explanation:
TRAP is non maskable interrupt . TRAP is active high, level, edge triggered non maskable highest priority interrupt. When TRAP line is active microprocessor insert intervals restarts automatically at vector location of TRAP.
 Question 10

 A X – 3 Y – 2 Z - 1 B X – 1 Y – 3 Z - 2 C X – 2 Y – 3 Z - 1 D X – 3 Y – 1 Z - 2
Computer-Organization       Match-the-Following
Question 10 Explanation:
Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.
Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.
Auto increment or decrements can be one by using loops.
 Question 11

 A An array, each element of which is a pointer to a structure of type node B A structure of 2 fields, each field being a pointer to an array of 10 elements C A structure of 3 fields: an integer, a float, and an array of 10 elements D An array, each element of which is a structure of type node
Programming       C-Programming
Question 11 Explanation:
The given code represents an array of s[ ], in this each element is a pointer to structure of type node.
 Question 12

 A X – 1 Y – 3 Z – 2 B X – 2 Y – 1 Z – 3 C X – 3 Y – 2 Z – 1 D X – 3 Y – 1 Z – 2
Programming       Match-the-Following
Question 12 Explanation:
X → m = NULL will results the loss of memory.
Y → n is pointer to invalid memory, a making it as a dangling pointer.
Z → p is not initialized.
p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.
 Question 13

 A X – 1 Y – 2 Z – 3 B X – 3 Y – 1 Z – 2 C X – 3 Y – 2 Z – 1 D X – 2 Y – 3 Z – 1
Data-Structures       Match-the-Following
Question 13 Explanation:
Stack is used in depth first search.
Queus is used in Queue.
Heap is used in heap.
 Question 14

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

 A (1 2 (4 5 6 7)) B (1 (2 3 4) 5 6) 7) C (1 (2 3 4) (5 6 7)) D (1 (2 3 NULL) (4 5))
Data-Structures       Binary-Trees
Question 14 Explanation:
Option C:

(Proper Representation)
 Question 15

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. Which of the following statements is true?

 A t(n) is O(1) B n ≤ t(n) ≤ n log2 n C D
Algorithms        Sorting
Question 15 Explanation:
Since the array is sorted. Now just pick the first two minimum elements and check if their sum is less than 1000 or not. If it is less than 1000 then we found it and if not then it is not possible to get the two elements whose sum is less than 1000. Hence, it takes constant time. So, correct option is (A).
 Question 16
Aliasing in the context of programming languages refers to
 A multiple variables having the same memory location B multiple variables having the same value C multiple variables having the same identifier D multiple uses of the same variable
Programming       Aliasing
Question 16 Explanation:
In computer programming, aliasing refers to the situation where the same memory location can be accessed using different names.
 Question 17

 A 22 bytes B 14 bytes C 18 bytes D 10 bytes
Programming       C-Programming
Question 17 Explanation:
short [5] = 5×2 = 10
max[float, long] = max [4, 8] = 8
Total = short[5] + max[float,long] = 10 + 8 = 18
 Question 18

 A 3 B 26 C 10 D 21
Compiler-Design       Compilers
Question 18 Explanation:
We have six different types of tokens are available
(i) Keyword
(ii) Identifier
(iii) Constant
(iv) Variable
(v) String
(vi) Operator
Print = Token 1
( = Token 2
"i=%d%x" = Token 3 [Anything inside " " is one Token]
, = Token 4
i = Token 5
, = Token 6
& = Token 7
i = Token 8
) = Token 9
; = Token 10
Here, totally 10 Tokens are present in the equation.
 Question 19
Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.
 A Leftmost derivation B Leftmost derivation traced out in reverse C Rightmost derivation D Rightmost derivation traced out in reverse
Compiler-Design       Parsers
Question 19 Explanation:
Top-down parser - Leftmost derivation
Bottom-Up parser - Reverse of rightmost derivation
 Question 20
Which of the following need not necessarily be saved on a context switch between processes?
 A General purpose registers B Translation look-aside buffer C Program counter D All of the above
Operating-Systems       Context-Switching
Question 20 Explanation:
We don't need to save TLB or cache to ensure correct program resumption. They are just bonus for ensuring better performance. But PC, stack and registers must be saved as otherwise program cannot resume.
 Question 21

 A Thrashing B Deadlock C Starvation, but not deadlock D None of the above
Operating-Systems       Process-Synchronization
Question 21 Explanation:
 Question 22
B+-trees are preferred to binary trees in databases because
 A Disk capacities are greater than memory capacities B Disk access is much slower than memory access C Disk data transfer rates are much less than memory data transfer rates D Disks are more reliable than memory
Database-Management-System       B+-Trees
Question 22 Explanation:
In B+ trees it is easy to reduce the number of last level access from the disk when the disk size is too large.
 Question 23

 A Department address of every employee B Employees whose name is the same as their department name C The sum of all employees’ salaries D All employees of a given department
Database-Management-System       Relational-Algebra
Question 23 Explanation:
The sum of all employee’s salaries can’t be represented by using the given six basic algebra operation. If we want to represent sum of salaries then we need to use aggregation operator.
 Question 24

X, Y and Z are closed intervals of unit length on the real line. The overlap of X and Y is half a unit. The overlap of Y and Z is also half a unit. Let the overlap of X and Z be k units. Which of the following is true?

 A k must be 1 B k must be 0 C k can take any value between 0 and 1 D None of the above
Engineering-Mathematics       Numerical-Methods
Question 24 Explanation:
The value of K must be Either 0 or 1.
 Question 25

 A 0 B C D 1
Engineering-Mathematics       Probability
Question 25 Explanation:
Pr(E1) = Pr(E2) = a(say)
Pr(E1 ∪ E2) = 1
E1 and E2 are Independent.
P(E1 ∪ E2) = Pr(E1) + Pr(E2) - Pr(E1 ∩ E2)
1 = a + a - Pr(E1)⋅Pr(E2)
1 = a + a - a⋅a
2a - a2 = 1
a2 - 2a + 1 = 0
(a - 1)2 = 0
a = 1 Pr(E1) = 1
 Question 26

 A S > T B S = T C S < T and 2S > T D 2S ≤ T
Engineering-Mathematics       Calculus
Question 26 Explanation:
S is continuously increasing function but T represent constant value so S>T.
 Question 27

 A 1 B 2 C 3 D 4
Engineering-Mathematics       Polynomials
Question 27 Explanation:
P(x) should be like

Minimum degree of P(x) = 4
Maximum degree of P(x) = 5
 Question 28
A relation R is defined on the set of integers as xRy iff (x+y) is even. Which of the following statements is true?
 A R is not an equivalence relation B R is an equivalence relation having 1 equivalence class C R is an equivalence relation having 2 equivalence classes D R is an equivalence relation having 3 equivalence classes
Engineering-Mathematics       Sets-And-Relation
Question 28 Explanation:
It is reflexive R(x+y) is even ⇒ R(x+x) is even.
It is symmetric R(x+y) is even ⇒ R(x+y) is even then R(y+x) is also v.
It is transitive R(x+y) is even ⇒ R((x+y)+z)) is even then R(x+(y+z)) is also even.
This given relation is equivalence.
Sum of two even numbers are even. Same sum of two odd numbers are even but one even, one odd is odd. It can have two equivalent classes.
 Question 29
Let P(S) denotes the powerset of set S. Which of the following is always true?
 A P(P(S)) = P(S) B P(S) ∩ P(P(S)) = {ɸ} C P(S) ∩ S = P(S) D S ∉ P(S)
Engineering-Mathematics       Sets-And-Relation
Question 29 Explanation:
Let us consider
S={1}
P(S)=[{ }, {1}]
P(P(S)) = [{ }, {1}, {{ }, 1}, {1, { }}]
Option A: P(P(S)) ≠ P(S) (wrong)
Option B: P(S) ∩ P(P(S)) ≠ ɸ (wrong)
Option C: P(S) ∩ S ≠ P(S) (wrong)
Option D: S ∈ P(S) (wrong)
None of the given is correct.
 Question 30
Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b ∨-b) and b ↔ c hold. Then the truth-value of the formula (a ∧ b) → (a ∧ c) ∨ d is always
 A True B False C Same as the truth-value of b D Same as the truth-value of d
Engineering-Mathematics       Propositional-Logic
Question 30 Explanation:
a ↔ (b ∨-b) and b ↔ c
Given ⇒ (a∧b) → (a∧c) ∨d
⇒ (a∧b) → (a∧c) ∨d (b⇔c)
⇒ T∨d
⇒ T
 Question 31
What can be said about a regular language L over {a} whose minimal finite state automation has two states?
 A L must be {an |n is odd} B L must be {an |n is even} C L must be {an|≥0} D Either L must be {an |n is odd}, or L must be {an | n is even}
Theory-of-Computation       Finite-Automata
Question 31 Explanation:
If first state is final, then it accepts even no. of a's. If second state is final then it accepts odd no. of a's.
 Question 32

 A Both (P1) and (P2) are decidable B Neither (P1) nor (P2) are decidable C Only (P1) is decidable D Only (P2) is decidable
Theory-of-Computation       Decidability-and-Undecidability
Question 32 Explanation:
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.
 Question 33

 A 0 1 0 0 B 1 1 0 1 C 1 0 1 1 D 1 0 0 0
Digital-Logic-Design       Boolean-Algebra
Question 33 Explanation:
Just put the values of each options in the equation and check it.
 Question 34

 A B C D None of the above
Digital-Logic-Design       K-Map
Question 34 Explanation:
Given k-map gives xy + xy + wz

⇒ wy + wz + xy
 Question 35

 A 1, 0 B 1, 1 C 0, 0 D 0, 1
Digital-Logic-Design       Sequential-Circuits
Question 35 Explanation:
Here clocks are applied to both flip flops simultaneously.
When 11 is applied to Jk flip flop it toggles the value of P so op at P will be 1.
Input to D flip flop will be 0(initial value of P) so op at Q will be 0
 Question 36
A graphics card has on board memory of 1MB. Which of the following modes can the card not support?
 A 1600 × 400 resolution with 256 colours on a 17 inch monitor B 1600 × 400 resolution with 16 million colours on a 14 inch monitor C 800 × 400 resolution with 16 million colours on a 17 inch monitor D 800 × 800 resolution with 256 colours on a 14 inch monitor
Operating-Systems       Graphics
Question 36 Explanation:
For every option we need to calculate memory.
Option A:
1600×400 = 64000 = 640 KB
256 colours 8 bits = 1 Byte
⇒ 640×1 = 640KB (we have 1MB)
Option B:
1600×400 = 640KB
16 million = 24 bits = 3 bytes
⇒ 640×3 = 1920KB (Not enough)
Option C:
800×400 = 320 KB
16 millions = 3 bytes ⇒ 320×3 = 960 KB (we have 1MB)
Option D:
800×400 = 320 KB
256 colours = 1 Byte ⇒ 320×1 = 320 (we have 1MB)
 Question 37

 A X = 1.0, Y = 1.0 B X = 1.0, Y = 0.0 C X = 0.0, Y = 1.0 D X = 0.0, Y = 0.0
Digital-Logic-Design       Number-Systems
Question 37 Explanation:
Given: 32 bits representation. So, the maximum precision can be 32 bits (In 32-bit IEEE representation, maximum precision is 24 bits but we take best case here). This means approximately 10 digits.
A = 2.0 * 1030, C = 1.0
So, A + C should make the 31st digit to 1, which is surely outside the precision level of A (it is 31st digit and not 31st bit). So, this addition will just return the value of A which will be assigned to Y.
So, Y + B will return 0.0 while X + C will return 1.0.
 Question 38

 A Rotates s left by k positions B Leaves s unchanged C Reverses all elements of s D None of the above
Data-Structures       Arrays
Question 38 Explanation:
If we perform the three given open operations it will result left rotation by K positions. If we perform n time it will result the initial array.
 Question 39
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?
 A LASTIN = LASTPOST B LASTIN = LASTPRE C LASTPRE = LASTPOST D None of the above
Data-Structures       Binary-Trees
Question 39 Explanation:
In full Binary tree LASTIN = LASTPRE.
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.
 Question 40

 A h(n) is O (f(n)) B h(n) is O (g(n)) C g(n) is not O (f(n)) D f(n) is O(g(n))
Algorithms        Time-Complexity
Question 40 Explanation:
Consider n value as 210
Then
f(n) = 3(n32)=3*(210)32 = 3*2320
g(n) = 2320
h(n) = 1024!
So relation between the functions can be:
f(n) and g(n) are of same order, so f(n) is O(g(n)) and g(n)=O(f(n)). Option C is wrong.
h(n) is n! Which is of higher order than f(n) and g(n). So options A and B are wrong.
 Question 41
Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and  emin the edge with minimum weight. Which of the following statements is false?
 A Every minimum spanning tree of G must contain emin B If emax is in a minimum spanning tree, then its removal must disconnect G C No minimum spanning tree contains emax D G has a unique minimum spanning tree
Algorithms        Minimum-Spanning-Tree
Question 41 Explanation:

Minimum Spanning Tree:
 Question 42

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

 A {u, v} must be an edge in G, and u is a descendant of v in T B {u, v} must be an edge in G, and v is a descendant of u in T C If {u, v} is not an edge in G then u is a leaf in T D If {u, v} is not an edge in G then u and v must have the same parent in T
Data-Structures       Graphs
Question 42 Explanation:

In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.
 Question 43

 A 10 B 4 C 6 D 7
Programming       C-Programming
Question 43 Explanation:
At i=0; count=0
i=1; count=1
i=2; count=3
i=3; count=6
i=4; count=10
It return count value is 10.
 Question 44

 A * has higher precedence than + B - has higher precedence than * C + and – have same precedence D + has higher precedence than *
Compiler-Design       Grammar
Question 44 Explanation:
The operator which is in low level that can have high preference.
Order of precedence is *, +, -.
Here * and + have equal preference, '-' can have higher precedence than + and *.
 Question 45

Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio results in average memory access time of

 A 1.9999 milliseconds B 1 millisecond C 9.999 microseconds D 1.9999 microseconds
Operating-Systems       Virtual Memory
Question 45 Explanation:
Average memory access time = (P*t1) + [(1-P)t2]
= (0.9999*1) + [(1-0.9999) *10000]
= (0.9999) + (0.0001 * 10000)
= 0.9999 + 1
= 1.9999 microseconds
 Question 46
Which of the following is NOT a valid deadlock prevention scheme?
 A Release all resources before requesting a new resource B Number the resources uniquely and never request a lower numbered resource than the last one requested C Never request a resource after releasing any resource D Request and all required resources be allocated before execution
Question 46 Explanation:
Given statement is wrong. We can request a resource after releasing any resource.
 Question 47

 A XY → Z and Z → Y B YZ → X and Y → Z C YZ → X and X → Z D XZ → Y and Y → X
Database-Management-System       Functional-Dependency
Question 47 Explanation:
A functional dependency A→B is said to hold if for two tuples t1 and t2.
If for t1[A] = t2[A] then t1[Y] = t2[Y].
 Question 48

 A r has no duplicates and s is non-empty B r and s have no duplicates C s has no duplicates and r is non-empty D r and s have the same number of tuples
Database-Management-System       SQL
Question 48 Explanation:
r has no duplicate, if r can have duplicates it can be remove in the final state. s in non-empty if s is empty then r*s becomes empty.
 Question 49

In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent?

 A x = 5 not AND (not (x = 5) B x = 5 AND x > 4 and x < 6, where x is an integer C x ≠ 5 AND not (x = 5) D None of the above
Database-Management-System       SQL
Question 49 Explanation:
For all values less than five, x<5 is true and if x=5 then it is false.
 Question 50

 A Theory Explanation is given below.
Engineering-Mathematics       Sets-And-Relation
 Question 51

 A Theory Explanation is given below.
Engineering-Mathematics       Sets-And-Relation
Question 51 Explanation:

A1 is the identity element here. Inverse is does not exist for zero then it is not a group.
 Question 52

 A Theory Explanation is given below.
Engineering-Mathematics       Sets-And-Relation
Question 52 Explanation:
(a) No. of multiset of size 4 that can be constructed from n distinct elements so that atleast one element occurs exactly twice:
= multiset of size 4 with exactly one element occurs exactly twice + multiset of size 4 with exactly two element occurs exactly twice.

(b) Infinite, because size of multiset is not given.
 Question 53

 A Theory Explanation is given below.
Engineering-Mathematics       Graph-Theory
 Question 54

 A Theory Explanation is given below.
Theory-of-Computation       Descriptive
Question 54 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 55

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

(b)
 Question 56

 A Theory Explanation is given below.
Digital-Logic-Design       Descriptive
 Question 57

 A Theory Explanation is given below.
Computer-Organization       Descriptive
Question 57 Explanation:
Note: Out of syllabus.
 Question 58

 A Theory Explanation is given below.
Computer-Organization       Descriptive
Question 58 Explanation:
Note: Out of syllabus.
 Question 59

 A Theory Explanation is given below.
Computer-Organization       Descriptive
Question 59 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 60

 A Theory Explanation is given below.
Data-Structures       Descriptive
Question 60 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 61

 A Theory Explanation is given below.
Engineering-Mathematics       Descriptive
 Question 62

 A Theory Explanation is given below.
Data Structures        Descriptive
Question 62 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 63

 A Theory Explanation is given below.
Algorithms        Descriptive
Question 63 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 64

 A Theory Explanation is given below.
Algorithms        Descriptive
Question 64 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 65

 A Theory Explanation is given below.
Programming       Descriptive
Question 65 Explanation:
Note: Out of syllabus.
 Question 66

 A Theory Explanation is given below.
Compiler-Design       Descriptive
 Question 67

 A Theory Explanation is given below.
Operating-Systems       Process-Synchronization
Question 67 Explanation:
(a) (i) Signal (mutex)
(ii) Signal (mutex)
(iii) R ⇒ 1 (or) W == 1
(b) In CS, atleast one of the reader is always present. That means writer can't be enter into the critical section.
 Question 68

 A Theory Explanation is given below.
Database-Management-System       B+-Trees
Question 68 Explanation:
(a)
(i)

(ii)

(b)
 Question 69

 A Theory Explanation is given below.
Database-Management-System       SQL
There are 69 questions to complete.