Gate 2012

Question 1
A
Both I1 and I2 are correct inferences
B
I1 is correct but I2 is not a correct inference
C
I1 is not correct but I2 is a correct inference
D
Both I1 and I2 are not correct inferences
Question 1 Explanation: 
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Let p = it rains
q = playing cricket/ match played
If (it rains) then (the match will not be played)
p ⇒ (∼q)
Inference: There was no rain. (i.e., p = F)
So for any F ⇒ (∼q) is true.
So this inference is valid.
I2: If it rains then the cricket match will not be played.
It did not rain.
p ⇒ (∼q)
Inference: The cricket match was played.
q = T
p ⇒ (∼q)
p ⇒ (∼T)
p ⇒ F
This is false for p = T, so this is not true.
Question 2
Which of the following is TRUE?  
A
Every relation in 3NF is also in BCNF
B
A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R
C
Every relation in BCNF is also in 3NF
D
No relation can be in both BCNF and 3NF
Question 2 Explanation: 
BCNF is a stronger version 3NF. So straight from definition of BCNF every relation in BCNF will also be in 3NF.
Question 3
A
No Choice
B
Choice A
C
D
Program gives no output as it is erroneous
Question 3 Explanation: 
Everything in the switch will be executed, because there is no break; statement after case ‘A’. So it executes all the subsequent statements until it find a break;
So,
→ Choice A
→ Choice B. No choice. Is the output.
Question 4
Assuming P ≠ NP, which of the following is TRUE?
A
NP-complete = NP
B
NP-complete ∩ P = ∅
C
NP-hard = NP
D
P = NP-complete
Question 4 Explanation: 
Note: Out of syllabus.
The definition of NP-complete is,
A decision problem p is NP-complete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
Question 5
The worst case running time to search for an element in a balanced binary search tree with n2n elements is
A
Θ (n log n)
B
Θ (n2n)
C
Θ (n)
D
Θ (log n)
Question 5 Explanation: 
→ Worst case running time to search for an element in a balanced binary search tree of ‘n’ elements is (log n).
→ No of elements = n.2n then search time = (log n.2n)
= (log n + log 2n)
= (log n + n log 2)
= O(n)
Question 6
A
X
B
X + Y
C
X ⊕ Y
D
Y
Question 6 Explanation: 
f(X,Y)=XY’ + XY = X(Y’ + Y) = X
Question 7
The decimal value 0.5 in IEEE single precision floating point representation has
A
fraction bits of 000…000 and exponent value of 0
B
fraction bits of 000…000 and exponent value of −1
C
fraction bits of 100…000 and exponent value of 0
D
no exact representation
Question 7 Explanation: 
(0.5)10 = (1.0)2 × 2–1
So, value of the exponent = -1
and
fraction is 000…000 (Implicit representation)
Question 8
A
3
B
4
C
7
D
8
Question 8 Explanation: 
The no. of child process created = 2n -1 = 23 -1 = 7 (where n is number of fork() statements)
7 are child processes.
Question 9
Consider the function f(x) = sin(x) in the interval x ∈ [π/4, 7π/4]. The number and location(s) of the local minima of this function are  
A
One, at π/2
B
One, at 3π/2
C
Two, at π/2 and 3π/2
D
Two, at π/4 and 3π/2
Question 9 Explanation: 
f(x) = sin x
f’(x) = cos x

[just consider the given interval (π/4, 7π/4)]
f'(x) = 0 at π/2, 3π/2
To get local minima f ’’(x) > 0, f ’’(x) = - sin x
f ’’(x) at π/2, 3π/2
f ’’(x) = -1< 0 local maxima
f ’’ (3π/2) = 1 > 0 this is local minima
In the interval [π/4, π/2] the f(x) is increasing, so f(x) at π/4 is also a local minima.
So there are two local minima for f(x) at π/4, 3π/2.
Question 10
The protocol data unit (PDU) for the application layer in the Internet stack is
A
Segment
B
Datagram
C
Message
D
Frame
Question 10 Explanation: 
The PDU for Data Link layer, Network layer, Transport layer and Application layer are frame, datagram, segment and message respectively.
Question 11
Let  be the 2×2 matrix with elements a11 = a12 = a21 = +1 and a22 = -1. Then the eigenvalues of the matrix A19 are
A
1024 and -1024
B
1024√2 and -1024√2
C
4√2 and -4√2
D
512√2 and -512√2
Question 11 Explanation: 
a11=a12=a21=1, a22=-1
The 2×2 matrix =
Cayley Hamilton theorem:
If matrix A has ‘λ’ as eigen value, An has eigen value as λn.
Eigen value of
|A-λI| = 0

-(1-λ)(1+λ)-1=0
-(1-λ2 )-1=0
-1=1-λ2
λ2=2
λ=±√2
A19 has (√2)19=29×√2 (or) (-√2)19=-512√2
=512√2
Question 12
     
A
B
{ε}
C
a*
D
{a ,ε}
Question 12 Explanation: 
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language is: {a* − a+} = {ϵ}
Question 13
A
∃x (real(x) ∨ rational(x))
B
∀x (real(x) → rational(x))
C
∃x (real(x) ∧ rational(x))
D
∃x (rational(x) → real(x))
Question 13 Explanation: 

∃x (real(x) ∧ rational(x))
(A) ∃x(real(x) ∨ rational(x))
means There exists some number, which are either real or rational.
(B) ∀x (real(x)→rational(x))
If a number is real then it is rational.
(D) ∃x (rational(x)→real(x))
There exists a number such that if it is rational then it is real.
Question 14
Given the basic ER and relational models, which of the following is INCORRECT?
A
An attribute of an entity can have more than one value
B
An attribute of an entity can be composite
C
In a row of a relational table, an attribute can have more than one value
D
In a row of a relational table, an attribute can have exactly one value or a NULL value
Question 14 Explanation: 
Option (A): In ER-model, multivalued attribute of an entity can have more than one value.
Option (B): In ER model, the attribute which can be further broken down into some other attributes is called composite attribute.
Option (C): In Relational model, the intersection of one row and column should contain only one value. So, option (C) is INCORRECT.
Option (D): In Relational model, the intersection of one row and column should contain either exactly one value or NULL.
Question 15
A
P and R
B
P and S
C
Q and R
D
Q and S
Question 15 Explanation: 
The SQL GROUP BY clause is used in collaboration with the SELECT statement to arrange identical data into groups. This GROUP BY clause follows the WHERE clause in a SELECT statement and precedes the ORDER BY clause. The attributes used in GROUP BY clause must present in SELECT statement.
The HAVING Clause enables you to specify conditions that filter which group results appear in the results. The WHERE clause places conditions on the selected columns, whereas the HAVING clause places conditions on groups created by the GROUP BY clause. So, we cannot use HAVING clause without GROUP BY clause.
Question 16
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
A
T(n) = 2T(n - 2) + 2
B
T(n) = 2T(n - 1) + n
C
T(n) = 2T(n/2) + 1
D
T(n) = 2T(n - 1) + 1
Question 16 Explanation: 
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3

= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
Question 17
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
A
3
B
4
C
5
D
6
Question 17 Explanation: 
If the graph is planar, then we have to consider Euler’s formula
v-e+f=2
Given 10 vertices & 15 edges
10-15+f=2
f=2+15-10
f=7
There will be an unbounded face always. So, number of faces = 6.
Question 18
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n.  Which of the following is ALWAYS TRUE?
A
A(n) = Ω (W(n))
B
A(n) = Θ (W(n))
C
A(n) = O (W(n))
D
A(n) = o (W(n))
Question 18 Explanation: 
The average case time can be lesser than or even equal to the worst case.
So, A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort).
A(n)=O(W(n))
Note: Option A is wrong because A(n) is not equal to Ω(w(n)) .
Question 19
The amount of ROM needed to implement a 4 bit multiplier is
A
64 bits
B
128 bits
C
1 Kbits
D
2 Kbits
Question 19 Explanation: 
To implement a 4-bit multiplier we need to store all the possible combinations of 24 x 24 inputs and their corresponding 8 output bits. The total ROM size needed = 28 x 8 bits = 211 bits = 2 Kbits.
Hence option D is the answer.
Question 20
Register renaming is done in pipelined processors
A
as an alternative to register allocation at compile time
B
for efficient access to function parameters and local variables
C
to handle certain kinds of hazards
D
as part of address translation
Question 20 Explanation: 
Register renaming is used to eliminate hazards that arise due to WAR (Write After Read) and WAW(Write After Write) dependencies. Hence option C is the answer.
Question 21
Consider a random variable X that takes values +1 and −1 with probability 0.5 each. The values of the cumulative distribution function F(x) at x = −1 and +1 are
A
0 and 0.5
B
0 and 1
C
0.5 and 1
D
0.25 and 0.75
Question 21 Explanation: 
Cumulative probability is sum of probabilities of all other points till the given value.
The sum of probabilities at x=1, x=-1 itself is 0.5+0.5 =1. It is evident that, there is no probability for any other values.
The F(x=-1) is 0.5 as per given probabilities and
F(x=1) = sum of F(x=-1) +F(x=0)=...f(X=1) = 0.5 +0.5 =1
Question 22
Which of the following transport layer protocols is used to support electronic mail?
A
SMTP
B
IP
C
TCP
D
UDP
Question 22 Explanation: 
TCP is used in transport layer to carry out mail which is initiated by application layer protocol SMTP.
Question 23
In the IPv4 addressing format, the number of networks allowed under Class C addresses is
A
214
B
27
C
221
D
224
Question 23 Explanation: 
For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence total number of networks possible is 221.
Question 24
A
1, 2, 3, 4
B
1, 2
C
2, 3, 4
D
3, 4
Question 24 Explanation: 
The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.
Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.
Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.
Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.
Question 25
   
A
1, 2 and 3
B
2, 3 and 4
C
1, 2 and 4
D
1, 3 and 4
Question 25 Explanation: 
L* will contain all those strings which can be obtained by any combination (and repetition) of the strings in language i,e, from L= {ab, aa, baa}
String 1: abaabaaabaa : ab aa baa ab aa
String 2: aaaabaaaa : aa aa baa aa
String 3: baaaaabaaaab: baa aa ab aa aa b, because of the last “b” the string cannot belong to L*.
String 4: baaaaabaa : baa aa ab aa
Question 26
A
B
C
D
Question 26 Explanation: 
Original graph:

(A) 3 cycle graph not in original one.

(B) Correct 5 cycles & max degree is 4.
(C) Original graph doesn’t have a degree of 3.

(D) 4 cycles not in original one.
Question 27
A
a serializable schedule
B
a schedule that is not conflict serializable
C
a conflict serializable schedule
D
a schedule for which a precedence graph cannot be drawn
Question 27 Explanation: 

The above schedule is not conflict serializable.
Question 28
The bisection method is applied to compute a zero of the function f(x) = x4 - x3 - x2 - 4 in the interval [1,9]. The method converges to a solution after ________ iterations.
A
1
B
3
C
5
D
7
Question 28 Explanation: 
Note: Numerical methods are not present in the GATE CS syllabus anymore.
Question 29
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
A
T' = T with total weight t' = t2
B
T' = T with total weight t'2
C
T' ≠ T but total weight t' = t2
D
None of the above
Question 29 Explanation: 
Let graph G be

Then MST for G is,

Now let's square the weights,

Then MST for G' is,

So, from above we can see that T is not necessarily equal to T' and moreover (t1) < (t2).
So option (D) is correct answer.
Question 30
A
B
C
D
Question 30 Explanation: 
Question 31
A
FCFS: P1, P2, P3 RR2: P1, P2, P3
B
FCFS: P1, P3, P2 RR2: P1, P3, P2
C
FCFS: P1, P2, P3 RR2: P1, P3, P2
D
FCFS: P1, P3, P2 RR2: P1, P2, P3
Question 31 Explanation: 
FCFS is - P1, P2, P3
FCFS is clear.
RR Queue: In RR queue time slot is of 2 units.
Processes are assigned in following order
P1, P2, P1, P3, P2, P1, P3, P2, P2
This question used ready queue concept. At t=2, P2 starts and P1 is sent to the ready queue and at t=3 P3 arrives so then the job P3 is queued in ready queue after P1. So at t=4, again P1 is executed then P3 is executed for first time at t=6.
RR2: P1, P3, P2 So option C.
Question 32
A
fails as L can overflow
B
fails as L can take on a non-zero value when the lock is actually available
C
works correctly but may starve some processes
D
works correctly without starvation
Question 32 Explanation: 
Check the loop first:
while (Fetch_And_Add (L,1))
L = 1; // A waiting process can be here just after
// the lock is released, and can make L = 1.
Assume P1 executes until while condition and preempts before executing L =1. Now P2 executes all statements, hence L = 0. Then P1 without checking L it makes L = 1 by executing the statement where it was preempted.
It takes a non-zero value (L=1) when the lock is actually available (L = 0). So option B.
Question 33
Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a second time. What is the probability that the sum total of values that turn up is at least 6?
A
10/21
B
5/12
C
2/3
D
1/6
Question 33 Explanation: 
The value on the die for first time rolling= {1, 2, 3}
The value on second time can be {1, 2, 3, 4, 5, 6}
So the Sum can be

We have Sample space = 36
The no. of events where (Sum = atleast 6) = {6, 7, 6, 7, 8, 6, 7, 8, 9}
So the probability atleast ‘6’ while getting {1, 2, 3} in first time = 9/36 → ①
If we get ‘6’ in the first time itself, then we do not go for rolling die again.
So, its probability = 1/6
Total probability = 1/6 + 9/36 = 1/6 + 1/4 = 10/24 = 5/12
Question 34
An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses to Organization A, and a quarter to Organization B, while retaining the remaining with itself. Which of the following is a valid allocation of addresses to A and B?
A
245.248.136.0/21 and 245.248.128.0/22
B
245.248.128.0/21 and 245.248.128.0/22
C
245.248.132.0/22 and 245.248.132.0/21
D
245.248.136.0/24 and 245.248.132.0/21
Question 34 Explanation: 
Question 35
Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
A
full: (REAR+1)mod n == FRONT
empty: REAR == FRONT
B
full: (REAR+1)mod n == FRONT
empty: (FRONT+1) mod n == REAR
C
full: REAR == FRONT
empty: (REAR+1) mod n == FRONT
D
full: (FRONT+1)mod n == REAR
empty: REAR == FRONT
Question 35 Explanation: 

To circulate within the queue we have to write mod n for (Rear + 1).
We insert elements using Rear & delete through Front.
Question 36
A
B
C
D
Question 36 Explanation: 

Main → A1 → A2 → A21 → A1
Since, Activation records are created at procedure exit time.
A1 & A2 are defined under Main ( ). So A1 & A2 access links are pointed to main.
A21 is defined under A2, hence its access link will point to A2.
Question 37
How many onto (or surjective) functions are there from an n-element (n ≥ 2) set to a 2-element set?
A
2n
B
2n-1
C
2n-2
D
2(2n– 2)
Question 37 Explanation: 
The number of onto functions from set of m elements to set of n elements, if m>n is
nm – (2n – 2)
i.e., 2n – (22 – 2) = 2n – 2
If there are 'm' elements in set A, 'n' elements in set B then
The number of functions are : nm
The number of injective or one-one functions are nPm
The number of surjective functions are:
If m If m>n, then n! * mCn
Given that m=n, n=2
2! * nC2
Question 38
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to
A
15
B
30
C
45
D
360
Question 38 Explanation: 
Complete graph means there exists an edge between every pair of vertices.
It is asked to find the distinct cycle of length 4. As it is complete graph, if we chose any two vertices, there will be an edge.
So, to get a cycle of length 4 (means selecting the 4 edges which can form a cycle) we can select any four vertices.
The number of such selection of 4 vertices from 6 vertices is 6C4 => 15.
From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like
a-b-c-d
a-b-d-c
a-c-b-d
a-c-d-b
a-d-b-c
a-d-c-b (Total 6, which is equal to number of cyclic permutations (n-1)! )
As they are labelled you can observe, a-b-c-d and a-d-c-b are same, in different directions.
So, we get only three combinations from the above 6.
So, total number of distinct cycles of length 4 will be 15*3 = 45.
If it is asked about just number of cycles then 15*6 = 90
Question 39
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
A
O (n log n)
B
O (n2 log n)
C
O (n2 + log n)
D
O (n2)
Question 39 Explanation: 
1.The comparison is strictly follow the Dictionary based order.
2.The length of the string is n, the time taken is to be O(n) for each comparison.
3. For level -1(bottom-up order): Every element has to be compared with other element the number of comparisons is O(n/2).
4. For level -1(bottom-up order): Total time taken by one level is O(n2).
5. For copying level to level the time taken by O(n2).
So, For level -1= O(n2)+ O(n2)
6. Second level O(n2)+ O(n2).
;
;
;
Final n level (logn)*O(n2) = O(n2 logn)
Question 40
A
SDT
B
SBDT
C
SACDT
D
SACET
Question 40 Explanation: 
They did not ask about shortest paths from S to T but they had asked the shortest path obtained by applying Dijkstra algorithm. If we apply Dijkstra algorithm we got path from S to T 10 only after relaxing edges through E and E will get 6 only after relaxing edges through C and C will get 5 only after relaxing edges through A. So, the shortest path from S to T if we follow Dijkstra algorithm is S,A,C,E,T.
The shortest path between S to T is SBDT also but if you follow Dijkstra shortest path algorithm then the shortest path you will getting from S to T is only SACET. We suggest you to apply Dijkstra algorithm on S and find the shortest path between S to all vertices. Then the path you will get from S to T is SACET.


Here we will draw edge from E to T not D to S because we updated the T value to 10 after selecting vertex E.
So, path is S, A, C, E, T.
Here D will get 7 only through S. So, SBDT is not possible and SDT is not possible because T will get 10 only after selecting E. So, path is SACET.
Question 41
A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes. The maximum possible file size in this file system is
A
3 KBytes
B
35 KBytes
C
280 KBytes
D
dependent on the size of the disk
Question 41 Explanation: 
It’s given disk block is of size 128B.
So, one direct block addressing will point to 8 disk blocks = 8*128 B = 1 KB
Singly Indirect block addressing will point to 1 disk block which has 128/8 disc block addresses = (128/8)*128 B = 2 KB
Doubly indirect block addressing will point to 1 disk block which has 128/8 addresses to disk blocks which in turn has 128/8 addresses to disk blocks = 16*16*128 B = 32 KB
Maximum possible file size = 1 KB + 2 KB + 32 KB = 35 KB
Question 42
A
OPTIMAL < LRU < FIFO
B
OPTIMAL < FIFO < LRU
C
OPTIMAL = LRU
D
OPTIMAL = FIFO
Question 42 Explanation: 
FIFO:

No. of page faults with FIFO = 6
LRU:

No. of page faults with LRU = 9
Optimal:

No. of page faults with optimal = 5
∴ Optimal < FIFO < LRU
Question 43
Suppose R1(A, B) and R2(C, D) are two relation schemas. Let r1 and r2 be the corresponding relation instances. B is a foreign key that refers to C in R2. If data in r1 and r2 satisfy referential integrity constraints, which of the following is ALWAYS TRUE?
A
B (r1) - ∏C (r2) = ∅
B
C (r2) - ∏B (r1) = ∅
C
B (r1) = ∏C (r2)
D
B (r1) - ∏C (r2) ≠ ∅
Question 43 Explanation: 
Referential integrity means, all the values in foreign key should be present in primary key.
So we can say that r2(C) is the superset of r1(B).
So (subset - superset) is always empty.
Question 44
Consider a source computer (S) transmitting a file of size 106 bits to a destination computer (D) over a network of two routers (R1 and R2) and three links (L1, L2 and L3). L1 connects S to R1; L2 connects R1 to R2; and L3 connects R2 to D. Let each link be of length 100 km. Assume signals travel over each link at a speed of 108 meters per second. Assume that the link bandwidth on each link is 1Mbps. Let the file be broken down into 1000 packets each of size 1000 bits. Find the total sum of transmission and propagation delays in transmitting the file from S to D?
A
1005 ms
B
1010 ms
C
3000 ms
D
3003 ms
Question 44 Explanation: 

Propagation delay = (Distance) / (Velocity) = 3*105/108 = 3ms
Total transmission delay for 1 packet = 3 * L / B = 3*(1000/106) = 3ms. Because at source and 2 routers, we need to transmit the bits.
The first packet will reach destination = Tt + Tp = 6ms.
While the first packet was reaching to D, other packets must have been processing in parallel. So D will receive remaining packets 1 packet per 1 ms from R2. So remaining 999 packets will take 999 ms.
And total time will be 999 + 6 = 1005 ms
Question 45
Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a timeout occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.
A
8 MSS
B
14 MSS
C
7 MSS
D
12 MSS
Question 45 Explanation: 
Given initial threshold = 8
Time = 1 during 1st trans. , window size = 2 (Slow start),
Time = 2 congestion window size = 4 (double the no. of ack.)
Time = 3 congestion window = 8
Time = 4 congestion window size = 9, after threshold, increase by one additive increase.
Time = 5 transmit 10 MSS, but time out occur congestion window size = 10
Hence threshold = (congestion window size)/2 = 10/2 = 5
Time = 6 transmit 2(since in the question, they are saying ss is starting from 2)
Time = 7 transmit 4
Time = 8 transmit 5
Time =9 transmit 6
Time =10 transmit 7
Question 46
   
A
B
C
D
Question 46 Explanation: 
All states are final states except “q” which is trap state. The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.
From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.
Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.
Question 47
A
B1: (1+height(n→right))
B2: (1+max(h1,h2))
B
B1: (height(n→right))
B2: (1+max(h1,h2))
C
B1: height(n→right)
B2: max(h1,h2)
D
B1: (1+ height(n→right))
B2: max(h1,h2)
Question 47 Explanation: 

Now, we analyze the code,
The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.
In such case, height of n will be the height of the right subtree +1.
The box B2 gets executed when both left & right subtrees of n are not NULL.
In such case, height of n will be max of heights of left & right subtrees of n+1.
Question 48
A
B
C
D
Question 48 Explanation: 

Hence
4 2
6 2
2 0
Question 49
A
B
C
D
Question 49 Explanation: 
Line 1 replaced by auto int a=1;
Line 2 replaced by register int a=2;
In main there will be no change if it is static or auto because of a+=1 the auto variable a is updated to 2 from 1.
In prtfun ( ), register makes a difference.
For first print statement a is updated to 4 & prints 4, 2.
But now it is not a static variable to retain the value of a to 4. So it becomes 2, when second function call takes place & prints 4, 2 again. There is no change in b, it acts like a local variable.
Hence,
4 2
4 2
2 0.
Question 50
     
A
7
B
4
C
5
D
9
Question 50 Explanation: 


Performs the cross product and selects the tuples whose A∙Id is either greater than 40 or C∙Id is less than 15. It yields:
Question 51
   
A
4
B
3
C
0
D
1
Question 51 Explanation: 

First query (2) will be executed and 0 (no) rows will be selected because in relation B there is no Name ‘Arun’.
The outer query (1) results the follow and that will be the result of entire query now. (Because inner query returns 0 rows).
Question 52
 
A
FIRST(A) = {a,b,ε} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = {a,b,$}
B
FIRST(A) = {a,b,$}
FIRST(B) = {a,b,ε}
FOLLOW(A) = {a,b}
FOLLOW(B) = {$}
C
FIRST(A) = {a,b,ε} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = ∅
D
FIRST(A) = {a,b} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = {a,b}
Question 52 Explanation: 
FIRST (P): is the set of terminals that begin the strings derivable from non terminal P. If P derives epsilon then we include epsilon in FIRST(P).
FOLLOW(P): is the set of terminals that can appear immediately to the right of P in some sentential form.
FIRST(A) = FIRST (S)
FIRST (S) = FIRST (aAbB) and FIRST (bAaB) and FIRST (ϵ)
FIRST(S) = {a, b, ϵ}
FIRST (B) = FIRST (S) = {a, b, ϵ}= FIRST (A)
FOLLOW(A) = {b} // because of production S→a A b B
FOLLOW(A) = {a} // because of production S→ b A a B
So FOLLOW (A) = {a, b}
FOLLOW (B) = FOLLOW (S) // because of production S→ a A b B
FOLLOW (S) = FOLLOW (A) // because of production S → A
So FOLLOW (S) = {$, a, b}= FOLLOW(B)
Question 53
A
E1: S → aAbB,A → S
E2: S → bAaB,B→S
E3: B → S
B
E1: S → aAbB,S→ ε
E2: S → bAaB,S → ε
E3: S → ε
C
E1: S → aAbB,S → ε
E2: S → bAaB,S→ε
E3: B → S
D
E1: A → S,S →ε
E2: B → S,S → ε
E3: B →S
Question 53 Explanation: 
The entries in E1, E2 and E3 is related to S and B, so we have to take only those production which have S and B in LHS.
S→ aAbB | bAaB | ε
The production S→ aAbB will go under column FIRST (aAbB) = a, so S→ aAbB will be in E1.
S→ bAaB will go under column FIRST(bAaB) = b, so S→ bAaB will be in E2.
S→ ε will go under FOLLOW (S) = FOLLOW(B) = {a, b, $ } , So S→ ε will go in E1, E2 and under column of $.
So E1 will have: S→ aAbB and S→ ε.
E2 will have S→ bAaB and S→ ε.
Now, B→ S will go under FIRST (S) = {a, b, ε}
Since FIRST(S) = ε so B→ S will go under FOLLOW (B) = {a, b, $}
So E3 will contain B→ S.
Question 54
A
11
B
14
C
16
D
27
Question 54 Explanation: 
It is given that cache size = 256 KB
Cache block size = 32 Bytes
So, number of blocks in the cache = 256K / 32 = 8 K
It is a 4-way set associative cache. Each set has 4 blocks.
So, number of sets in cache = 8 K / 4 = 2 K = 211.
So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.
Since cache block size is 32 bytes, block offset needs 5 bits.
Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16
So, we need 16 tag bits.
Question 55
A
160 Kbits
B
136 Kbits
C
40 Kbits
D
32 Kbits
Question 55 Explanation: 
It is given that cache size =256 KB
Cache block size = 32 Bytes
So, number of blocks in the cache = 256K / 32 = 8 K
It is a 4-way set associative cache. Each set has 4 blocks.
So, number of sets in cache = 8 K / 4 = 2 K = 211.
So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.
Since cache block size is 32 bytes, block offset needs 5 bits.
Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16
So, we need 16 tag bits.
It is given that in addition to address tag there are 2 valid bits, 1 modified bit and 1 replacement bit.
So size of each tag entry = 16 tag bits + 2 valid bits + 1 modified bit + 1 replacement bit = 20 bits
Size of cache tag directory=Size of tag entry×Number of tag entries
= 20×8 K
=160 Kbits
Question 56
The cost function for a product in a firm is given by 5q2, where q is the amount of production. The firm can sell the product at a market price of ₹50 per unit. The number of units to be produced by the firm such that the profit is maximized is
A
5
B
10
C
15
D
25
Question 56 Explanation: 
Total selling price =50q
Profit = 50q - 5q2
This is maximum at q = 5.
Question 57
A
attempts
B
setbacks
C
meetings
D
delegations
Question 57 Explanation: 
Setback = a reversal (or) setback in a progress (or) something that happens that delays
Despite several setbacks the mission succeeded in its attempt to resolve the conflict.
Question 58
A
Diminish
B
Divulge
C
Dedicate
D
Denote
Question 58 Explanation: 
Mitigate = make (something bad) less severe, serious (or) painful
Synonyms = Diminish, alleviate, reduce etc.
Question 59
Choose the grammatically INCORRECT sentence:
A
They gave us the money back less the service charges of Three Hundred rupees.
B
This country’s expenditure is not less than that of Bangladesh.
C
The committee initially asked for a funding of Fifty Lakh rupees, but later settled for a lesser sum.
D
This country’s expenditure on educational reforms is very less.
Question 59 Explanation: 
The country's expenditure on educational reforms is very less.
In the sentence "very less" is incorrect instead of this we use "much less" or else "very little".
Question 60
A
that
B
which
C
who
D
whom
Question 60 Explanation: 
Suresh's dog is the one that was hurt in the stampede.
that can refer groups of things.
who can refer to people.
which can introduces a non-essential clause.
whom can refer to object of a verb (or) preposition.
Question 61
 
A
Gender-discriminatory
B
Xenophobic
C
Not designed to make the post attractive
D
Not gender-discriminatory
Question 61 Explanation: 
Xenephobic which refers to having (or) showing a dislike of or prejudice against people from other countries.
Question 62
A political party orders an arch for the entrance to the ground in which the annual convention is being held. The profile of the arch follows the equation y = 2x - 0.1x2 where y is the height of the arch in meters. The maximum possible height of the arch is
A
8 meters
B
10 meters
C
12 meters
D
14 meters
Question 62 Explanation: 
Given,
y = 2x - 0.1x2
Differentiating both sides,
dy/dx = 2 - 0.2x
For maximum, dy/dx = 0
2 - 0.2x = 0
0.2x = 2
x = 10
Question 63
 
A
0.288
B
0.334
C
0.667
D
0.720
Question 63 Explanation: 
Probability that a shock absorber from X is reliable = 0.6×0.96 = 0.576
Probability that a shock absorber from Y is reliable = 0.4×0.72 = 0.288
Probability that a randomly selected reliable absorber is from Y is = 0.288/(0.576+0.288) = 0.334
Question 64
   
A
P, Q
B
Q, R
C
P, R
D
R, S
Question 64 Explanation: 
If a value of 'x' is addered (or) multiplied to everagery element in the list, the average also changes by same value.
⇒ P, R are correct
Question 65
Given the sequence of terms: AD  CG  FK  JP, the next term is
A
OV
B
OW
C
PV
D
PW
Question 65 Explanation: 

OV is the next term.
There are 65 questions to complete.