GATE 2015(Set03)
Question 1 
Extreme focus on syllabus and studying for tests has become such a dominant concern of Indian students that they close their minds to anything _____ to the requirements of the exam
related  
extraneous  
outside  
useful 
Question 1 Explanation:
extraneous irrelevant or unrelated to the subject being dealt with.
Question 2 
A function f(x) is linear and has a value of 29 at x = 2 and 39 at x = 3. Find its value at x = 5.
59  
45  
43  
35 
Question 2 Explanation:
f(x)=2x+33
Question 3 
The Tamil version of ________ John Abrahamstarrer Madras café ________ cleared by the Censor Board with no cuts last week but the film’s distributors _________ no takers among the exhibitors for a release in Tamil Nadu _________ this Friday.
Mr., was, found, on  
a, was, found, at  
the, was, found, on  
a, being, find at 
Question 3 Explanation:
JohnAbraham starrer Madras Café talks about the movie not the person, so Mr. is ruled out. ‘Find no takers’ is not the correct phrase. At this Friday is incorrect. So, option C is correct.
Question 4 
If ROAD is written as URDG, then SWAN should be written as:
VXDQ  
VZDQ  
VZDP  
UXDQ 
Question 4 Explanation:
R+3=U, O+3=R, A+3=D, D+3=G;
S+3=V, W+3=Z, A+3=D, N+3=Q.
S+3=V, W+3=Z, A+3=D, N+3=Q.
Question 5 
Select the pair that best expresses a relationship similar to that expressed in the pair: Children: Pediatrician
Adult: Orthopedist  
Females: Gynecologist  
Kidney: Nephrologist  
Skin: Dermatologist 
Question 5 Explanation:
Community of people: Doctor
Question 6 
2006  
2007  
2008  
2009 
Question 6 Explanation:
Increase in exports in 2006 = 100  70/70 = 42.8%
Increase in imports in 2006 = 120  90/90 = 33.3% which is more than any other year.
Increase in imports in 2006 = 120  90/90 = 33.3% which is more than any other year.
Question 7 
PHome, QPower, RDefense, STelecom, TFinance  
RHome, SPower, PDefense, QTelecom, TFinance  
PHome, QPower, TDefense, STelecom, UFinance  
QHome, UPower, TDefense, RTelecom, PFinance 
Question 7 Explanation:
Since U does not want any portfolio, (C) and (D) are ruled out. R wants Home, or Finance or No portfolio, (A) is not valid. Hence option (B) is correct
Question 8 
x=yy
 
x=(yy)  
x=y+y
 
x=(y+y) 
Question 8 Explanation:
Verify which of the options satisfies the x=2 when y=1.
Then the Answer is x =  (y  y)
Then the Answer is x =  (y  y)
Question 9 
(iii) and (iv)  
(ii) and (iii)  
(i), (ii) and (iii)  
(ii) only 
Question 9 Explanation:
Statement (ii) and (iii) are True.
→ He is unlikely due to lack of requisite temperament  (ii) is True
→ He was guilty of throwing away his wicket severral times  (iii) is True
→ He is unlikely due to lack of requisite temperament  (ii) is True
→ He was guilty of throwing away his wicket severral times  (iii) is True
Question 10 
Alexander turned his attention towards India, since he had conquered Persia. Which one of the statements below is logically valid and can inferred from the above sentence?
Alexander would not have turned his attention towards India had he not conquered Persia.  
Alexander was not ready to rest on his laurels, and wanted to march to India  
Alexander was completely in control of his army and could command it to move towards India  
Since Alexander’s kingdom extended to Indian borders after the conquest of Persia, he was keen to move further 
Question 10 Explanation:
Let X be "Alexander turned his attention towards India"
Y be " he had conquered Persia"
Like that
∼X be "Alexander would not have turned his attention towards India"
then
∼Y be "he had not conquered Persis"
Answer is option A.
Y be " he had conquered Persia"
Like that
∼X be "Alexander would not have turned his attention towards India"
then
∼Y be "he had not conquered Persis"
Answer is option A.
Question 11 
The result is head  
The result is tail
 
If the person is of Type 2, then the result is tail  
If the person is of Type 1, then the result is tail 
Question 11 Explanation:
We do not know the type of person from whom those words are coming from and so we can have two cases.
Case 1:
The person who speaks truth. This definitely implies that result of toss is Head.
Case 2:
The person who lies. In this the reality will be the negation of the statement.
The negation of (x⇔y) is exactly one of x or y holds. "The result of the toss is head if and only if I am telling the truth". So here two possibilities are there,
→ It is head and lie spoken.
→ It is not head and truth spoken.
Clearly, the second one cannot speaks the truth. So finally it is head.
Hence, option (A).
Case 1:
The person who speaks truth. This definitely implies that result of toss is Head.
Case 2:
The person who lies. In this the reality will be the negation of the statement.
The negation of (x⇔y) is exactly one of x or y holds. "The result of the toss is head if and only if I am telling the truth". So here two possibilities are there,
→ It is head and lie spoken.
→ It is not head and truth spoken.
Clearly, the second one cannot speaks the truth. So finally it is head.
Hence, option (A).
Question 12 
{P,R}→{S,T}  
{P,R}→{R,T}  
{P,S}→{S}  
{P,S,U}→{Q} 
Question 12 Explanation:
X→Y is trivial if Y⊆ X
Question 13 
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.
80  
70  
60  
50 
Question 13 Explanation:
Load factor(α) = no. of elements/no. of slots = 2000/25 = 80
Question 14 
612.06  
612.07  
612.08  
612.09 
Question 14 Explanation:
Note: Out of Syllabus.
Question 15 
Only I is correct  
Only I and III are correct  
Only II and III are correct  
All of I, II and III are correct

Question 15 Explanation:
In TCP, as sender and receiver can send segments at the same time, It is FULLDUPLEX.
TCP can use selective ACK and
TCP uses byte streams that is every byte is send using TCP is numbered.
Question 16 
Suppose U is the power set of the set S = {1, 2, 3, 4, 5, 6}. For any T ∈ U, let T denote the number of element in T and T' denote the complement of T. For any T, R ∈ U, let T \ R be the set of all elements in T which are not in R. Which one of the following is true?
∀X ∈ U (X = X')  
∃X ∈ U ∃Y ∈ U (X = 5, Y = 5 and X ∩ Y = ∅)  
∀X ∈ U ∀Y ∈ U (X = 2, Y = 3 and X \ Y = ∅)  
∀X ∈ U ∀Y ∈ U (X \ Y = Y' \ X') 
Question 16 Explanation:
As X and Y are elements of U, so X and Y are subsets of S.
(A) False. Consider X = {1,2}. Therefore, X' = {3,4,5,6}, X = 2 and X' = 4.
(B) False. Because for any two possible subsets of S with 5 elements should have atleast 4 elements in commonc. Hence X∩Y cannot be null.
(C) False. Consider X = {1,4}, Y= {1,2,3} then X\Y = {4} which is not null.
(D) True. Take any possible cases.
(A) False. Consider X = {1,2}. Therefore, X' = {3,4,5,6}, X = 2 and X' = 4.
(B) False. Because for any two possible subsets of S with 5 elements should have atleast 4 elements in commonc. Hence X∩Y cannot be null.
(C) False. Consider X = {1,4}, Y= {1,2,3} then X\Y = {4} which is not null.
(D) True. Take any possible cases.
Question 17 
Among simple LR (SLR), canonical LR, and lookahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?
SLR, LALR
 
Canonical LR, LALR
 
SLR, canonical LR
 
LALR, canonical LR 
Question 17 Explanation:
SLR is very easy to implement and CLR is most powerful method.
Question 18 
4  
5  
2  
3 
Question 18 Explanation:
Let's first draw heap from the given array,
→ Swap 100 & 15
→ Swap 100 & 50
→ Swap 89 & 100
∴ Total 3 interchanges are needed.
→ Swap 100 & 15
→ Swap 100 & 50
→ Swap 89 & 100
∴ Total 3 interchanges are needed.
Question 19 
The maximum number of processes that can be in Ready state for a computer system with n CPUs is
n  
n^{2}  
2^{n}  
Independent of n 
Question 19 Explanation:
Number of processes which are in running processes will be atmost n as there are n processors.
Maximum number of processes that will be in ready state is independent of number of processors.
Maximum number of processes that will be in ready state is independent of number of processors.
Question 20 
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
65
 
67
 
69
 
83 
Question 20 Explanation:
Question 21 
WHERE P1.capacity >= All (select P2.capacity from Cinema P2)  
WHERE P1.capacity >= Any (select P2.capacity from Cinema P2)  
WHERE P1.capacity > All (select max(P2.capacity) from Cinema P2)  
WHERE P1.capacity > Any (select max(P2.capacity) from Cinema P2) 
Question 21 Explanation:
Inner query collects capacities of all the theatres and in outer query we are filtering the tuples with the condition “capacity >= All”.
So the theatres which are having maximum capacity will satisfy the condition.
So the theatres which are having maximum capacity will satisfy the condition.
Question 23 
12  
120400  
1204  
1034 
Question 23 Explanation:
p = s1+2;
p now points to third element in s1, i.e., '3'.
*p = '0', will make value of '3' as '0' in s1. And finally s1 will become 1204.
p now points to third element in s1, i.e., '3'.
*p = '0', will make value of '3' as '0' in s1. And finally s1 will become 1204.
Question 24 
The number of 4 digit numbers having their digits in nondecreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is _____ .
15  
16  
17  
18 
Question 24 Explanation:
Just try to write all the four digit numbers containing the digits 1, 2 and 3 only, in decreasing order.
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 3 3
1 2 2 2
1 2 2 3
1 2 3 3
1 2 3 3
1 3 3 3
2 2 2 2
2 2 2 3
2 2 3 3
2 3 3 3
3 3 3 3
Hence, total 15 4digit no. are possible.
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 3 3
1 2 2 2
1 2 2 3
1 2 3 3
1 2 3 3
1 3 3 3
2 2 2 2
2 2 2 3
2 2 3 3
2 3 3 3
3 3 3 3
Hence, total 15 4digit no. are possible.
Question 25 
{α(4,2,1)  α≠0, α∈R}  
{α(4,2,1)  α≠0, α∈R}  
{α(2,0,1)  α≠0, α∈R}  
{α(2,0,1)  α≠0, α∈R} 
Question 25 Explanation:
X be an eigen vector corresponding to eigen value λ =1, then
AX = λX ⇒ (A  I)X = 0
⇒ y+2z = 0 and x+2y = 0
⇒ y = 2z and x/(2) = y
∴ x/(2) = y = 2z ⇒ x/(4) = y/2 = z/1 = α(say)
∴ Eigen vectors are {α(4,2,1  α≠0, α∈R}
AX = λX ⇒ (A  I)X = 0
⇒ y+2z = 0 and x+2y = 0
⇒ y = 2z and x/(2) = y
∴ x/(2) = y = 2z ⇒ x/(4) = y/2 = z/1 = α(say)
∴ Eigen vectors are {α(4,2,1  α≠0, α∈R}
Question 26 
E, 201  
F, 201  
E, E20  
2, 01F 
Question 26 Explanation:
Block size is of 16 bytes, so we need 4 offset bits. So the lowest 4 bit is offset bits.
ac No. of cache lines in cache is 2^{12} bytes which needs 12 bits. So next lower 12 bits are line indexing bits.
And the remaining top 4 bits are tag bits (out of 20). So answer is (A).
ac No. of cache lines in cache is 2^{12} bytes which needs 12 bits. So next lower 12 bits are line indexing bits.
And the remaining top 4 bits are tag bits (out of 20). So answer is (A).
Question 27 
The result evaluating the postfix expression 10 5 + 60 6 / * 8  is
284  
213  
142  
71 
Question 27 Explanation:
→ '10' is pushed in the stack
→ '5' is pushed in the stack
→ '+' comes so addition will be done by popping the top two elements in the stackand the result is pushed back into the stack, i.e., 10+5 = 15
→ 60 pushed in the stack
→ 6 pushed in the stack
→ '/' comes. So, 60/6 = 10
→ '*' comes. So, 15 * 10 = 150
→ '8' comes, push in the stack
→ '' comes. So, 1508 = 142
So the final result is 142.
→ '5' is pushed in the stack
→ '+' comes so addition will be done by popping the top two elements in the stackand the result is pushed back into the stack, i.e., 10+5 = 15
→ 60 pushed in the stack
→ 6 pushed in the stack
→ '/' comes. So, 60/6 = 10
→ '*' comes. So, 15 * 10 = 150
→ '8' comes, push in the stack
→ '' comes. So, 1508 = 142
So the final result is 142.
Question 28 
Consider a CSMA/CD network that transmits data at a rate of 100 Mbps (10^{8} bits second) over a 1 km (kilometer) cable with no repeaters. If the minimum frame size required for this network is 1250 bytes, what is the signal speed (km/sec) in the cable?
8000  
10000  
16000  
20000 
Question 28 Explanation:
Given: L = 1250 Bytes
B = 100 Mbps
d = 1 km
v = ?
In CSMA/CD, L = 2×d/v×B
⇒ v = 2dB/L = 2×10^{3}×10^{8}/10^{4}
⇒ v = 20,000 km/sec
B = 100 Mbps
d = 1 km
v = ?
In CSMA/CD, L = 2×d/v×B
⇒ v = 2dB/L = 2×10^{3}×10^{8}/10^{4}
⇒ v = 20,000 km/sec
Question 29 
Consider a software program that is artificially seeded with 100 faults. While testing this program, 159 faults are detected, out of which 75 faults are from those artificially seeded faults. Assuming that both are and seeded faults are of same nature and have same distribution, the estimated number of undetected real fault is _____ .
175  
176  
177  
178 
Question 29 Explanation:
Note: Out of Syllabus.
Question 30 
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____ .
199  
198  
197  
196 
Question 30 Explanation:
A binary tree T with n leaf nodes have exactly (n  1) nodes that have exactly two children.
Question 31 
4  
5  
6  
8 
Question 31 Explanation:
No. of states in DFA accepting L and complement of L is same. So let's draw minimal DFA for L,
So, 5 states are there.
So, 5 states are there.
Question 32 
Question 32 Explanation:
Given,
af(x) + bf(1/x) = 1/x  25  (1)
Put x = 1/x,
af(1/x) + bf(x) = x  25  (2)
Multiply equation (1) with 'a' and Multiply equation (2) with 'b', then
abf(1/x) + a^{2} = a/x  25a  (3)
abf(1/x) + b^{2} = bk  25b  (4)
Subtract (3)  (4), we get
(a^{2}  b^{2}) f(x) = a/x 25a  bx + 25b
f(x) = 1/(a^{2}  b^{2}) (a/x  25a  bx +25b)
Now from equation,
Hence option (A) is the answer.
af(x) + bf(1/x) = 1/x  25  (1)
Put x = 1/x,
af(1/x) + bf(x) = x  25  (2)
Multiply equation (1) with 'a' and Multiply equation (2) with 'b', then
abf(1/x) + a^{2} = a/x  25a  (3)
abf(1/x) + b^{2} = bk  25b  (4)
Subtract (3)  (4), we get
(a^{2}  b^{2}) f(x) = a/x 25a  bx + 25b
f(x) = 1/(a^{2}  b^{2}) (a/x  25a  bx +25b)
Now from equation,
Hence option (A) is the answer.
Question 33 
Only S1  
Only S2  
Both S1 and S2  
Neither S1 nor S2 
Question 33 Explanation:
For LL(1),
For first production,
So, there is 'c' common in both the first(s) in the production of S. So not LL(1).
For LR(1),
Since RR conflict is present. So, not LR(1).
Hence, Option (D) is the correct answer.
For first production,
So, there is 'c' common in both the first(s) in the production of S. So not LL(1).
For LR(1),
Since RR conflict is present. So, not LR(1).
Hence, Option (D) is the correct answer.
Question 34 
T2 must be aborted and then both T1 and T2 must be restarted to ensure transaction atomicity  
Schedule S is nonrecoverable and cannot ensure transaction atomicity  
Only T2 must be aborted and then restarted to ensure transaction atomicity  
Schedule S is recoverable and can ensure atomicity and nothing else needs to be done 
Question 34 Explanation:
T2 is reading the value written by T1 and getting committed before T1 commits. So it is nonrecoverable schedule.
Question 35 
Consider a B^{+} tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each nonleaf node of the tree is ____ .
50  
60  
70  
80 
Question 35 Explanation:
Explanation:
Suppose that ‘k’ is order of the nonleaf node
k(8) + (k1)12 ≤ 1024
20k ≤1036
k ≤ ⌊1036/20⌋ ⇒ k ≤ 51
As the order is 51, maximum we can store 50 keys.
k(8) + (k1)12 ≤ 1024
20k ≤1036
k ≤ ⌊1036/20⌋ ⇒ k ≤ 51
As the order is 51, maximum we can store 50 keys.
Question 36 
Suppose X_{i} for i = 1, 2, 3 are independent and identically distributed random variables whose probability mass functions are Pr[X_{i }= 0] = Pr[X_{i }= 1]=1/2 for i = 1, 2, 3. Define another random variable Y = X_{1}X_{2} ⊕ X_{3}, where ⊕ denotes XOR. Then Pr[Y = 0X_{3} = 0] = _______________.
0.75  
0.76  
0.77  
0.78 
Question 36 Explanation:
Pr(Y=0/ X_{3}=0) = Pr(Y=0 ∩ X_{3}=0)/ Pr(X_{3}=0)
= 3/8 / 4/8 = 3/4 = 0.75
Question 37 
The total number of prime implicants of the function f(w,x,y,z) = Σ(0, 2, 4, 5, 6, 10) is ______.
3  
4  
2  
1 
Question 37 Explanation:
Total 3 prime implicants are there.
Question 39 
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
256  
512  
1024  
2048 
Question 39 Explanation:
Time complexity of merge sort = O(n log n) = an log n
where c is some constant
It is given that for n = 64,
cn log n = 30
c × 64 log 64 = 30
c × 64 × 6 = 30
c = 5/64
Now, the value of n for
c n log n = 360
5/64 × n log n = 360
n log n = 360×64/5
= 72 × 64 = 2^{9} × 9
So for n = 2^{9}, it satisfies.
So, n = 2^{9} = 512
where c is some constant
It is given that for n = 64,
cn log n = 30
c × 64 log 64 = 30
c × 64 × 6 = 30
c = 5/64
Now, the value of n for
c n log n = 360
5/64 × n log n = 360
n log n = 360×64/5
= 72 × 64 = 2^{9} × 9
So for n = 2^{9}, it satisfies.
So, n = 2^{9} = 512
Question 40 
309.33  
309.34  
309.35  
309.36 
Question 40 Explanation:
Let ‘S’ be the distance covered in 20 minutes, then by simpson’s 1/3^{rd} rule,
∵v = velocity
= 2/3[(0+0)+4(10+25+32+11+2)+2(18+29+20+5)]
= 309.33 km
(Here length of each of the subinterval is h = 2)
∵v = velocity
= 2/3[(0+0)+4(10+25+32+11+2)+2(18+29+20+5)]
= 309.33 km
(Here length of each of the subinterval is h = 2)
Question 41 
140  
150  
160  
170 
Question 41 Explanation:
**ptr = 40
∴ printf (“%d%d”, p + r – p, p + r) will print 140.
Question 42 
Any one of I and III but not II or IV  
Any one of I, III, and IV but not II  
Any one of II and III but not I or IV  
Any one of I, II, III, and IV p 
Question 42 Explanation:
All are deadlock prevention strategies.
Question 43 
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________.
995  
996  
997  
998 
Question 43 Explanation:
G has 100 vertices ⇒ spanning tree contain 99 edges given, weight of a minimum spanning tree of G is 500 since, each edge of G is increased by five.
∴ Weight of a minimum spanning tree becomes 500 + 5 ⨯ 99= 995
Question 44 
pq+r = 0 or p = q = r  
p+qr = 0 or p = q = r
 
p+q+r = 0 or p = q = r  
pq+r = 0 or p = q = r 
Question 44 Explanation:
For nontrivial solution the value of determinant should be zero.
Question 45 
Consider a network connected two systems located 8000 kilometers apart. The bandwidth of the network is 500 × 10^{6} bits per second. The propagation speed of the media is 4 × 10^{6} meters per second. It is needed to design a GoBackN sliding window protocol for this network. The average packet size is 10^{7} bits. The network is to be used to its full capacity. Assume that processing delays at nodes are negligible. Then the minimum size in bits of the sequence number field has to be ___________.
8  
7  
6  
5 
Question 45 Explanation:
η=100%
n = ?
∴a=T_{p}/T_{n} =2/0.02=100
Given Protocol, GobackN protocol, So η = w/(1+2a) where w = 2^{n}1
100/100 = w/(1+2a) ⇒ w = 1+2a
⇒ 2^{(n1)} = 1+2(100)
⇒ 2^{n}  1 = 201
⇒ 2^{n} = 202 ⇒ 2^{n} = 2^{8}
⇒ n = 8
n = ?
∴a=T_{p}/T_{n} =2/0.02=100
Given Protocol, GobackN protocol, So η = w/(1+2a) where w = 2^{n}1
100/100 = w/(1+2a) ⇒ w = 1+2a
⇒ 2^{(n1)} = 1+2(100)
⇒ 2^{n}  1 = 201
⇒ 2^{n} = 202 ⇒ 2^{n} = 2^{8}
⇒ n = 8
Question 46 
II only  
III only  
I and IV only  
I only 
Question 46 Explanation:
L_{2} ≤ pL_{4}
L_{1} ≤ pL_{2}
If L_{4} ∈ P then L_{2} ∈ P hence L_{1} ∈ P, hence option C.
L_{1} ≤ pL_{2}
If L_{4} ∈ P then L_{2} ∈ P hence L_{1} ∈ P, hence option C.
Question 47 
4  
5  
6  
7 
Question 47 Explanation:
Minimum average latency is based on an advanced concept in pipelining.
S1 is needed at time 1 and 5, so its forbidden latency is 51 = 4.
S2 is needed at time 2 and 4, so its forbidden latency is 42 = 2.
So, forbidden latency = (2,4,0) (0 by default is forbidden)
Allowed latency = (1,3,5) (any value more than 5 also).
Collision vector (4,3,2,1,0) = 10101 which is the initial state as well.
From initial state we can have a transition after "1" or "3" cycles and we reach new states with collision vectors
(10101 >> 1 + 10101 = 11111) and (10101 >> 3 + 10101 = 10111) respectively.
These 2 becomes states 2 and 3 respectively.
For "5" cycles we come back to state 1 itself.
From state 2 (11111), the new collision vector is 11111.
We can have a transition only when we see first 0 from right.
So, here it happens on 5th cycle only which goes to initial state. (Any transition after 5 or more cycles goes to initial state as we have 5 time slices).
From state 3 (10111), the new collision vector is 10111.
So, we can have a transition on 3, which will give (10111 >> 3 + 10101 = 10111) third state itself. For 5, we get the initial state.
Thus all the transitions are complete. State\Time 1 3 5 1 (10101) 2 3 1 2 (11111)   1 3 (10111)  3 1 So, minimum length cycle is of length 3 either from 33 or from 13. So the minimum average latency is also 3.
S1 is needed at time 1 and 5, so its forbidden latency is 51 = 4.
S2 is needed at time 2 and 4, so its forbidden latency is 42 = 2.
So, forbidden latency = (2,4,0) (0 by default is forbidden)
Allowed latency = (1,3,5) (any value more than 5 also).
Collision vector (4,3,2,1,0) = 10101 which is the initial state as well.
From initial state we can have a transition after "1" or "3" cycles and we reach new states with collision vectors
(10101 >> 1 + 10101 = 11111) and (10101 >> 3 + 10101 = 10111) respectively.
These 2 becomes states 2 and 3 respectively.
For "5" cycles we come back to state 1 itself.
From state 2 (11111), the new collision vector is 11111.
We can have a transition only when we see first 0 from right.
So, here it happens on 5th cycle only which goes to initial state. (Any transition after 5 or more cycles goes to initial state as we have 5 time slices).
From state 3 (10111), the new collision vector is 10111.
So, we can have a transition on 3, which will give (10111 >> 3 + 10101 = 10111) third state itself. For 5, we get the initial state.
Thus all the transitions are complete. State\Time 1 3 5 1 (10101) 2 3 1 2 (11111)   1 3 (10111)  3 1 So, minimum length cycle is of length 3 either from 33 or from 13. So the minimum average latency is also 3.
Question 48 
In the network 200.10.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is ____________.
158  
157  
156  
155 
Question 48 Explanation:
No. of bit in HID part = 3227 = 5 bits
Subnet mask is 255.255.255.224
Do AND with given IP and subnet mask then we get NID 200.10.11.128
In fourth octet first three bit will fixed for subnet and remaining 5 bits is for HID, so maximum value as 11111.
The address with all 1s in host part is broadcast address and can't be assigned to a host.
So the maximum possible last octal in a host IP is 10011110 which is 158.
Subnet mask is 255.255.255.224
Do AND with given IP and subnet mask then we get NID 200.10.11.128
In fourth octet first three bit will fixed for subnet and remaining 5 bits is for HID, so maximum value as 11111.
The address with all 1s in host part is broadcast address and can't be assigned to a host.
So the maximum possible last octal in a host IP is 10011110 which is 158.
Question 49 
L_{1} and L_{2} only  
L_{1} and L_{3} only  
L_{2} and L_{3} only  
L_{3} only 
Question 49 Explanation:
L_{1}: First push all the a's in the stack then push all the b's in the stack. Now pop all the b's from the stack watching next no. of a's. And then pop all the a's from the stack watching next no. of b's. So can be done by PDA, hence CFL.
L_{2}: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparision with the next b's. So not CFL.
L_{3}: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
L_{2}: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparision with the next b's. So not CFL.
L_{3}: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Question 50 
10  
11  
12  
13 
Question 50 Explanation:
j = 2*3 / 4+2.0 / 5+8 / 5;
= 6 / 4+2.0 / 5+1;
= 1 + 0.4 + 1
= 2.4
But since j is integer,
j=2
Now,
k = k  (j)
k = 0  (1) = 1
When i=0, i+k = 1,
printf executed 1 time
When i=1, i+k = 0,
printf executed 1 time
When i=2, i+k = 1,
printf executed 3 times
When i=3, i+k = 2,
printf executed 3 times
When i=4, i+k = 3,
printf executed 2 times
∴ Total no. of times printf executed is,
1 + 1 + 3 + 3 + 2 = 10
= 6 / 4+2.0 / 5+1;
= 1 + 0.4 + 1
= 2.4
But since j is integer,
j=2
Now,
k = k  (j)
k = 0  (1) = 1
When i=0, i+k = 1,
printf executed 1 time
When i=1, i+k = 0,
printf executed 1 time
When i=2, i+k = 1,
printf executed 3 times
When i=3, i+k = 2,
printf executed 3 times
When i=4, i+k = 3,
printf executed 2 times
∴ Total no. of times printf executed is,
1 + 1 + 3 + 3 + 2 = 10
Question 51 
230  
240  
250  
260 
Question 51 Explanation:
x = x + f1( ) + f2( ) + f3( ) + f4( )
f1( ) = 25 + 1 = 26
f2( ) = 50 + 1 = 51
f3( ) = 10 × 10 = 100
f2( ) = 51 × 1 = 52 (Since here x is static variable so old value retains)
∴ x = 1+26+51+100+52 = 230
f1( ) = 25 + 1 = 26
f2( ) = 50 + 1 = 51
f3( ) = 10 × 10 = 100
f2( ) = 51 × 1 = 52 (Since here x is static variable so old value retains)
∴ x = 1+26+51+100+52 = 230
Question 52 
Only S1 is true  
Only S2 is true  
Only S1 and S3 are true  
Only S2 and S3 are true 
Question 52 Explanation:
S1: False. Antidependency means WAR dependency. There is no WAR dependency between I_{2} and I_{5}.
S2: True. There is WAR dependency between I_{2} and I_{4}.
S3: False. Because WAR or antidependency can be resolved by register renaming.
S2: True. There is WAR dependency between I_{2} and I_{4}.
S3: False. Because WAR or antidependency can be resolved by register renaming.
Question 53 
Two hosts are connected via a packet switch with 10^{7} bits per second links. Each link has a propagation delay of 20 microseconds. The switch begins forwarding a packet 35 microseconds after it receives the same. If 10000 bits of data are to be transmitted between the two hosts using a packet size of 5000 bits, the time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is _______.
(1575)  
(1576)  
(1577)  
(1578) 
Question 53 Explanation:
Given that there is a single switch between the source and destination.
Bandwidth of the each link is 10^{7} bits/sec.
Given that propagation delay between host to switch and switch to host is same i.e. 20 microseconds.
Given that 35 microseconds of buffering time is required by the switch.
Total data we need to send is 10000 bits.
Given that packet size is 5000 bits.
Number of packets we need to send is 10000/5000 = 2 packets.
Total time for the first packet to reach from source to switch = Transmission time + propagation time
Transmission time=(5000 bits)/(10^{7} bits/sec)=500 microseconds
Total time between source to switch is = 500 + 20 = 520 microseconds
Time required for the packet to reach from switch to destination is = Buffer time+Transmission time + propagation time = 35 + 500 + 20 = 555 microseconds.
Total time required for the first packet to reach to destination from the source = 520 + 555 =1075 microseconds.
While transferring first packet from switch to destination source starts sending of it's second packet to switch, that means from 1055 microsecond on wards transmission of 2nd packet is started by the source.
By the time first packet is reached to the destination 2nd packet is completely available at the switch.
Time required for the 2nd packet to reach to the destination from the switch is
= transmission time + propagation time = 500+20 = 520 microseconds
Therefore total time required for the two packets to reach to destination from the source = 1055+ 520 = 1575 microseconds.
Bandwidth of the each link is 10^{7} bits/sec.
Given that propagation delay between host to switch and switch to host is same i.e. 20 microseconds.
Given that 35 microseconds of buffering time is required by the switch.
Total data we need to send is 10000 bits.
Given that packet size is 5000 bits.
Number of packets we need to send is 10000/5000 = 2 packets.
Total time for the first packet to reach from source to switch = Transmission time + propagation time
Transmission time=(5000 bits)/(10^{7} bits/sec)=500 microseconds
Total time between source to switch is = 500 + 20 = 520 microseconds
Time required for the packet to reach from switch to destination is = Buffer time+Transmission time + propagation time = 35 + 500 + 20 = 555 microseconds.
Total time required for the first packet to reach to destination from the source = 520 + 555 =1075 microseconds.
While transferring first packet from switch to destination source starts sending of it's second packet to switch, that means from 1055 microsecond on wards transmission of 2nd packet is started by the source.
By the time first packet is reached to the destination 2nd packet is completely available at the switch.
Time required for the 2nd packet to reach to the destination from the switch is
= transmission time + propagation time = 500+20 = 520 microseconds
Therefore total time required for the two packets to reach to destination from the source = 1055+ 520 = 1575 microseconds.
Question 54 
Let R be a relation on the set of ordered pairs of positive integers such that ((p,q),(r,s)) ∈ R if and only if p  s = q  r. Which one of the following is true about R?
Both reflexive and symmetric  
Reflexive but not symmetric  
Not reflexive but symmetric  
Neither reflexive nor symmetric 
Question 54 Explanation:
Since pq ≠ qp
∴(p,q) R (p,q)
⇒ R is not reflexive.
Let (p,q) R (r,s) then ps = qr
⇒ rq = sp
⇒ (r,s) R (p,q)
⇒ R is symmetric.
∴(p,q) R (p,q)
⇒ R is not reflexive.
Let (p,q) R (r,s) then ps = qr
⇒ rq = sp
⇒ (r,s) R (p,q)
⇒ R is symmetric.
Question 55 
First Come First Serve
 
Nonpreemptive Shortest Job First  
Shortest Remaining Time  
Round Robin with Quantum value two 
Question 55 Explanation:
FCFS:
TAT for A = completion time(A)  AT(A) = 3  0 = 3
TAT of B = 9  1 = 8
TAT of C = 13  4 = 9
TAT of D = 15  6 = 9
∴ Avg. TAT = 29/4
SJF:
TAT of A = 3  0 = 3
TAT of B = 9  1 = 8
TAT of C = 15  4 = 11
TAT of D = 11  6 = 5
∴ Avg. TAT = 27/4
SRTF:
TAT of A = 3  0 = 3
TAT of B = 15  1 = 14
TAT of C = 8  4 = 4
TAT of D = 10  6 = 4
∴ Avg. TAT = 25/4
RR:
TAT of A = 5  0 = 5
TAT of B = 15  1 = 14
TAT of C = 13  4 = 9
TAT of D = 11  6 = 5
∴ Avg. TAT = 33/4
∴ SRTF has lowest Avg. TAT.
There are 55 questions to complete.