## Gate 2012

 Question 1
Consider the following logical inferences.
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.
Which of the following is TRUE?
 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
Engineering-Mathematics       Propositional-Logic
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
Database-Management-System       Normalization
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
What will be the output of the following C program segment?
 char inchar = 'A'; switch (inchar) { case 'A' :     printf ("choice A n") ; case 'B' :     printf ("choice B ") ; case 'C' : case 'D' : case 'E' : default:     printf ("No Choice") ; }
 A No Choice B Choice A C D Program gives no output as it is erroneous
Programming       C-Programming
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
Algorithms       P-NP
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)
Data-Structures       Binary-Search-Tree
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
The truth table represents the Boolean function
 A X B X + Y C X ⊕ Y D Y
Digital-Logic-Design       Boolean-Algebra
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
Digital-Logic-Design       Number-Systems
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 process executes the code
fork();
fork();
fork();
The total number of child processes created is
 A 3 B 4 C 7 D 8
Operating-Systems       System-Calls
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
Engineering-Mathematics       Calculus
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
Computer-Networks       Application-Layer-Protocol
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
Engineering-Mathematics       Linear-Algebra
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
What is the complement of the language accepted by the NFA shown below?
 A ∅ B {ε} C a* D {a ,ε}
Theory-of-Computation       Finite-Automata
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))
Engineering-Mathematics       Propositional-Logic
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
Database-Management-System       ER-Model
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
which of the  following statements are TRUE about an SQL query? P:An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause Q:An SQL query can contain a HAVING clause even if it has a GROUP BY clause R: All attributes used in the GROUP BY clause must appear in the SELECT clause S: Not all attributes used in the GROUP BY clause need to appear in the SELECT clause
 A P and R B P and S C Q and R D Q and S
Database-Management-System       SQL
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
Data-Structures       Recursion
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
Engineering-Mathematics       Graph-Theory
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))
Algorithms       Time-Complexity
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
Digital-Logic-Design       Combinational-Circuits
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
Computer-Organization       Instruction-Pipelining
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
Engineering-Mathematics       Probability
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
Computer-Networks       Transport Layer Protocols
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
Computer-Networks       IPv4
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
Which of the following problems are decidable?
 A 1, 2, 3, 4 B 1, 2 C 2, 3, 4 D 3, 4
Theory-of-Computation       Decidability-and-Undecidability
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
Given the language L ={ab,aa,baa}, which of the following strings are in L *? 1)abaabaaabaa 2)aaaabaaaa 3)baaaaabaaaab 4)baaaaabaa
 A 1, 2 and 3 B 2, 3 and 4 C 1, 2 and 4 D 1, 3 and 4
Theory-of-Computation       Regular Languages
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
Which of the following graphs is isomorphic to
 A B C D
Engineering-Mathematics       Graph-Theory
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
Consider the following transactions with data items P and Q initialized to zero:
T1: read (P) ;
if P = 0 then Q : = Q + 1 ;
write (Q) ;
if Q = 0 then P : = P + 1 ;
write (P) ;
Any non-serial interleaving of T1 and T2 for concurrent execution leads to
 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
Database-Management-System       Transactions
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
Engineering-Mathematics       Numerical-Methods
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
Algorithms        Minimum-Spanning-Tree
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
What is the minimal form of the karnaugh map shown below? Assume that X denotes a don't care term
 A B C D
Digital-Logic-Design       K-Map
Question 30 Explanation:
 Question 31
Consider the 3 processes, P1, P2 and P3 shown in the table.
Process           Arrival time         Time Units Required
P1                0                         5
P2                1                         7
P3                3                         4
The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are
 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
Operating-Systems       Process-Scheduling
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
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.
  AcquireLock(L){
L = 1;
}
ReleaseLock(L){
L = 0;
}
This implementation
 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
Operating-Systems       Process-Synchronization
Question 32 Explanation:
Check the loop first:
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
Engineering-Mathematics       Probability
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
Computer-Networks       IPv4
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
Data-Structures       Queues
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
Consider the program given below, in a block-structured pseudo-language with lexical scoping and nesting of procedures permitted.
Program main;
Var ...

Procedure A1;
Var ...
Call A2;
End A1

Procedure A2;
Var ...

Procedure A21;
Var ...
Call A1;
End A21

Call A21;
End A21

Call A1;
End main.

Consider the calling chain : Main->A1->A2->A21->A1 The correct set of activation records along with their access links is given by :
 A B C D
Compiler-Design       Run-Time-Environments
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)
Engineering-Mathematics       Functions
Question 37 Explanation:

Onto function is possible if m ≥ n. So, no. of onto functions possible is,
nm - nC1 (n-1)m + nC2 (n-2)m + .......
Here in Question,
m = n, n = 2
So, the final answer will be,
= 2n - 2C1 (2-1)n + 2C2 (2-2)n
= 2n - 2 × 1 + 0
= 2n - 2
 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
Engineering-Mathematics       Graph-Theory
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)
Algorithms        Merge-Sort
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
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
 A SDT B SBDT C SACDT D SACET
Algorithms        Shortest-Path
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
Operating-Systems       File-System
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
Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 On a demand paged virtual memory system running on a computer system that main memory size of 3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacements policy. Then
 A OPTIMAL < LRU < FIFO B OPTIMAL < FIFO < LRU C OPTIMAL = LRU D OPTIMAL = FIFO
Operating-Systems       Page-Replacement
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) ≠ ∅
Database-Management-System       Relational-Algebra
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
Computer-Networks       Switching
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
Computer-Networks       Congestion-Control
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
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
 A B C D
Theory-of-Computation       Finite-Automata
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
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root. The appropriate expression for the two boxes B1 and B2 are
 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)
Data-Structures       Binary-Trees
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
Programming       C-Programming
Question 48 Explanation:

Hence
4 2
6 2
2 0
 Question 49
Consider the following C program
 int a, b, c = 0; void prtFun (void); int main () {     static int a = 1; /* line 1 */     prtFun();     a += 1;     prtFun();     printf ( "n %d %d " , a, b) ; }   void prtFun (void) {     static int a = 2; /* line 2 */     int b = 1;     a += ++b;     printf (" n %d %d " , a, b); } What output will be generated by the given code segment?
 A B C D
Programming       C-Programming
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
Consider the following relations A, B, C. How many tuples does the result of the following relational algebra expression contain? Assume that the schema of A U B is the same as that of
 A 7 B 4 C 5 D 9
Database-Management-System       Relational-Algebra
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
Consider the above tables A, B and C. How many tuples does the result of the following SQL query contains?
SELECT A.id
FROM   A
WHERE  A.age > ALL (SELECT B.age
FROM   B
WHERE  B. name = "arun")

 A 4 B 3 C 0 D 1
Database-Management-System       SQL
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} Compiler-Design Parsers 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 A → S So FOLLOW (S) = {$, a, b}= FOLLOW(B)
 Question 53
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3.  is the empty string, $indicates end of input, and, | separates alternate right hand sides of productions. Note:In the table second column first row it's not "A" it's "a".  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 Compiler-Design Parsers 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
Computer-Organization       Cache
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 computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit. The number of bits in the tag field of an address is
 A 160 Kbits B 136 Kbits C 40 Kbits D 32 Kbits
Computer-Organization       Cache
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
Aptitude       Numerical
Question 56 Explanation:
Total selling price =50q
Profit = 50q - 5q2
For Profit to be maximum,
d(Profit)/dq = 0
d(50q - 5q2) /dq = 0
50 - 10q = 0
50 = 10q
q = 5
 Question 57
Choose the most appropriate alternative from the options given below to complete the following sentence: Despite several ––––––––– the mission succeeded in its attempt to resolve the conflict.
 A attempts B setbacks C meetings D delegations
Aptitude       Verbal
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
Aptitude       Verbal
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.
Aptitude       Verbal
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
Choose the most appropriate alternative from the options given below to complete the following sentence: Suresh’s dog is the one ––––––––– was hurt in the stampede.
 A that B which C who D whom
Aptitude       Verbal
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
Aptitude       Verbal
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
Aptitude       Numerical
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
An automobile plant contracted to buy shock absorbers from two suppliers X and Y. X supplies 60% and Y supplies 40% of the shock absorbers. All shock absorbers are subjected to a quality test. The ones that pass the quality test are considered reliable. Of X’s shock absorbers, 96% are reliable. Of Y’s shock absorbers, 72% are reliable. The probability that a randomly chosen shock absorber, which is found to be reliable, is made by Y is
 A 0.288 B 0.334 C 0.667 D 0.72
Aptitude       Numerical
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
Aptitude       Numerical
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
Aptitude       Numerical
Question 65 Explanation:

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