Gate2005
Question 1 
int
( * f) (
int
* ) ;
A function that takes an integer pointer as argument and returns an integer.  
A function that takes an integer as argument and returns an integer pointer.  
A pointer to a function that takes an integer pointer as argument and returns an integer.  
A function that takes an integer pointer as argument and returns a function pointer. 
→ A pointer to a function which takes integer as a pointer and return an integer value.
Question 2 
Same as an abstract class
 
A data type that cannot be instantiated
 
A data type type for which only the operations defined on it can be used, but none else
 
All of the above 
Question 3 
both are procedural languages
 
both are based on λcalculus
 
both are declarative
 
both use Hornclauses

Question 4 
(i) and (ii) only
 
(i) and (iv) only
 
(i), (ii) and (iv) only
 
(i), (iii) and (iv) only

Question 5 
An array of 50 numbers
 
An array of 100 numbers
 
An array of 500 numbers  
A dynamically allocated array of 550 numbers

→ Then using array of 50 numbers is the best way to store the frequencies.
Question 6 
Graph G has no minimum spanning tree (MST)
 
Graph G has a unique MST of cost n1
 
Graph G has multiple distinct MSTs, each of cost n1
 
Graph G has multiple spanning trees of different costs

Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n1).
Question 7 
O(n)  
O(n log n)
 
O(n^{3/2})
 
O(n^{3})

For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R^{+} such that x R^{+} y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.
To find the transitive closure of given relation, we can represent the given relation by the graph such that if x R y then there should be directed edge between x and y in a graph. For this graph, we have to apply modified Floyd_Warshall Algorithm to find the transitive closure of the graph.
The time complexity of this algorithm is O(V3) where V is the number of vertices in the given graph. You can take here V as the number of elements is set i.e., N. Therefore time complexity for the given question is O(n^{3}).
Question 8 
X = Y
 
X ⊂ Y  
Y ⊂ X
 
None of these

B = {1, 3, 4, 5}
C = {2, 4, 5, 6}
X = (A  B)  C
X = {2, 6}  {2, 4, 5, 6}
= ∅
Y = (A  C)  (B  C)
= {1, 3}  { 1, 3}
= ∅
X = Y
X = (A  B)  C
= (1, 5)  (5, 7, 4, 3)
= (1)
Y = (A  C)  (B  C)
= (1, 4)  (2, 4)
= (1)
X = Y
Question 9 
not a lattice
 
a lattice but not a distributive lattice
 
a distributive lattice but not a Boolean algebra  
a Boolean algebra

But it is not distributed because for some element there are more than one complement. Moreover if it is not distributive then it can't be boolean.
Question 10 
6  
8  
9  
13 
F = E  V + 2 [From Euler's formula i.e., F + V  E = 2]
F = 19  13 +2
F = 8
Question 11 
12  
8  
Less than 8
 
More than 12

Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices  Minimum cover of vertex G
= 20  8
= 12
Question 12 
f(b  a)
 
f(b)  f(a)  
Then the probablity be area of the corresponding curve i.e.,
Question 13 
3 and 13
 
2 and 11  
4 and 13
 
8 and 14

Inverse of 4 = m; Inverse of 7 = n
(4×m)%15=1; (7*n)%15=1
Option A: m=3 n=13
12%15≠1 (✖️) 91%15=1 (✔️)
Option B: m=2 n=11
8%15≠1 (✖️) 11%15≠1 (✖️)
Option C: m=4 n=13
16%15=1(✔️) 91%15=1 (✔️)
Option D: m=8 n=14
120%15≠1(✖️) 98%15≠1(✖️)
Question 14 
ambiguous
 
leftrecursive  
rightrecursive  
an operatorgrammar

It have A → AA has left recursion.
Question 15 
f is independent of X
 
f is independent of Y
 
f is independent of Z
 
None of X, Y, Z is redundant

= ((X’+Y) YZ)’
= (X’YZ + YZ)’
= ((X’+1) YZ)’
= (YZ)’
Question 16 
 2^{n1} to (2^{n1}  1)  
 (2^{n1}  1) to (2^{n1}  1)
 
 2^{n1} to 2^{n1}
 
 (2^{n1} + 1) to (2^{n1}  1) 
The smallest (negative) n bit number is 100..0 (i.e., 1 followed by n1 zeros) which is equal to  2^{n1}.
1000...00
0111...11 < 1’s complement
1000..00 < 2’s complement
=  2^{n1}
Question 17 
1AF
 
D78  
D71  
32F

Make 3 zeros on the left side so that the number of bits is multiple of 4.
= (0001 1010 1111)_{2}
= (1 A F)_{16}
Question 18 
BC'D' + A'C'D + AB'D  
ABC' + ACD + B'C'D
 
ACD' + A'BC' + AC'D'
 
A'BD + ACD' + BCD'

f(A,B,C,D) = A'C'D + BC'D' + AB'D
Question 19 
Neither vectored interrupt nor multiple interrupting devices are possible.
 
Vectored interrupts are not possible but multiple interrupting devices are possible.
 
Vectored interrupts and multiple interrupting devices are both possible.
 
Vectored interrupt is possible but multiple interrupting devices are not possible.

Also for vectored Interrupts it is always possible if we implement in daisy chain mechanism.
Question 20 
Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?
I/O protection is ensured by operating system routine(s)
 
I/O protection is ensured by a hardware trap
 
I/O protection is ensured during system configuration
 
I/O protection is not possible

Question 21 
Saving temporary html pages
 
Saving process data
 
Storing the superblock
 
Storing device drivers

→ The interchange of data between a virtual memory and a real memory is called as swapping and space on a disk as 'swap space'.
→ Swap space in the disk can be used for saving process data.
Question 22 
Virtual memory increases
 
Larger RAMs are faster
 
Fewer page faults occur
 
Fewer segmentation faults occur

→ Such as if RAM size increases, then no. of page entries increases, then no. of page faults decreases.
Question 23 
TCP, but not UDP
 
TCP and UDP
 
UDP, but not TCP
 
Neither TCP nor UDP

Question 24 
Finding the IP address from the DNS
 
Finding the IP address of the default gateway  
Finding the IP address that corresponds to a MAC address
 
Finding the MAC address that corresponds to an IP address

Question 25 
2^{n}
 
2^{n1}  
2^{n}  1  
2^{n2} 
For Goback N, the maximum window size can be 2^{n}  1.
Question 26 
In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges. Why is the spanning tree algorithm used for bridgerouting?
For shortest path routing between LANs
 
For avoiding loops in the routing paths
 
For fault tolerance
 
For minimizing collisions

Question 27 
255.255.0.0
 
255.255.64.0
 
255.255.128.0
 
255.255.252.0

Question 28 
Database relations have a large number of records  
Database relations are sorted on the primary key
 
B^{+} trees require less memory than binary search trees
 
Data transfer from disks is in blocks 
Thus, the data can be transferred through blocks in B^{+} trees. This can be used for indexing the database relations.
Question 29 
BCNF is stricter than 3NF
 
Lossless, dependencypreserving decomposition into 3NF is always possible
 
Lossless, dependencypreserving decomposition into BCNF is always possible  
Any relation with two attributes is in BCNF

Option B: Lossless, dependency preserving decomposition into 3NF is always possible.
Option C: It is false.
It is not possible to have dependency preserving in BCNF decomposition.
→ Let take an example, 3NF can't be decomposed into BCNF.
Option D: It is true.
Let consider t wo attributes (X, Y).
If (X→Y), X is a candidate key. It is in BCNF and viceversa.
Question 30 
s ⊂ r
 
r ∪ s = r
 
r ⊂ s  
r * s = s

Table r: R(A, B, C, D)
Table r_{1}: Π_{A,B,C}(R)
Table r_{2}: Π_{A,D}(R)
S = r_{1} * r_{2} (* denotes natural join)
Table S:
Table r ⊂ Table S
⇒ r ⊂ S
Question 31 
double foo ( double ); /* Line 1 */ int main() { double da, db; // input da db = foo(da); } double foo( double a) { return a; } 
8, 4, 0, 2, 14
 
8, 4, 0, 2, 0
 
2, 0, 4, 8, 14
 
2, 0, 4, 8, 0

⇒ foo (a, sum) = foo (2048,0)
⇒ n == 2048
⇒ k = n%10 = 2048%10 = 8
⇒ j = n/10 = 2048/10 = 204
Sum = Sum+k = 0+8 = 8
foo(j, sum) = foo(204, 8)
⇒ n=204
k = n%10 = 204%10 = 4
j = n/10 = 204/10 = 20
sum = sum+k = 12+0 = 12
foo(j, sum) =foo(2,12)
⇒ n=2
k = n%10 = 2%10 = 2
j = n/10 = 2/10 = 0
sum = 14
foo(0,14) ⇒ n==0
printf("%d", k) ⇒ k = 2, 0, 4, 8
After foo( ) statement one more printf statement is there then if print 0 after all digits of n.
2, 0, 4, 8, 0.
Question 32 
double foo ( double ); /* Line 1 */ int main() { double da, db; // input da db = foo(da); } double foo( double a) { return a; } 
no compile warning or error  
some compilerwarnings not leading to unintended results  
some compilerwarnings due to typemismatch eventually leading to unintended results
 
compiler errors 
Question 33 
9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
 
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
 
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
 
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29 
Question 34 
10, 8, 7, 5, 3, 2, 1
 
10, 8, 7, 2, 3, 1, 5
 
10, 8, 7, 1, 2, 3, 5
 
10, 8, 7, 3, 2, 1, 5

Insert → 1 into heap structure
Insert → 7 into heap structure
Here, violating Maxheap property. So perform heapify operation.
The final sequence is 10, 8, 7, 3, 2, 1, 5.
Question 35 
5  
14  
24  
42 
(or)
t(0)=1
t(1)=1
t(4) = t(0)t(3) + t(1)t(2) + t(2)t(1) + t(3)t(0)
= 5+2+2+5
= 14
(or)
^{8}C_{4} / 5 = 14
Question 36 
nk  
(n  1) k + 1
 
n (k  1) + 1
 
n (k  1)

Leaves = total nodes  internal nodes
= nk+1n
= n(k1)+1
Question 37 
T(n) = O(n^{2})  
T(n) = θ(n log n)
 
T(n) = Ω(n^{2})
 
T(n) = O(n log n)

a=2, b=2, k=1, p=0.
The recurrence relation result will be O(nlogn).
Question 38 
O(V^{2})
 
O(E+VlogV)  
O(VlogV)
 
O((E+V)logV)

In worst case graph will be a complete graph i.e total edges = v(v1)/2 where v is no. of vertices.
E<=v^{2}
Time Complexity of Dijkstra's algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v^{2} + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
Question 39 
O(nlog log n)
 
θ(nlog n )
 
Ω(nlog n )
 
Ω(n^{3/2})

P = log n
Q = n/log n
∴ Putting values we get,
O(n log log n)
Question 40 
X ≡ Y  
X → Y
 
Y → X
 
¬Y → X

⇒ ∼(P∨Q) ∨ R
⇒ (∼P∧∼Q) ∨ R
⇒ (∼P∨R) × (∼Q∨R)
⇒ (P→R) ∧ (Q→R)
Option B: X→Y
[(P→R) × (Q→R)] → [(P→R) ∨ (Q→R)]
∼[(P→R) × (Q→R) ∨ (P→R) ∨ (Q→R)]
[∼(P→R) ∨ ∼(Q→R)] ∨ [(P→R) ∨ (Q→R)]
[∼(P→R) ∨ (P→R)] ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] ∨ [∼(Q→R) ∨ (Q→R)]
T ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] V T
T (✔️)
Question 41 
∀(x) [teacher(x) → ∃ (y) [student(y) → likes (y, x)]]  
∀(x) [teacher(x) → ∃ (y) [student(y) ∧ likes (y, x)]]
 
∃(y) ∀(x) [teacher(x) → [student(y) ∧ likes (y, x)]]
 
∀(x) [teacher(x) ∧ ∃ (y)[student(y) → likes (y, x)]]

Option B: If x is a teacher, then there exists some y, who is a student and like x. (✔️)
Option C: There exists a student who likes all teachers.
Option D: If x is a teacher and then there exists some y, if y is a student then y likes x.
Question 42 
R∪S, R∩S are both equivalence relations.  
R∪S is an equivalence relation.
 
R∩S is an equivalence relation.
 
Neither R∪S nor R∩S is an equivalence relation.

Let (a,b) present in R and (b,c) present in S and (a,c) is not present in either of them. Then R∪S will contain (a,b) and (b,c) but not (a,c) and hence not transitive.
And equivalence relation must satisfy 3 property:
(i) Reflexive
(ii) Symmetric
(iii) Transitive
But as we have seen that for R∪S, Transitivity is not satisfied.
Question 43 
f and g should both be onto functions
 
f should be onto but g need not be onto
 
g should be onto but f need not be onto
 
both f and g need not be onto

f: B→C and g: A→B are two functions.
h = f∘g = f(g(x))
→ If his onto function, that means for every value in C, there must be value in A.
→ Here, we are mapping C to A using B, that means for every value in C there is a value in B then f is onto function.
→ But g may (or) may not be the onto function i.e., so values in B which may doesn't map with A.
Question 44 
4  
6  
16  
24 
That means a=0,1,2 ⇒ 3
b = dmod5
That means b=0,1,2,3,4 ⇒ 4
→ Total no. of order pairs = 3 * 5 = 15
→ Ordered pair (c,d) has 1 combination.
Then total no. of combinations = 15+1 = 16
Question 45 
P_{3} is decidable if P_{1} is reducible to P_{3}
 
P_{3} is undecidable if P_{3} is reducible to P_{2}  
P_{3} is undecidable if P_{2} is reducible to P_{3}  
P_{3} is decidable if P_{3} is reducible to P_{2}'s complement

Option B: If P_{3} is reducible to P_{2}, then P_{3} cannot be harder than P_{2}. But P_{2} being undecidable, this can't say P_{3} is undecidable.
Option C: If P_{2} is reducible to P_{3}, then P_{3} is atleast as hard as P_{2}. Since, P_{2} is undecidable. This means P_{3} is also undecidable.
Question 46 
a group
 
a monoid but not a group
 
a semi group but not a monoid
 
neither a group nor a semi group

The algebraic structure is a group because the given matrix can have inverse and the inverse is nonsingular.
Question 47 
G_{1}  
G_{2}  
G_{3}  
G_{4} 
which is planar
G_{3} can also be drawn as
which is planar
G_{4} can also be drawn as
which is planar
But G_{1} cannot be drawn as planar graph.
Hence, option (A) is the answer.
Question 48 
no solution
 
a unique solution
 
more than one but a finite number of solutions
 
an infinite number of solutions

2(2  20) +1(3 + 5) + 3(12  2)
= 44 + 8 + 30
= 6 ≠ 0
→ A ≠ 0, we have Unique Solution.
Question 49 
1 and 1
 
1 and 6  
2 and 5  
4 and 1

A = (2  λ)(5  λ)  (4) = 0
10  7λ+ λ^{2}  4= 0
λ^{2}  7λ + 6 = 0
λ^{2}  6λ  λ + 6 = 0
(λ  6) 1(λ  6) = 0
λ = 1 (or) 6
Question 50 
i
 
i+1
 
2i  
2^{i} 
Put g(i) = i+1
S = 1 + 2x + 3x^{2} + 4x^{3} + .....
Sx = 1x + 2x^{2} + 3x^{3} + 4x^{4} + ......
S  Sx = 1 + x + x^{2} + x^{3} + .....
[Sum of infinite series in GP with ratio < 1 is a/1r]
S  Sx = 1/(1x)
S(1x) = 1/(1x)
S = 1/(1x)^{2}
Question 51 
(i) Select a box (ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.Given that a ball selected in the above process is a red ball, the probability that it came from the box P is
4/19
 
5/19
 
2/9  
19/30 
Q → 3 red, 1 blue
The probability of selecting a red ball is
(1/3)(2/5) + (2/3)(3/4)
2/15 + 1/2 = 19/30
The probability of selecting a red ball from P
(1/3) * (2/5) = 2/15
→ The colour of ball is selected is to be red and that is taken from the box P.
⇒ Probability of selecting a red ball from P/Probability of selecting a red ball
⇒ (2/15)/(19/30)
⇒ 4/19
Question 52 
1/2^{n}
 
1  1/n
 
1/n!
 
1(1/2^{n})

Hence Probability = (2^{n}  1) /2^{n} = 1  1/2^{n}
Question 53 
{w ∈ {a, b}*  every a in w is followed by exactly two b's}  
{w ∈ {a, b}* every a in w is followed by at least two b’}
 
{w ∈ {a, b}* w contains the substring 'abb'}
 
{w ∈ {a, b}* w does not contain 'aa' as a substring} 
Ex: abbbb, abbb...
Option B: It is True. If a string is to be accepted by given machine then it have atleast two b's.
Option C: It is false. Ex: abba. It contains 'abb' as a substring but not accepted by given machine.
Option D: It is false. Ex: abbab. It is not accepted by TM. It doesn't have 'aa' as a substring but not accepting.
Question 54 
Let N_{f} and N_{p} denote the classes of languages accepted by nondeterministic finite automata and nondeterministic pushdown automata, respectively. Let D_{f} and D_{p} denote the classes of languages accepted by deterministic finite automata and deterministic pushdown automata, respectively. Which one of the following is TRUE?
D_{f} ⊂ N_{f} and D_{p} ⊂ N_{p}
 
D_{f} ⊂ N_{f} and D_{p} = N_{p}  
D_{f} = N_{f} and D_{p} = N_{p}
 
D_{f} = N_{f} and D_{p} ⊂ N_{p}

So D_{f} = N_{f}
NPDA can accept more languages than DPDA.
D_{p} ⊂ N_{p}
Question 55 
L1 = {a^{n}b^{n}c^{m}  n, m > 0} L2 = {a^{n}b^{m}c^{m}  n, m > 0}Which one of the following statements is FALSE?
L_{1} ∩ L_{2} is a contextfree language  
L_{1} ∪ L_{2} is a contextfree language
 
L_{1} and L_{2} are contextfree languages
 
L_{1} ∩ L_{2} is a context sensitive language

CFL is not closed under Intersection.
L_{1} = {a^{n}b^{n}c^{m}  n>0 & m>0}
L_{2} = {a^{m}b^{n}c^{n}  n>0 & m>0}
L_{3} = L_{1} ∩ L_{2}
={a^{n}b^{n}c^{n}  n>0} It is not contextfree.
Question 56 
But, recursive enumerable languages are not closed under complementation.
If L_{1} is recursive, then L_{1}', is also recursive.
If L_{2} is recursive enumerable, then L_{2}', is not recursive enumerable language.
Question 57 
L1 = {ww^{R} w ∈ {0, 1}*} L2 = {w#w^{R}  w ∈ {0, 1}*}, where # is a special symbol L3 = {ww  w ∈ (0, 1}*)Which one of the following is TRUE?
L_{1} is a deterministic CFL
 
L_{2} is a deterministic CFL
 
L_{3} is a CFL, but not a deterministic CFL
 
L_{3} is a deterministic CFL 
→ Given L_{1} is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L_{2} = {w#w^{R}  w ∈ (0,1)*}
→ Given L_{2} is CFL and also DCFL.
→ The string w and w^{R} are separated by special symbol '#'.
→ L_{3} = {ww  w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L_{2} is DCFL. (✔️)
Question 58 
α : Given G(V, E), does G have an independent set of size  V   4? β : Given G(V, E), does G have an independent set of size 5?Which one of the following is TRUE?
α is in P and β is NPcomplete
 
α is NPcomplete and β is in P
 
Both α and β are NPcomplete
 
Both α and β are in P

Question 59 
E → E + n  E × n  nFor a sentence n + n × n, the handles in the rightsentential form of the reduction are
n, E + n and E + n × n
 
n, E + n and E + E × n
 
n, n + n and n + n × n
 
n, E + n and E × n

→ E + n * n {Applying E → E + n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 60 
S → (S)  aLet the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good
n_{1} < n_{2} < n_{3}
 
n_{1} = n_{3} < n_{2}
 
n_{1} = n_{2} = n_{3}
 
n_{1} ≥ n_{3} ≥ n_{2} 
→ LR(1) be the states of LR(1) items.
→ LR(0) items never be greater than LR(1) items then SLR(1) = LALR(1) < LR(1)
n_{1} = (n_{3}) < (n_{2})
Question 61 
int main ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I = 0, I < N, I++); /* Line 3 */ } 
No compilation error
 
Only a lexical error
 
Only syntactic errors
 
Both lexical and syntactic errors

Question 62 
A_{0} A_{1} A_{1}' A_{3} A_{4}
 
A_{0} A_{1} A_{2}' A_{3} A_{4}
 
A_{1} A_{2} A_{2}' A_{3} A_{4}  
A_{1} A_{2}' A_{3} A_{4} A_{5}'

Input will be accepted by the flipflop after the cycle gets finished, because +ve edge is occuring at the end of the clock cycle only.
Question 63 
It computes 1's complement of the input number
 
It computes 2's complement of the input number
 
It increments the input number
 
It decrements the input number

Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111

1000 = I/p

It results 2's complement.
Question 64 
Question 65 
ADD A[R0], @ BThe first operand (destination) "A [R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@ B" uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand). The number of memory cycles needed during the execution cycle of the instruction is
3  
4  
5  
6 
1 → To get 1^{st} operand from memory address (Read).
1 → To get 2^{nd} operand Address (Read).
1 → To get 2^{nd} operand from the address given by previous memory (Read).
1 → To store first operand (Write).
3R + 1W = 4
Question 66 
1 A[1] = B[J]; a Indirect addressing 2 while [*A++]; b Indexed, addressing 3 int temp = *x; c Autoincrement
(1, c), (2, b), (3, a)
 
(1, a), (2, c), (3, b)
 
(1, b), (2, c), (3, a)
 
(1, a), (2, b), (3, c)

Here using the Index.
(b) while [*A++]; Auto increment.
The memory is increments automatically.
(c) int temp = *x; Indirect Addressing.
Here temp is assigned to integer type of Address contained in x.
Question 67 
10, 17
 
10, 22
 
15, 17
 
5, 17

So indexing requires 10 bits.
No. of offset bit required to access 32 byte block = 5
So, No. of TAG bits = 32  10  5 = 17
Question 68 
IF — Instruction fetch from instruction memory, RD — Instruction decode and register read, EX — Execute: ALU operation for data and address computation, MA — Data memory access  for write access, the register read at RD stage is used, WB — Register write back. Consider the following sequence of instructions: I1 : L R0, 1oc1; R0 <= M[1oc1] I2 : A R0, R0; R0 <= R0 + R0 I3 : S R2, R0; R2 <= R2  R0 Let each stage take one clock cycle.What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I1 ?
8  
10  
12  
15 
If we don't use operator forwarding:
Total clock cycles = 8/11
There is no '11' in option.
Then no. of cycles = 8
Question 69 
A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred bytewise. Let the interrupt overhead be 4 μsec. The byte transfer time between the device interfaces register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under programcontrolled mode?
15  
25  
35  
45 
In 1 sec it transfer 10 KB of data = 10 × 10^{3} B = 10^{4}B
Data interrupt overhead = 4μsec = 4×10^{6} sec
Transferring 10KB overhead = 4×10^{6}×10^{4}sec
Performance gain = 1/(4×10^{6}×10^{4}) =10^{2}/4 = 25
Question 70 
10  
25  
40  
50 
It reads 512 * 1024 B in one rotation.
Time taken to read 4B = 153ns
(153) for 4 is approximately = 160
Percentage CPU get blocked = 40*100/160 = 25
Question 71 
Suppose n processes, P_{1}, …., P_{n} share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process P_{i} is s_{i}, where s_{i }> 0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?
If the deadlock will never occcur in the corresponding process then the following condition be true.
Question 72 
if (fork() == 0) { a = a + 5; printf(“%d,%dn”, a, &a); } else { a = a –5; printf(“%d, %dn”, a, &a); }Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?
u = x + 10 and v = y
 
u = x + 10 and v is ≠ y
 
u + 10 = x and v = y
 
u + 10 = x and v ≠ y

u=a5; v be address of a
a=u+5;
x, y values printed by child process.
x=a+5; y be the address of a
x=u+5+5; v=y
x=u+10
Question 73 
4  
6  
7  
9 
Packet size have minimum header overhead.
Question 74 
94  
416  
464  
512 
Round trip propagation delay is RTT = 2*T_{p}
Minimum frame size of Ethernet can be found by using formula T_{t} = 2*T_{p}
Let L is minimum frame size. Then L / 10Mbps = 46.4 μs
L=464 Kbits
It has nothing to do with jamming signal.
Question 75 
2  
3  
4  
5 
R_{1} is one to many.
R_{2} is many to many.
→ E_{1} and E_{2} have separate table because they need to store multiple values.
→ R_{2} also have separate table by considering Primary keys E_{1} and E_{2} as foreign keys.
→ R_{1} is converted to many side table i.e., E_{2} as Primary key and E_{1} as Foreign key.
So, totally we need 3 tables to store the value.
Question 76 
A C  2 4 3 4 4 3 5 2 7 2 9 5 6 4The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:
(3,4) and (6,4)  
(5,2) and (7,2)
 
(5,2), (7,2) and (9,5)
 
(3,4), (4,3) and (6,4)

Totally (5,2), (7,2), (9,5) are also deleted.
Question 77 
select title from book as B where (select count(*) from book as T where T.price > B.price) < 5
Titles of the four most expensive books
 
Title of the fifth most inexpensive book
 
Title of the fifth most expensive book
 
Titles of the five most expensive books

The where clause of outer query will be true for 5 most expensive books.
Question 78 
AE, BE
 
AE, BE, DE
 
AEH, BEH, BCH  
AEH, BEH, DEH 
So only option (D) contains E and H as part of candidate key.
Question 79 
2  
3  
4  
5 
i.e., for load, add and write.
1) Load Y
2) R_{1}, add
3) output to R_{1}
Question 80 
Consider the following data path of a CPU.
The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation  the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR 79. The instruction "call Rn, sub" is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is
Rn < = PC + 1; PC < = M[PC];
The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:
2  
3  
4  
5 
1 cycle → Load PC to MAR
1 cycle → Fetch memory and load to PC

3 cycles

Question 81 
O(1)
 
O(n)  
O(n!)  
O(n^{n})

Time complexity is O(2^{n}).
foo(n) = foo(n1) + foo(n2) + ... + 1
foo(n1) = foo(n2) + foo(n3) + ...
=> foo(n) = 2*foo(n1), foo(0) = 1
=> foo(n) is in O(2^{n}) [By recursion tree method you can solve it].
Question 82 
double foo ( int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } } 
O(1)
 
O(n)
 
O(n^{2})
 
O(n!)

Question 83 
the minimum weighted spanning tree of G
 
the weighted shortest path from s to t
 
each path from s to t
 
the weighted longest path from s to t

Question 84 
a path from s to t in the minimum weighted spanning tree
 
a weighted shortest path from s to t
 
an Euler walk from s to t
 
a Hamiltonian path from s to t

Minimum congestion is the edge with maximum weight among all other edges included in the path.
Now suppose shortest path from A→B is 6, but in MST, we have A→C→B(A→C=4, C→B=3), then along the path in MST, we have minimum congestion i.e., 4.
Question 85 
E → number E.val = number. val  E '+' E E(1).val = E(2).val + E(3).val  E '×' E E(1).val = E(2).val × E(3).valThe above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
It detects recursion and eliminates recursion
 
It detects reducereduce conflict, and resolves
 
It detects shiftreduce conflict, and resolves the conflict in favor of a shift over a reduce action
 
It detects shiftreduce conflict, and resolves the conflict in favor of a reduce over a shift action

Question 86 
E → number E.val = number. val  E '+' E E(1).val = E(2).val + E(3).val  E '×' E E(1).val = E(2).val × E(3).valAssume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?
Equal precedence and left associativity; expression is evaluated to 7
 
Equal precedence and right associativity; expression is evaluated to 9
 
Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7
 
Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9

Hence, the answer is 9 and right associative.
Question 87 
Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3Are all tasks completed in the schedule that gives maximum profit?
All tasks are completed  
T_{1} and T_{6} are left out
 
T_{1} and T_{8} are left out
 
T_{4} and _{6} are left out

T_{3} T_{9} T_{7} T_{2} T_{4} T_{5} T_{8} T_{1} T_{6}
Now the maximum deadline given is 7.
So we will take Array of 7 elements. And will try to put the tasks starting from T_{3} to T_{6}, upto their maximum deadline possible.
So T_{4} and T_{6} are left out.
Question 88 
Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3What is the maximum profit earned?
147  
165  
167  
175 
30+25+23+20+18+16+15 = 147
Question 89 
0D 24  
0D 4D  
4D 0D
 
4D 3D

Convert 0.239 to binary
0.239 * 2 = 0.478
0.478 * 2 = 0.956
0.956 * 2 = 1.912
0.912 * 2 = 1.824
0.824 * 2 = 1.648
0.648 * 2 = 1.296
0.296 * 2 = 0.512
0.512 * 2 = 1.024
Mantissa = (0. 00111101)_{2}
Bias= 64. So biased exponent is 13+64 = 77= (1001101)_{2}
0.239 × 2^{13} = 0 1001101 00111101
= 0100 1101 0011 1101
= 4 D 3 D
Question 90 
0A 20
 
11 34
 
4D D0
 
4A E8

Convert 0.239 to binary
0.239 * 2 = 0.478
0.478 * 2 = 0.956
0.956 * 2 = 1.912
0.912 * 2 = 1.824
0.824 * 2 = 1.648
0.648 * 2 = 1.296
0.296 * 2 = 0.512
0.512 * 2 = 1.024
Mantissa = (0. 00111101)_{2}
0.239 × 2^{13} = 1.11101000 x 2^{10} < Normalized Mantissa
Bias = 64. So biased exponent is 10+64 = 74 = (1001010)_{2}
0.239 × 2^{13} = 0 1001010 11101000
= 0100 1010 1110 1000
= (4 A E 8)_{16}