## GATE 2014(Set-01)

 Question 1

Aptitude       Verbal
Question 1 Explanation:
Cope: Deal effectively with something difficult.
(1) Adopt ⇒ Legally take and bring it up as one's own.
(2) Adapt ⇒ Make suitable for a new use or purpose.
(3) Adept ⇒ Very skilled (or) proficienct at something.
(4) Accept ⇒ Believe (or) come to recognize as valid (or) correct.
Option B is correct.
 Question 2
 A superb B medium C mediocre D exhilarating
Aptitude       Verbal
Question 2 Explanation:
Mediocre ⇒ Average quality (or) Not very good.
 Question 3
In a press meet on the recent scam, the minister said, "The buck stops here". What did the minister convey by the statement?
 A He wants all the money B He will return the money C He will assume final responsibility D He will resist all enquiries
Aptitude       Verbal
Question 3 Explanation:
"The buck stops here" means "The responsibility for something cannot (or) should not passed to someone else.
⇒ It represents that this is the final stage of responsibility.
 Question 4
If (z + 1/z)= 98, compute (z2+ 1/z2).
 A 96 B 97 C 98 D 99
Aptitude       Numerical
Question 4 Explanation:
z2+1/z2+2∙z∙ 1/z=98⇒z2 + 1/z2=96
 Question 5
The roots of ax2+ bx + c = 0 are real and positive. a, b and c are real. Then ax+ b|x|+ c = 0 has
 A no roots B 2 real roots C 3 real roots D 4 real roots
Aptitude       Numerical
Question 5 Explanation:
ax2+bx+c=0
For roots to be real & positive b2-4ac>0
This will have 2 real positive roots.
ax2+b|x|+c=0
Discriminant =b2-4ac>0
ax2+bx+c
(-b)2-4ac
⇒b2-4ac
Is also > 0. This will have real roots.
⇒ This will have 4 real roots.
 Question 6
 A The Palghat gap is caused by high rainfall and high temperatures in southern Tamil Nadu and Kerala B The regions in Tamil Nadu and Kerala that are near the Palghat Gap are low-lying C The low terrain of the Palghat Gap has a significant impact on weather patterns in neighbouring parts of Tamil Nadu and Kerala D Higher summer temperatures result in higher rainfall near the Palghat Gap area
Aptitude       Verbal
Question 6 Explanation:
The given passage says that "it results neighbouring regions of Tamilnadu getting more rainfall from the south west monsoon and neighbouring regions of Kerela having higher summer temperatures".
⇒ Option C is suitable option.
 Question 7
 A Strategies are now available for eliminating psychiatric illnesses B Certain psychiatric illnesses have a genetic basis C All human diseases can be traced back to genes and how they are expressed D In the future, genetics will become the only relevant field for identifying psychiatric illnesses
Aptitude       Verbal
Question 7 Explanation:
The first sentence can represents the two specific illness depression and schizophernia. ⇒ Option B is the only option that contain illness.
 Question 8
Round-trip tickets to a tourist destination are eligible for a discount of 10% on the total fare.  In addition, groups of 4 or more get a discount of 5% on the total fare.  If the one way single person fare is Rs 100, a group of 5 tourists purchasing round-trip tickets will be charged Rs _________.
 A 850 B 851 C 852 D 853
Aptitude       Numerical
Question 8 Explanation:
One way fare for a single person = Rs.100
Round trip, there is a discount of 10% of total fare.
Group of 4 or more, Discount of 5% of total fare.
∴ 5 tourists ⇒ Total fare = 5 × 200 = 1000
Total discount = 10% of 1000 + 5% of 1000
= 100 + 50
= ₹150
∴ Fare charged = 1000 - 150 = ₹850
 Question 9

 A 48 B 49 C 50 D 51
Aptitude       Numerical
Question 9 Explanation:
Total respondents = 300
[No. of respondents who do not own a scooter] = [No. of respondents who own's only a car + No. of respondents who do not own any vehicle]
= 40 + 34 + 70
= 144
Percentage = 144/300 × 100 = 48%
 Question 10
When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created with these lines? _____________
 A 6 B 7 C 8 D 9
Aptitude       Numerical
Question 10 Explanation:
Tetrahedron is a pyramid like structure with 4 corner points (vertical).
→ If you take a point inside a tetrahedron, then you have 5 points.
→ An internal plane is formed by joining any of the three points.
→ No. of planes = 5 C 3 = 10
But 4 of them will be faces of tetrahedron.
∴ New planes = 10 - 4 = 6
 Question 11
 A ∀x:glitters(x) ⇒¬gold(x) B ∀x:gold(x) ⇒glitters() C ∃x: gold(x)∧¬glitters(x) D ∃x:glitters(x)∧¬gold(x)
Aptitude       Numerical
Question 11 Explanation:
Method 1:
Not all that glitters is gold.
Option A:
∀x:glitters(x) ⇒¬gold(x)
which means that every item (x), which glitters is not gold.
Option B:
∀x:gold(x) ⇒glitters()
Every item (x) which is gold is a glitter.
(or)
Every golden item glitters.
Option C:
∃x: gold(x)∧¬glitters(x)
There are some gold items which does not glitters.
Option D:
∃x:glitters(x)∧¬gold(x)
There exists some glitters which are not gold.
(or)
Not all glitters are gold.

Method 2:

⇒ (∼∀x) (∼ (glitters(x) ⇒ gold(x))
⇒ ∃x (∼ (∼glitters(x) ∨ gold(x))
⇒ ∃x (glitters ∧ gold(x))
 Question 12
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .
 A 0.25 B 0.26 C 0.27 D 0.28
Aptitude       Numerical
Question 12 Explanation:
We break a unit length rod into two pieces at a uniformly chosen point.

If we break at point x, length of the one piece x and the other piece is 1 – x.
Length of the shorter stick is between 0 to 0.5. If it is more than 0.5 then it will be longer stick.
The random variable (l) follows a uniform distribution. The probability function of l is
1/(b-a)=1/(0.5-0)=2 (length is between 0 to 0.5)
Expected value of length
(where P(l) is the probability density function)
 Question 13
Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
 A G1=(V,E1) where E1={(u,v)|(u,v)∉E} B G2=(V,E2 )where E2={(u,v)│(u,v)∈E} C G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E} D G4=(V4,E) where V4 is the set of vertices in G which are not isolated
Engineering-Mathematics       Graph-Theory
Question 13 Explanation:
G(V, E) is a directed graph.
→ It strongly connected.
(A) G1=(V,E1) where E1={(u,v)|(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G2=(V,E2 )where E2={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
This can also be true.
eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G4=(V4,E) where V4 is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G4 contain only ‘1’ component, which is not same as G.
 Question 14
 A 1 B 2 C 3 D 4
Aptitude       Numerical
Question 14 Explanation:
Given:
3x + 2y = 1
4x + 7z = 1
x + y + z = 3
x – 2y + 7z = 0
This is a non-homogeneous equation system.
The Augmented matrix for above set of equations is

For matrix (A):
R4→ R4+R1

R4→ R4-R2

Rank = 3
For matrix (AB):

R4→(R4+R1 )-R2

Rank = 3
Rank of (A) = Rank (AB), so Unique solution
rank = 3 = no. of variables
Working Rule for Non-homogeneous equation:
(1) rank (A) < rank (AB), Inconsistent solution
(2) is rank (A) = rank (AB) = r then
if r = n, Unique solution
r < n, Infinite solution
 Question 15
The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix is _____________________.
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Linear-Algebra
Question 15 Explanation:
For real symmetric matrix, the eigen values are orthogonal to each other. So their dot product will be zero.
The finite dimensional spectral theorem says that any symmetric matrix whose entries are real can be diagonalized by an orthogonal matrix.
 Question 16

 A I only B II only C Both I and II D Neither I nor II
Engineering-Mathematics       Calculus
Question 16 Explanation:
Rolle’s theorem:
Rolle’s theorem states that for any continuous, differentiable function that has two equal values at two distinct points, the function must have a point on the function where the first derivative is zero. The technical way to state this is: if f is continuous and differentiable on a closed interval [a,b] and if f(a) = f(b), then f has a minimum of one value c in the open interval [a, b] so that f'(c) = 0.
We can observe that, sin, cos are continuous, but, Tan is not continuous at π/2. As the mentioned interval does not contain π/2, we can conclude that it is continuous.
As per Rolls theorem both statement 1 and statement 2 are true.
 Question 17

 A B C D
Digital-Logic-Design       Boolean-Algebra
Question 17 Explanation:
PQ + P’QR + P’QR’S
= Q(P+P’R) + P’QR’S
= Q(P+R) + P’QR’S
=QP + QR + P’QR’S
= QP + Q(R + P’R’S)
= QP + Q( R + P’S)
= QP + QR + QP’S
= Q(P+P’S) + QR
= Q(P+S)+ QR
= QP + QS + QR
 Question 18

 A 5 B 6 C 7 D 8
Digital-Logic-Design       Number-Systems
Question 18 Explanation:
Let base of the number system is r.
(3r2 + r + 2) / 2r= (r+3+1/r)
(3r2 + r + 2) / 2r= (r2+3r+1) / r
(3r2 + r + 2) = (2r2+6r+2)
r2 -5r = 0
Therefor r = 5
 Question 19
A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long.  It needs to support 45 instructions, which have an immediate operand in addition to two register operands.  Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________.
 A 16383 B 16384 C 16385 D 16386
Computer-Organization       Machine-Instructions
Question 19 Explanation:
1 Word = 32 bits
Each instruction has 32 bits.
To support 45 instructions, opcode must contain 6-bits.
Register operand1 requires 6 bits, since the total registers are 64.
Register operand 2 also requires 6 bits

14-bits are left over for immediate Operand Using 14-bits, we can give maximum 16383, Since 214 = 16384 (from 0 to 16383)
 Question 20

 A Compilation fails. B Execution results in a run-time error. C On execution, the value printed is 5 more than the address of variable i. D On execution, the value printed is 5 more than the integer value entered.
Programming       Programming
Question 20 Explanation:
int i; // Initially i takes the Garbage value
int *pi = &i; // pi is a pointer which stores the address of i.
scanf (pi); // pi = &i (we rewrite the garbage value with our values) say x = 2
printf (i+5); // i+5 = x+5 = 2+5 = 7
Hence on execution, the value printed is 5 more than the integer value entered.
 Question 21
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
 A θ(n) B θ(n+m) C θ(n2 ) D θ(m2 )
Data-Structures       Graphs
Question 21 Explanation:
DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V2).
 Question 22
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(nalogbn). Then the value of a+10b is ________.
 A 1 B 2 C 3 D 4
Data-Structures       Time-Complexity
Question 22 Explanation:
Binary tree traversal takes O(n) time for reaching 4th level from the leaf node. Every node has to check their subtree having exactly 4 nodes. Checking time can be done in maximum constant time for each node. Nodes in the level is always less than n and it's complexity is O(n). Finally a value becomes 1 and b value becomes 0.
Substitute into a and b values in equation.
⇒ a+10b
⇒ a*1 + 10*0
⇒ 1+0
⇒ 1
 Question 23

 A The graph does not have any topological ordering. B Both PQRS and SRQP are topological. C Both PSRQ and SPRQ are topological orderings. D PSRQ is the only topological ordering.
Data-Structures       Graphs
Question 23 Explanation:

There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.
 Question 24
Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
 A t1=5 B t12 C t1>t2 D t1=t2
Data-Structures       Quick-Sort
Question 24 Explanation:
[1, 2, 3, 4, 5] [4, 1, 5, 3, 2]
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2nd array through not in sorted manner.
Hence t1> t2.
 Question 25
Which one of the following is TRUE?
 A The language L={an bn│n≥0} is regular. B The language L={an│n is prime} is regular. C The language L={w│w has 3k+1b's for some k∈N with Σ={a,b} } is regular. D The language L={ww│w∈Σ* with Σ={0,1} } is regular.
Theory-of-Computation       Regular Languages
Question 25 Explanation:
The Language L= {an bn | n>=0} is CFL but not regular, as it requires comparison between a’s and b’s.
L = {an | n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)
L = {ww | w ∈ ∑*} is CSL.
But L = { w | w has 3k+1 b’s for some k ∈ natural number} is regular.
Lets take values of k={1,2,3,….}
So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.
The DFA will be
 Question 26
 A {q0,q1,q2 } B {q0,q1 } C {q0,q1,q2,q3 } D {q3 }
Theory-of-Computation       Finite-Automata
Question 26 Explanation:
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2
Hence δ (q0, 0011) = {q0, q1, q2}
 Question 27
Which one of the following is FALSE?
 A A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. B Available expression analysis can be used for common subexpression elimination. C Live variable analysis can be used for dead code elimination. D x=4*5⇒x=20 is an example of common subexpression elimination.
Compiler-Design       Code-Optimization
Question 27 Explanation:
x=4* 5 ⇒ x=20 is an example of common subexpression elimination is a false statement.
Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.
For ex: Consider the following code:
m=y+z * p
n= y+z *k
The common subexpression is “y+z” we can be calculate it one time and replace in both expression
temp = y+z
m = temp*p
n = temp*k
 Question 28
 A 1-a, 2-b, 3-c, 4-d B 1-d, 2-a, 3-b, 4-c C 1-d, 2-b, 3-a, 4-c D 1-c, 2-a, 3-b, 4-d
Software-Engineering       SE
Question 28 Explanation:
Note: Out of syllabus.
 Question 29
Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.
 A 3 B 4 C 5 D 6
Operating-Systems       Disk-Scheduling
Question 29 Explanation:

90 is serviced after servicing three requests, i.e.,
100 → 105 → 110 → 90
 Question 30
Which one of the following is FALSE?
 A User level threads are not scheduled by the kernel. B When a user level thread is blocked, all other threads of its process are blocked. C Context switching between user level threads is faster than context switching between kernel level threads. D Kernel level threads cannot share the code segment.
Question 30 Explanation:
Kernel level threads shares the code segment.
 Question 31
Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies  {{E,F} → {G}, {F} → {I,J}, {E,H} → {K,L}, {K} → {M}, {L} → {N}} on R. What is the key for R?
 A {E,F} B {E,F,H} C {E,F,H,K,L} D {E}
Database-Management-System       Functional-Dependency
Question 31 Explanation:
A) (EF)+ = EFGIJ. So, EF is not a key.
B) (EFH)+ = EFHGIJKLMN, EFH is deriving all the attributes of R. So, EFH is a key.
C) If EFH is a key, then EFHKL will become the super key.
D) (E)+ = E
 Question 32
 A S1 is TRUE and S2 is FALSE. B Both S1 and S2 are TRUE. C S1 is FALSE and S2 is TRUE. D Both S1 and S2 are FALSE.
Database-Management-System       SQL
Question 32 Explanation:
S1: False
Using a check constraint, we can have the same effect as foreign key while adding elements to the child table. But while deleting elements from the parent table the referential integrity constraint is no longer valid. So, a check constraint cannot replace a foreign key.
S2: False:
Foreign key in one table should be defined as a primary key in other table. In above table definition, table S has a foreign key that refers to field ‘a’ of R. The field ‘a’ in table S is part of the primary key and part of the key cannot be declared as a foreign key.
 Question 33
 A S1, S2, and S3 are all true. B S1, S2, and S3 are all false. C S1 and S2 are true, but S3 is false. D S1 and S3 are true, but S2 is false.
Computer-Networks       Routing
Question 33 Explanation:
S1: The computational overhead in link state protocols is higher than in distance vector protocols. Because LSR is based upon global knowledge whereas DVR is based upon Local info.(True)
S2: A distance vector protocol with split horizon avoid persistent routing loops is true, but not a link state protocol is false because link state protocols do not have count to infinity problem.
S3: As Distance vector protocol has count to infinity problem and converges slower. (True)
 Question 34
 A P and R only B Q and R only C Q and S only D R and S only
Computer-Networks       Security
Question 34 Explanation:
RSA and DES are for Encryption where MD5 and SHA – 1 are used to generate Message Digest.
 Question 35
 A 4,2,1,3 B 1,2,3,4 C 4,1,2,3 D 2,4,1,3
Computer-Networks       TCP
Question 35 Explanation:
First of all the browser must now know what IP to connect to. For this purpose browser takes help of Domain name system (DNS) servers which are used for resolving hostnames to IP addresses. As browser is an HTTP client and as HTTP is based on the TCP/IP protocols, first it establishes a TCP connection with the web server and requests a web page using HTTP, and then the web server sends the requested web page using HTTP. Hence the order is 4,2,1,3.
 Question 36
Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is 2×108 m/s and the token transmission time is ignored. If each station is allowed to hold the token for 2 µsec, the minimum time for which the monitoring station should wait (in µsec) before assuming that the token is lost is _______.
 A 28μs to 30 μs B 29μs to 31 μs C 30μs to 32 μs D 31μs to 33 μs
Computer-Networks       Token-Ring
Question 36 Explanation:
Given length (d) = 2 Km
No. of Stations (m) = 10
Propagation speed (v) = 2⨯108 m/s
THT = 2μs
So, Max, TRT = Tp in the ring + No. of Active Stations * THT
= 10 ⨯ 10-6 + 10 ⨯ 2 ⨯ 10-6
= 30 μs
 Question 37
Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2 KB. The time taken (in msec) by the TCP connection to get back to 32 KB congestion window is _________.
 A 1100 to 1300 B 1101 to 1301 C 1102 to 1302 D 1103 to 1303
Computer-Networks       TCP
Question 37 Explanation:
Given that at the time of Time Out, Congestion Window Size is 32KB and RTT = 100ms
When Time Out occurs, for the next round of Slow Start, Threshold = (size of Cwnd) / 2
It means Threshold = 16KB
Slow Start
2KB
1RTT
4KB
2RTT
8KB
3RTT
16KB ----------- Threshold reaches. So Additive Increase Starts
4RTT
18KB
5RTT
20KB
6RTT
22KB
7RTT
24KB
8RTT
26KB
9RTT
28KB
10RTT
30KB
11RTT
32KB
So, Total no. of RTTs = 11 → 11 * 100 = 1100
 Question 38
Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.
 A 5 B 6 C 7 D 8
Computer-Networks       Sliding-Window-Protocol
Question 38 Explanation:
Given L=1 KB
B=1.5 Mbps
Tp=50 ms
η=60%
Efficiency formula for SR protocol is
η=W/(1+2a)⇒60/100=W/(1+2a) (∵a=Tp/Tx)
Tx=L/B=8×103/1.5×106=5.3ms
a=Tp/Tx=50/5.3=500/53=9.43
⇒ 60/100=W/19.86⇒W=11.9≈12
⇒ W=2n-1=12⇒2n=24⇒2n=24≈25⇒n=5
 Question 39
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?
 A r1 (x); r2 (x); w1 (x); r3 (x); w2 (x) B r2 (x);r1 (x);w2 (x);r3 (x);w1 (x) C r3 (x);r2 (x);r1 (x);w2 (x);w1 (x) D r2 (x);w2 (x);r3 (x);r1 (x);w1 (x)
Database-Management-System       Transactions
Question 39 Explanation:
Option: A

- Polygraph contains cycle. So, not a conflict serializable.
Option: B

-Cyclic
Option: C

- Cyclic
Option: D

- Acyclic, so conflict serializable.
 Question 40
 A S1 is TRUE and S2 is FALSE. B Both S1 and S2 are TRUE. C S1 is FALSE and S2 is TRUE. D Both S1 and S2 are FALSE.
Database-Management-System       Normalization
Question 40 Explanation:
S1: True
If we can prove the relation is in BCNF then by default it would be in 1NF, 2NF, 3NF also.
Let R(AB) be a two attribute relation, then
If {A→B} exists then BCNF since {A}+ = AB = R
If {B→A} exists then BCNF since {B}+ = AB = R
If {A→B, B→A} exists then BCNF since A and B both are Super Key now.
If {No non-trivial Functional Dependency} then default BCNF.
Hence it’s proved that a Relation with two single-valued attributes is in BCNF hence it’s also in 1NF, 2NF, 3NF.
S2: False
The canonical cover for the given FD set is {AB→C, D→E, AB→E, E→C}. As we can see AB→E is not covered in minimal cover since {AB}+ = ABC in the given cover {AB→C, D→E, E→C}
 Question 41

 A Only REQ1 can be permitted. B Only REQ2 can be permitted. C Both REQ1 and REQ2 can be permitted. D Neither REQ1 nor REQ2 can be permitted.
Operating-Systems       Bankers-Algorithm
Question 41 Explanation:
Lets take 1st case,
After allowing Req 1,

Available: X=3, Y=2, Z=0
With this we can satisfy P1's requirement. So available becomes: X=6, Y=4, Z=0.
Since Z is not available, neither P0's nor P2's requirement can be satisfied. So, it is an unsafe state.
Lets take 2nd case,
After allowing Req 2,

Available: X=1, Y=2, Z=2
With this we can satisfy any one of P1's or P2's requirement. Lets first satisfy P1's requirement. So Available now becomes:
X=6, Y=4, Z=2
Now with the availability we can satisfy P2's requirement. So Available now becomes,
X=8, Y=5, Z=3
With this availability P0 can also be satisfied. So, hence it is in safe state.
So from above two cases Req 1 cannot be permitted but Req 2 can be permitted.
 Question 42
 A 7.2 B 7.3 C 7.4 D 7.5
Operating-Systems       Process-Scheduling
Question 42 Explanation:
Using SRTF:

TAT(A) = 8-0 = 8, TAT(B)= 5-3=2, TAT(C)= 12-5=7, TAT(D)= 21-7= 14, TAT(E)=15-10=5
Average turnaround time = 8+2+7+14+5/ 5 = 7.2ms
 Question 43
Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.
 A 7 B 8 C 9 D 10
Operating-Systems       Page-Replacement-Algorithm
Question 43 Explanation:

Total 7 faults are there.
 Question 44
 A a shift-reduce conflict and a reduce-reduce conflict. B a shift-reduce conflict but not a reduce-reduce conflict. C a reduce-reduce conflict but not a shift-reduce conflict. D neither a shift-reduce nor a reduce-reduce conflict.
Compiler-Design       Parsers
Question 44 Explanation:
The input symbol is “<” which is not in canonical set of item, so it is neither a shift-reduce nor a reduce-reduce conflict with reference to “<” symbol.
But if it would have asked about “>” then it will be a SR conflict.
 Question 45
 A Neither L nor is recursively enumerable (r.e.). B One of L and is r.e. but not recursive; the other is not r.e. C Both L and are r.e. but not recursive. D Both L and are recursive.
Compiler-Design       Closure-Property
Question 45 Explanation:
If both L and L’ are recursively enumerable, then L must be recursive. Hence, both L and L´ are recursively enumerable, but not recursive is not a viable possibility.
 Question 46
 A I and II only B I and III only C II and III only D I, II, and III
Compiler-Design       Regular-Expressions
Question 46 Explanation:
The DFA accepts the language “all strings ending with 1”.
So the regular expression corresponding to DFA is (0+1)*1.
Now, by using state elimination method,
So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.
But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.
 Question 47
There are 5 bags labeled 1 to 5.  All the coins in a given bag have the same weight.  Some bags have coins of weight 10 gm, others have coins of weight 11 gm.  I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5.  Their total weight comes out to 323 gm.  Then the product of the labels of the bags having 11 gm coins is _______.
 A 12 B 13 C 14 D 15
Algorithms       General
Question 47 Explanation:
Bags: 1 2 3 4 5
No. of coins picked: 1 2 4 8 16
There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.
Let there be x number of 10gm coins and y number of 11gm coins.
So, 10x + 11y = 323 ------ (1)
And we also know that total number of coins picked is
1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,
= 31 ------ (2)
Solving equation (1) and (2), we get
y = 13
Means total there are 13 coins of 11gm.
Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.
So product of labelled bag number = 1×3×4 = 12
 Question 48
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
 A B C D
Algorithms       P-NP
Question 48 Explanation:
The most important open question in complexity theory is whether the P = NP, which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems (since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.
 Question 49
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.
 A 148 B 149 C 150 D 151
Algorithms       General
Question 49 Explanation:
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is 3n/2 – 2 = 148. (∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)
 Question 50
Consider a hash table with 9 slots.  The hash function is h(k) = k mod 9.  The collisions are resolved by chaining.  The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10.  The maximum, minimum, and average chain lengths in the hash table, respectively, are
 A 3, 0, and 1 B 3, 3, and 3 C 4, 0, and 1 D 3, 0, and 2
Data-Structures       Hashing
Question 50 Explanation:
Hash table has 9 slots.
h(k) = k mod 9
Collisions are resolved using chaining.
Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5
28%9 – 1
19%9 – 1
15%9 – 6
20%9 – 2
33%9 – 6
12%9 – 3
17%9 – 8
10%9 – 1
Maximum chain length is 3
Minimum chain length is 0
Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1
 Question 51
 A maximum possible sum of elements in any sub-array of array E. B maximum element in any sub-array of array E. C sum of the maximum elements in all possible sub-arrays of array E. D the sum of all the elements in the array E.
Data-Structures       General
Question 51 Explanation:
Y=0
for (i=0; i Y=Y+E[i] // E is an array, this statement calculates the sum of elements of the array E and stores it in Y.
for (i=0; i for(j=i; j {
Z=0;
for(k=i; k<=j; k++)
Z=Z+E[k];
// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].
Store the current sum in Z.
If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.
 Question 52
 A Half of the product of the 3 consecutive integers. B One-third of the product of the 3 consecutive integers. C One-sixth of the product of the 3 consecutive integers. D None of the above.
Data-Structures       Time-Complexity
Question 52 Explanation:
D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3;

Also you can try for smaller ‘n’.
 Question 53
Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______________________.
 A 4 B 5 C 6 D 7
Data-Structures       Pipelining
Question 53 Explanation:
For 6 stages, non- pipelining takes 6 cycles.
There were 2 stall cycles for pipelining for 25% of the instructions.
So pipeline time =(1+(25/100)*2)=3/2=1.5
Speed up =Non-pipeline time / Pipeline time=6/1.5=4
 Question 54
An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?
 A n⁄N B 1⁄N C 1⁄A D k⁄n
Data-Structures       Cache
Question 54 Explanation:
Consider the scenario, you have k-way set associative cache, let us say a block b0 comes to set-0 and then there are k-1 unique blocks to the same set. Now the set-0 is full then one more block came to set-0 and the block b0 is replaced using LRU, if b0 comes again then it will cause a miss. But it is given that the set associativity A>=k, means the no. of blocks in a set is k or more so assume we have (k+1)-way set associativity, applying the above logic b0 comes first and then k-1 other unique accesses come to the same set-0 then there is still place for one more block in set-0 and if b0 comes again now then it will not cause a miss. As the associativity increases further there will not be any more misses other than the unique blocks we have a best case scenario. So out of N accesses only the unique blocks n can be missed and the miss ratio is n/N.
As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.
 Question 55
 A B C D
Digital-Logic-Design       Multiplexer
Question 55 Explanation:
F(P,Q,R)= P’Q’ (0) + P’Q (1) + PQ’ (R) + PQ(R’)
= P’Q + PQ’R + PQR’
= Q(P’ + P R’) + PQ’R
= Q(P’ + R’) + PQ’R
= P’Q + QR’ + PQ’R
 Question 56
The function f(x) = x sinx satisfies the following equation: f ''(x) + f(x)+ tcosx = 0. The value of t is __________.
 A -2 B -3 C -4 D -5
Engineering-Mathematics       Calculus
Question 56 Explanation:
f(x) = x Sinx
f ’(x) = x(Sinx)’ + Sin(x)(x’)
= xCosx + Sinx ---------①
f ’’(x) = x (Cosx)’ + Cos (x)’+ Cos x
= -x Sinx + 2Cosx -----------②
Given: f ’’(x) + f(x) + t Cosx = 0
Replace ① & ②,
-xSinx + 2Cosx + xSinx + tCosx = 0
2Cosx + tCosx = 0
t = -2
 Question 57
A function f(x) is continuous in the interval [0,2]. It is known that f(0) = f(2) = -1 and f(1) = 1. Which one of the following statements must be true?
 A There exists a y in the interval (0,1) such that f(y)=f(y+1) B For every y in the interval (0,1),f(y)=f(2-y) C The maximum value of the function in the interval (0,2) is 1 D There exists a y in the interval (0, 1) such that f(y)=-f(2-y)
Engineering-Mathematics       Calculus
Question 57 Explanation:
Consider this function as sum of two functions as, g(y) = f(y) -f(y+1)
Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1]
g(0) = -2, g(1) = 2
Since g is continuous and goes from negative to positive value in [0,1]. Therefore at some point g would be 0 in (0,1).
g=0 ⇒ f(y) = f(y+1) for some y in (0,1).
Apply similar logic to option D, Let g(y) = f(y) + f(2 - y)
Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1] (sum of two continuous functions is continuous)
g(0) = -2, g(1) = 2
Since g is continuous and goes from negative to positive value in [0, 1]. Therefore at some point g would be 0 in (0, 1).
There exists y in the interval (0, 1) such that:
g=0 ⇒ f(y) = -f(2 – y)
 Question 58
Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is X⁄1296. The value of X is ___________.
 A 10 B 11 C 12 D 13
Engineering-Mathematics       Probability
Question 58 Explanation:
Each dice can result from {1, 2, 3, 4, 5, 6}
To get ‘22’ as Sum of four outcomes
x1 + x2 + x3 + x4 = 22
The maximum Sum = 6+6+6+6 = 24 which is near to 22
So, keeping three 6’s, 6+6+6+x = 22
x = 4 combination① = 6 6 6 4
Keeping two 6’s, 6+6+x1+x2 = 22
x1+x2 = 10 possible x’s (5, 5) only
combination② = 6 6 5 5
No. of permutation with 6664 = 4!/ 3! = 4
“ “ “ 6655 = 4!/ 2!2! = 6
Total = 4+6 = 10 ways out of 6×6×6×6 = 1296
Pnb (22) = 10/1296 ⇒ x = 10
 Question 59
A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)}and the set of all 3-pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1).  The number of 10-pennants is ______________.
 A 89 B 90 C 91 D 92
Engineering-Mathematics       Combinatorics
Question 59 Explanation:
No twos: 1111111111⇒ 1 pennant
Single two: 211111111 ⇒ 9!/8!1! = 9 pennants
Two twos: 22111111 ⇒ 8!/6!2! = 28
Three twos: 2221111 ⇒ 7!/3!4! = 35
Four twos: 222211 ⇒ 6!/4!2! = 15
Five twos: 22222 ⇒ 1
Total = 89 pennants.
 Question 60
Let S denote the set of all functions  f:{0,1}→ {0,1}. Denote by N the number of functions from S to the set {0,1}. The value of loglog2N is ______.
 A 16 B 17 C 18 D 19
Engineering-Mathematics       Relations-and-Functions
Question 60 Explanation:
The number of functions from A to B where size of A=|A| and size of B=|B| is |B||A|
{0,1}4={0,1}×{0,1}×{0,1}×{0,1}=16
|S|=216
N=2|S|
loglogN=loglog2|S|=log |S| =log216=16
 Question 61
Consider an undirected graph where self-loops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a - c| ≤ 1 and |b - d| ≤ 1. The number of edges in this graph is __________.
 A 506 B 507 C 508 D 509
Engineering-Mathematics       Graph-Theory
Question 61 Explanation:
The total number of vertices in the graph is 12*12=144. The vertices are allowed to connect in both horizontal and vertical directions which are separated by at most 1 distance.
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.
From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012=2*E
⇒ E=506
 Question 62
An ordered -tuple (d1, d2, ..., dn) with d1 ≥ d2 ≥ ... dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, ..., dn respectively. Which of the following 6-tuples is NOT graphic?
 A (1, 1, 1, 1, 1, 1) B (2, 2, 2, 2, 2, 2) C (3, 3, 3, 1, 0, 0) D (3, 2, 1, 1, 1, 0)
Engineering-Mathematics       Graph-Theory
Question 62 Explanation:
This can be checked by Havel-hakimi theorem:
A) (1, 1, 1, 1, 1, 1)

Yes, it is a graph.
We will see that option (C) is not graphic.
 Question 63
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
 A ((p↔q)∧r)∨(p∧q∧∼r) B (∼(p↔q )∧r)∨(p∧q∧∼r) C ((p→q)∧r)∨(p∧q∧∼r) D (∼(p↔q)∧r)∧(p∧q∧∼r)
Engineering-Mathematics       Prepositional-Logic
Question 63 Explanation:
Method 1: construct the tables for all options and check with T, T, F combinations.
Method2: directly check with one of {TTF, TFT, FTT} options.
As there are two T’s in each option, replace them and check with the third value.
Eg: Place p=q= T
(∼(p↔q)∧r)∨(p∧q∧∼r)
=(∼(T↔T)∧r)∨(T∧T∧∼r)
=(∼(T)∧r)∨(T∧∼r)
=(F∧r)∨(T∧∼r)
=(F)∨(∼r)
=∼r
This is true for r=F.
Similarly with p=r=T and q=F.
q=r=T and p=F
 Question 64
 A It executes but does not give the correct result. B It executes and gives the correct result. C It generates an error because of pairwise comparison. D It generates an error because the GROUP BY clause cannot be used with table joins in a subquery.
Database-Management-System       SQL
Question 64 Explanation:
The given SQL query will display the last names and hire-dates of all latest hires in their respective departments in the location ID 1700. So, correct option is (B).
 Question 65
Consider two processors P1 and P2 executing the same instruction set. Assume that under identical conditions, for the same input, a program running on P2 takes 25% less time but incurs 20% more CPI (clock cycles per instruction) as compared to the program running on P1. If the clock frequency of P1 is 1GHz, then the clock frequency of P2 (in GHz) is _________.
 A 1.6 B 1.7 C 1.8 D 1.9
Computer-Organization       Speed-Up
Question 65 Explanation:
1 cycle time for P1=109/ 1GH=1 ns
Assume P1 takes 5 cycles for a program then P2 takes 20%more, means, 6 cycles.
P2 takes 25% less time, means, if P1 takes 5 ns, then P2 takes 3.75 ns.
Assume P2 clock frequency is x GHz.
P2 taken 6 cycles, so 6×109/x GH=3.75, x=1.6
There are 65 questions to complete.