GATE Previous Year Solved Papers CS
GATE Previous Year Solved Papers CS
GATE Previous Year Solved Papers CS
Solved Paper
Computer Science/IT
(Fully Solved)
GATExplore.com
1. Consider an undirected random graph of eight vertices. The probability that there
is an edge between a pair of vertices is ½. What is the expected number of
unordered cycles of length three?
Ans. (C)
1
Exp: P(edge) =
2
Ans: (C)
x 0 0.3 0.6 0.9 1.2 1.5 1.8 2.1 2.4 2.7 3.0
f(x) 0 0.09 0.36 0.81 1.44 2.25 3.24 4.41 5.76 7.29 9.00
3
The value of ∫ f ( x ) dx computed using the trapezoidal rule is
0
Ans: (D)
3
h
Exp: ∫ f ( x ) dx = 2 f ( x ) + f ( x ) + 2 ( f ( x ) + f ( x ) + ... + f ( x ) )
0
0 10 1 2 9
0.3
= 9.00 + 2 (25.65) = 9.045
2
x + 3
lim f ( x ) = lim = 2 = f (3)
x →3 − x →3 −
3
∴ f ( x ) is continuous at x = 3
5. Which one of the following expressions does NOT represent exclusive NOR of x
and y?
(A) xy + x ' y ' (B) x ⊕ y ' (C) x '⊕ y (D) x '⊕ y '
Ans: (D)
Exp: (A) x y = xy + x y
(B ) x ⊕ y = xy + x y = xy + x y = x y
(C ) ()
x ⊕ y = x y + x y = x y + xy = x y
(D ) x ⊕ y = (x) y + x y = x ⊕ y
6. In a k-way set associative cache, the cache is divided into v sets, each of which
consists of k lines. The lines of a set are placed in sequence one after another.
The lines in set s are sequenced before the lines in set (s+1). The main memory
blocks are numbered 0 onwards. The main memory block numbered j must be
mapped to any one of the cache lines from
(A) ( j mod v ) * k to ( j mod v ) *k + (k − 1)
(B) ( j mod v ) to ( j mod v ) + (k − 1)
(C) ( j mod k ) to ( j mod k ) + ( v − 1)
(D) ( j mod k ) * v to ( j mod k ) * v + ( v − 1)
Ans: (B)
Exp: Set number in the cache = (main memory block number) MOD number of sets in
the cache.
As the lines in the set are placed in sequence, we can have the lines from 0 to K
– 1 in the set.
Number of sets = v
Main memory block number = j
First line = (j mod v); last line = (j Mod v) + (k – 1)
(A) Θ n2( ) (
(B) Θ n2 logn ) ( )
(C) Θ n3 (
(D) Θ n3 logn )
Ans: (C)
n(n − 1)
For complete graph: E =
2
V =n
n(n − 1)
∴ Θ n × = Θ(n3 )
2
3. NP − complete ∈ NP
Hence, NP-complete can be solved in non-deterministic polynomial time
10. Three concurrent processes X, Y, and Z execute three different code segments
that access and update certain shared variables. Process X executes the P
operation (i.e., wait) on semaphores a, b and c; process Y executes the P
operation on semaphores b, c and d; process Z executes the P operation on
semaphores c, d, and a before entering the respective code segments. After
completing the execution of its code segment, each process invokes the V
operation (i.e., signal) on its three semaphores. All semaphores are binary
semaphores initialized to one. Which one of the following represents a deadlock-
free order of invoking the P operations by the processes?
(A) X : P ( a ) P (b ) P ( c ) Y : P (b ) P ( c ) P ( d) Z : P ( c ) P ( d) P ( a)
(B) X : P (b ) P ( a) P ( c ) Y : P (b ) P ( c ) P ( d) Z : P ( a ) P ( c ) P ( d)
(C) X : P (b ) P ( a) P ( c ) Y : P ( c ) P (b ) P ( d) Z : P ( a ) P ( c ) P ( d)
(D) X : P ( a ) P (b ) P ( c ) Y : P ( c ) P (b ) P ( d) Z : P ( c ) P ( d) P ( a)
Ans: (B)
Exp: Suppose X performs P(b) and preempts, Y gets chance, but cannot do its first
wait i.e., P(b), so waits for X, now Z gets the chance and performs P(a) and
preempts, next X gets chance. X cannot continue as wait on ‘a’ is done by Z
already, so X waits for Z. At this time Z can continue its operations as down on c
and d. Once Z finishes, X can do its operations and so Y. In any of execution
order of X, Y, Z one process can continue and finish, such that waiting is not
circular. In options (A),(C) and (D) we can easily find circular wait, thus deadlock
12. Assume that source S and destination D are connected through two intermediate
routers labeled R. Determine how many times each packet has to visit the
network layer and the data link layer during a transmission from S to D.
S R R D
Ans: (C)
Exp:
Application
Transport Application
Network Transport
13. The transport layer protocols used for real time multimedia, file transfer, DNS
and email, respectively are
(A) TCP, UDP, UDP and TCP (B) UDP, TCP, TCP and UDP
(C) UDP, TCP, UDP and TCP (D) TCP, UDP, TCP and UDP
Ans: (C)
Exp: Real time multimedia needs connectionless service, so under lying transport layer
protocol used is UDP
File transfer rums over TCP protocol with port no-21
DNS runs over UDP protocol within port no-53
Email needs SMTP protocol which runs over TCP protocol within port no – 25
Ans: (D)
Exp:
X Y
X − public Y − public
X − private Y − private
15. Match the problem domains in Group I with the solution technologies in Group
II.
Group I Group II
(p) Services oriented computing (1) Interoperability
(q) Heterogeneous communicating systems (2) BPMN
(R) Information representation (3) Publish-find bind
(S) Process description (4) XML
(A) P – 1, Q – 2, R – 3, S – 4 (B) P – 3, Q – 4, R – 2, S – 1
(C) P – 3, Q – 1, R – 4, S – 2 (D) P – 4, Q – 3, R – 2, S – 1
Ans: (C)
17. What is the maximum number of reduce moves that can be taken by a bottom-
up parser for a grammar with no epsilon- and unit-production
(i.e., of type A → ∈ and A → a) to parse a string with n tokens?
(A) n/2 (B) n-1 (C) 2n-1 (D) 2n
Ans: (C)
Exp: string = abcd
S
⇑ (7 )
YD
⇑ (6 : Y → XC )
XCD
⇑ (5 : X → AB )
ABCD
⇑ ( 4 : D → d)
ABCd
⇑ (3 : C → c )
ABcd
⇑ (2 : B → b )
Abcd
⇑ (1 : A → a)
abcd
2 × ( 4 ) − 1 = 7 reductions
⇒ 2n − 1reductions required
Note : Unit productions is given as A → a, it was typo
Above reductions are not in reverse of RMD but when they are reduced in bottom
up parsing we will get same number of reductions.
18. Consider the languages L1 = Φ and L 2 = {a} . Which one of the following
represents L1 L*2 UL*1 ?
(A) {∈} (B) Φ (C) a * (D) {ε, a}
Ans: (A)
EXP: Concatenation of empty language with any language will give the empty
language and L1 * = Φ* = ∈ . Hence L1 L*2 UL*1 = {∈}
19. Which one of the following is the tightest upper bound that represents the time
complexity of inserting an object into a binary search tree of n nodes?
(A) O(1) (B) O(log n) (C) O(n) (D) O(n log n)
Ans: (C)
Exp: For skewed binary search tree on n nodes, the tightest upper bound to insert a
node is O(n)
20. Which one of the following is the tightest upper bound that represents the
number of swaps required to sort n numbers using selection sort?
(A) O(log n) (B) O(n) (C) O(n log n) (D) O(n2)
Ans: (B)
Exp: The maximum number of swaps that takes place in selection sort on n numbers is
n
21. In the following truth table, V = 1 if and only if the input is valid.
Inputs Outputs
D0 D1 D2 D3 X0 X1 V
0 0 0 0 X X 0
1 0 0 0 0 0 1
0 1 0 0 1 1
1 X 1 0 0 1
X X X 1 1 1 1
What function does the truth table represent?
(A) Priority encoder (B) Decoder
(C) Multiplexer (D) Demultiplexer
Ans: (A)
Exp: 4 to 2 priority encoder.
22. The smallest integer than can be represented by an 8-bit number in 2’s
complement form is
(A) -256 (B) -128 (C) -127 (D) 0
Ans: (B)
Exp: −28−1 = −128 . Range is -2(n-1) to +2(n-1)-1
1 x x2
23. Which one of the following does NOT equal 1 y y2 ?
1 z z2
1 x ( x + 1) x + 1 1 x + 1 x2 + 1
(A) 1 y ( y + 1) y + 1 (B ) 1 y + 1 y2 + 1
1 z ( z + 1) z +1 1 z + 1 z2 + 1
0 x − y x2 − x2 2 x + y x2 + y2
(C ) 0 y−z y2 − z2 (D ) 2 y+z y2 + z2
1 z z2 1 z z2
Ans: (A)
If matrix B is obtained from matrix A by replacing the lth row by itself plus k
times the mth row, for l ≠ m then det(B)=det(A). With this property given
matrix is equal to the matrices given in options (B),(C) and (D).
24. Suppose p is number of cars per minute passing through a certain road junction
between 5 PM and 6PM, and p has a Poisson distribution with mean 3. What is
the probability of observing fewer than 3 cars during any given minute in this
interval?
( )
(A) 8 / 2e3 ( )
(B) 9 / 2e3 ( )
(C) 17 / 2e3 ( )
(D) 26 / 2e3
Ans: (C)
Exp:
P (p < 3) = P (p = 0 ) + P (p = 1) + P (p = 2 )
e−µ µ0 e−µ µ1 e−µ µ2
=
0!
+
1!
+
2!
( where µ = 3)
−3
e ×9
= e−3 + e−3 × 3 +
2
9 17
= e −3 1 + 3 + = 3
2 2e
26. (
Which one of the following is NOT logically equivalent to ¬∃x ∀y ( α ) ∧ ∀z ( β ) ? )
(
(A) ∀x ∃z ( ¬β ) → ∀y ( α ) ) (
(B) ∀x ∀z ( β ) → ∃y ( ¬α ) )
(C) ∀x ( ∀y ( α ) → ∃z ( ¬β ) ) (D) ∀x ( ∃y ( ¬α ) → ∃z ( ¬β ) )
Ans: (A)
Exp: ¬∃x ( ∀ y ( α ) ∧ ∀z ( β ) ) ≡ ∀ × ∀y ( α ) → ∃z ( ¬β ) option " C "
∵ ¬ (P ∧ q) ≡ p ⇒ ¬q
≡ ∀x ∀z ( β ) → ∃y ( ¬α ) option "B "
∵p ⇒ q ≡ ¬q ⇒ ¬p
≡ ∀x ∀y ( α ) → ∃z ( ¬β ) option "D "
∵ ¬ (p ∧ q) ≡ p ⇒ ( ¬q)
27. A RAM chip has a capacity of 1024 words of 8 bits each (1K × 8 ) . The number of
2×4 decoders with enable line needed to construct a
16K × 16 RAM from 1K × 8 RAM is
(A) 4 (B) 5 (C) 6 (D) 7
Ans: (B)
Exp. RAM chip size = 1k × 8 1024 words of 8 bits each
RAM to construct = 16k × 16
16k × 16
Number of chips required = = 16 × 2 [16 chips vertically with each
1k × 8
having 2 chips horizontally]
So to select one chip out of 16 vertical chips, we need 4 x 16 decoder.
Available decoder is – 2 x 4 decoder
To be constructed is 4 x 16 decoder
28. Consider an instruction pipeline with five stages without any branch prediction:
Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute
Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and
WO are 5 ns, 7 ns, 10 ns, 8 ns and 6 ns, respectively. There are intermediate
storage buffers after each stage and the delay of each buffer is 1 ns. A program
consisting of 12 instructions I1 , I2 , I3 ,......I12 is executed in this pipelined
processor. Instruction I4 is the only branch instruction and its branch target is I9 .
If the branch is taken during the execution of this program, the time (in ns)
needed to complete the program is
(A) 132 (B) 165 (C) 176 (D) 328
Ans: (C)
Exp: Total clock slots taken are 16. Each slot will take maximum of {5, 7, 10, 8 ,7}
=10.
29. Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter
MultiDequeue ( Q ) {
m=k
while ( Q is not empty ) and (m > 0 ) {
Dequeue ( Q )
m = m −1
}
}
Ans: (C)
30. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23,
39, 35, 42. Which one of the following is the postorder traversal sequence of the
same tree?
(A) 10, 20,15, 23, 25, 35, 42, 39, 30 (B) 15,10, 25, 23, 20, 42, 35, 39, 30
(C) 15,20,10, 23, 25, 42, 35, 39, 30 (D) 15,10, 23, 25, 20, 35, 42, 39, 30
Ans: (D)
Exp:
Pr eorder : 30, 20,10,15, 25, 23, 39,35, 42
Inorder : 10,15,20, 23, 25, 30,35, 39, 42
BST : 30
20 39
10 25 35 42
15 23
31. What is the return value of f (p,p ) if the value of p is initialized to 5 before the
call? Note that the first parameter is passed by reference, whereas the second
parameter is passed by value.
int f (int & x, int c ) {
c = c − 1;
if ( c == 0 ) return 1;
x = x + 1;
return f ( x, c ) * x;
}
(A) 3024 (B) 6561 (C) 55440 (D) 161051
Ans: (B)
Exp:
9 6 7 8 9
f ( x, 5)
9×9×9×9 ⇓ (1)
= 6561
f ( x, 4 ) × x
9×9×9 ⇓ (2 )
f ( x, 3) × x
9×9 ⇓ (3)
f ( x, 2 ) × x
9 ⇓ ( 4)
f ( x, 1) × x
2. G is a CFG. IS L ( G) = Σ * ?
(A) 3 only (B) 3 and 4 only (C) 1, 2 and 3 only (D) 2 and 3 only
Ans: (D)
Exp: There is an algorithm to check whether the given CFG is empty, finite or infinite
and also to convert NFA to DFA hence 1 and 4 are decidable.
33. Consider the following two sets of LR(1) items of an LR(1) grammar
X → c.X, c / d X → c.X, $
X → .cX, c / d X → .cX, $
X → .d, c / d X → .d, $
Which of the following statements related to merging of the two sets in the
corresponding LALR parser is/are FALSE?
x → c.X, c / d / $
x → .cX, c / d / $
x → .d, c / d / $
1. Merging of two states depends on core part (production rule with dot
operator), not on look aheads.
2. The two states are not containing Reduce item ,So after merging, the merged
state can not contain any S-R conflict
3. As there is no Reduce item in any of the state, so can’t have R-R conflict.
4. Merging of stats does not depend on further goto on any terminal.
So all statements are false.
35. The following figure represents access graphs of two modules M1 and M2. The
filled circles represent methods and the unfilled circles represent attributes. IF
method m is moved to module M2 keeping the attributes where they are, what
can we say about the average cohesion and coupling between modules in the
system of two modules?
Module M1 Module M2
36. In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total
length is 400 and the fragment offset value is 300. The position of the datagram,
the sequence numbers of the first and the last bytes of the payload, respectively
are
(A) Last fragment, 2400 and 2789 (B) First fragment, 2400 and 2759
(C) Last fragment, 2400 and 2759 (D) Middle fragment, 300 and 689
Ans: (C)
Exp: M= 0 – Means there is no fragment after this, i.e. Last fragment
HLEN=10 - So header length is 4×10=40, as 4 is constant scale factor
Total Length = 400(40 Byte Header + 360 Byte Payload)
Fragment Offset = 300, that means 300×8 Byte = 2400 bytes are before this last
fragment
So the position of datagram is last fragment
Sequence number of First Byte of Payload = 2400 (as 0 to 2399 Sequence no are
used)
Sequence number of Last Byte of Payload = 2400+360-1=2759
37. Determine the maximum length of cable (in km) for transmitting data at a rate of
500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal
speed in the cable to be 2,00,000 km/s
(A) 1 (B) 2 (C) 2.5 (D) 5
Ans: (B)
Exp:
500 × 106 bits − − − − − −1 sec
5 × 108 104 1
∴ 104 bits − − − − − − = sec = sec
10 4
5 × 108 5 × 104
1 sec− − − − − −2 × 105 km
1 2 × 105
∴ sec − − − − − = 4 km
5 × 104 5 × 104
4
∴ Maximum length of cable = = 2 km
2
{
(IV) < SN >| ∃SR ∃R P ( < SR , SN >∈ Stu de nts∧ < SR ,107,R P >∈ Re gistration ∧ R P > 90 )}
(A) I, II, III and IV (B) I, II and III only
(C) I, II and IV only (D) II, III and IV only
Ans: (A)
Exp: Four queries given in SQL, RA, TRC and DRC in four statements respectively
retrieve the required information.
(
(I) w1 x 0 ) W is Preempted
(
(II) Y1 , Y2 , Y3 x −2 ) Y is completed
(IV)
(
W2 , W3 x 1 ) It increments local copy of x and stores & W is completed
(V) X1 , X2 , X3 ( x 2 ) X is completed
Maximum value of x = 2
0 0
0,1
A: 0 0
0, 1
(1) L(A) is regular, its complement is also regular and if it is regular it is also
context free.
(2) L ( A ) = (11 * 0 + 0 ) ( 0 + 1) * 0 * 1 * = 1 * 0 ( 0 + 1) *
Language has all strings where each string contains ‘0’.
(3) A is not minimal, it can be constructed with 2 states
(4) Language has all strings, where each string contains ‘0’. (atleast length one)
L2 = {0 1
P q
}
0r p, q,r ≥ 0, p ≠ r is CFL
Re peats (
J = 2, 22 , 23 , 24 , − − − − − n
)
n n n k = Θ (nlogn)
to n = + 1 times k =k+
2 2 2
n n n
k= + + − − − − logn times = logn
2 2 2
n n n n
= logn + logn + logn − − − − + 1 times
2 2 2 2
n n
= + 1 . logn
2 2
(
= Θ n2 logn )
43. The number of elements that can be sorted in Θ (logn) time using heap sort is
log n
(A) Θ (1) (B) Θ ( log n ) (C) Θ
log log n
(D) Θ (log n)
Ans: (A)
Exp: After constructing a max-heap in the heap sort , the time to extract
maximum element and then heapifying the heap takes Θ (log n) time by which
we could say that Θ (log n) time is required to correctly place an element in
sorted array. If Θ (logn) time is taken to sort using heap sort, then number of
elements that can be sorted is constant which is Θ (1)
44. Consider a hard disk with 16 recording surfaces ( 0 − 15) having 16384 cylinders
(0 − 16383) and each cylinder contains 64 sectors ( 0 − 63) . Data storage capacity
in each sector is 512 bytes. Data are organized cylinder–wise and the addressing
format is <cylinder no., sector no.>. A file of size 42797 KB is stored in the disk
and the starting disk location of the file is <1200, 9, 40>. What is the cylinder
number of the last sector of the file, if it is stored in a contiguous manner?
(A) 1281 (B) 1282 (C) 1283 (D) 1284
Ans: (D)
42797 × 1024
42797 KB ≡ = 85594 sec tors
512
Starting is 1200, 9, 40 contains total 24 + ( 6 × 64 ) = 408 sec tors
Next, 1201, --------, 1283 cylinders contains total 1024 × 83 = 84992 sec tors
(∵ each cylinder contains 16 × 64 = 1024 sec tors )
∴ Total = 408 + 84992 = 85400 sec tors
∴ The required cylinder number is 12 84 which will contain the last sector of
the file
V ( e1 ) V ( e1 )
a b
V ( e4 ) V ( e4 )
V ( e2 ) ⇒ L ( G) :
G V ( e2 )
d V ( e3 ) c
V ( e3 )
Ans: (D)
Exp: “None of my friends are perfect”
= ∀x (F ( x ) → ¬P ( x ) )
= ∀x ( ¬F ( x ) ∨ ¬P ( x ) )
= ¬∃x (F ( x ) ∧ P ( x ) )
The procedure given below is required to find and replace certain characters inside an
input character string supplied in array A. The characters to be replaced are
supplied in array oldc, while their respective replacement characters are supplied
in array newc. Array A has a fixed length of five characters, while arrays oldc and
newc contain three characters each. However, the procedure is flawed
void find _ and _ replace ( char * A, char * oldc, char * newc ) {
for (int i = 0; i < 5; i + + )
for (int j = 0; j < 3; j + + )
(
if A i = = oldc j ) A i = newc j ;
}
The procedure is tested with the following four test cases
(1) oldc = " abc ", newc = " dab " (2) oldc = " cde ", newc = "bcd"
(3) oldc = "bca", newc = " cda" (4) oldc = " abc ", newc = "bac "
48. The tester now tests the program on all input strings of length five consisting of
characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out
this testing with the four test cases given above, how many test cases will be able to
capture the flaw?
(A) Only one (B) Only two (C) Only three (D) All four
Ans: (B)
Exp: Flaw in this given procedure is that one character of Array ‘A’ can be replaced by
more than one character of newc array, which should not be so.Test case (3) and
(4) identifies this flaw as they are containing ‘oldc’ and ‘newc’ array characters
arranged in specific manner. Following string can reflect flaw, if tested by test
case (3).
initially i = j = 0
b = b so replaced by c
Next i = 0 & j = 1
A = " c c d a" oldc = "b c a" newc = " c d a"
↑ ↑ ↑
i=0 j=1 j=1
c = c so replaced by d
49. If array A is made to hold the string “abcde”, which of the above four test cases
will be successful in exposing the flaw in this procedure?
(A) None (B) 2 only (C) 3 and 4 only (D) 4 only
Ans: (C)
Exp: Now for string “abcde” in array A, both test case (3) and (4) will be successful in
finding the flaw, as explained in above question.
The following code segment is executed on a processor which allows only register
operands in its instructions. Each instruction can have almost two source operands
and one destination operand. Assume that all variables are dead after this code
segment
c = a + b;
d = c * a;
e = c + a;
x = c * c;
if ( x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
50. Suppose the instruction set architecture of the processor has only two registers. The
only allowed compiler optimization is code motion, which moves statements from one
place to another while preserving correctness. What is the minimum number of spills
to memory in the compiled code?
(A) 0 (B) 1 (C) 2 (D) 3
Ans: (C)
Exp:
c = a + b; R 2 ← R1 + R2
d = c * a; spill ← R2 * R1
e = c + a; spill2 ← R2 + R1
x = c * c; R 2 ← R2 * R 2
if ( x > a) CMP R 2 R1
JNG xxx (Jump if not
greater)
{y = a * a;} R1 ← R1 * R1
goto yyy
51. What is the minimum number of registers needed in the instruction set architecture
of the processor to compile this code segment without any spill to memory? Do not
apply any optimization other than optimizing register allocation
(A) 3 (B) 4 (C) 5 (D) 6
Ans: (B)
Exp:
c = a + b; R 2 ← R1 + R 2
d = c * a; R 3 ← R 2 * R1
e = c + a; R 4 ← R 2 + R1
x = c * c; R 2 ← R2 * R 2
if ( x > a) CMP R 2 R1
JNG xxx (Jump if not
greater)
{y = a * a;} R1 ← R1 * R1
goto yyy
else xxx : R 3 ← R 3 * R3
{ R4 ← R4 * R4
d = d * d; yyy : Exit
e = e * e;
}
In the above code minimum number of registers are used = 4
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.
F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional
dependencies (FDs) so that F + is exactly the set of FDs that hold for R
A computer uses 46–bit virtual address, 32–bit physical address, and a three–level
paged page table organization. The page table base register stores the base
address of the first–level table ( T1 ) ,which occupies exactly one page. Each entry of
T1 stores the base address of a page of the second–level table ( T2 ) . Each entry of T2
stores the base address of a page of the third–level table ( T3 ) Each entry of T3 stores
a page table entry (PTE). The PTE is 32 bits in size. The processor used in the
computer has a 1 MB 16 way set associative virtually indexed physically tagged cache.
The cache block size is 64 bytes.
32 − bits
32 − bits
220
number of sets = 10
= 210
2
Index of cache bits will be used as frame bits.
20 12
F.No offset
12
Frame size = 2 =4K bytes
55. What is the minimum number of page colours needed to guarantee that no two
synonyms map to different sets in the processor cache of this computer?
(A) 2 (B) 4 (C) 8 (D) 16
Ans:
58. Which one of the following options is the closest in meaning to the word given
below?
Nadir
(A) Highest (B) Lowest (C) Medium (D) Integration
Ans: (B)
Nadir in the lowest point on a curve
60. What will be the maximum sum of 44, 42, 40, ... ?
(A) 502 (B) 504 (C) 506 (D) 500
Ans: (C)
The maximum sum is the sum of 44, 42,- - - - -2.
The sum of ‘n’ terms of an AP
n
= 2a + (n − 1) d
2
In this case, n = 22, a = 2 and d = 2
∴ Sum = 11 4 + 21 × 2 = 11 × 46 = 506
61. Out of all the 2-digit integers between 1 and 100, a 2-digit number has to be
selected at random. What is the probability that the selected number is not
divisible by 7?
(A) 13/90 (B) 12/90 (C) 78/90 (D) 77/90
Ans: (D)
The number of 2 digit multiples of 7 = 13
∴ Probability of choosing a number
90 − 13 77
Not divisible by 7 = =
90 90
62. A tourist covers half of his journey by train at 60 km/h, half of the remainder by
bus at 30 km/h and the rest by cycle at 10 km/h. The average of the tourist in
km/h during his entire journey is
(A) 36 (B) 30 (C) 24 (D) 18
Ans: (C)
Let the total distance covered be ‘D’
D
Now, average speed =
Total time taken
D 1 120
= = = = 24 km / hr
D D D 1 1 1 5
2 + +
+ 4 + 4 120 120 40
60 30 10
( 2 ) − ( 1) + ( 3 ) − ( 2 ) ( ) −( )
2 2 2 2 2 2
81 80
+−−−−−
1+ 2 2+ 3 80 + 81
=
( 2 − 1 )( 1+ 2 )+−−−−−−+( 81 − 80 )( 81 + 80 )
( 1+ 2 ) 80 + 81
64. The current erection cost of a structure is Rs. 13,200. If the labour wages per
day increase by 1/5 of the current wages and the working hours decrease by
1/24 of the current period, then the new cost of erection in Rs. is
(A) 16,500 (B) 15,180 (C) 11,000 (D) 10,120
Ans: (B)
Let ‘W’ be the labour wages, and ‘T’ be the working hours.
Now, total cost is a function of W × T
Increase in wages = 20%
∴ Revised wages = 1.2 W
100
Decrease in labour time = %
24
1 23
∴ Re vised time = 1 − T = 24 T
24
23
∴ Re vised Total cos t = 1.2 × WT = 1.15 WT
24
= 1.15 × 13200 = 15180
65. After several defeats in wars, Robert Bruce went in exile and wanted to commit
suicide. Just before committing suicide, he came across a spider attempting
tirelessly to have its net. Time and again, the spider failed but that did not deter
it to refrain from making attempts. Such attempts by the spider made Bruce
curious. Thus, Bruce started observing the near-impossible goal of the spider to
have the net. Ultimately, the spider succeeded in having its net despite several
failures. Such act of the spider encouraged Bruce not to commit suicide. And
then, Bruce went back again and won many a battle, and the rest is history.
Which one of the following assertions is best supported by the above information?
(A) Failure is the pillar of success
(B) Honesty is the best policy
(C) Life begins and ends with adventures
(D) No adversity justifies giving up hope
Ans: (D)
Total Number of
Section Classification 1 Mark 2 Marks Questions
Engineering Mathematics 2 3 5
Discrete Mathematics 3 2 5
Digital Logic 1 2 3
Computer Organization 2 2 4
Theory of Computation 1 3 4
Data Structures &
Algorithms 9 5 14
Compiler Design 1 3 4
Operating Systems 2 2 4
DBMS 1 3 4
Computer Networks 2 2 4
SEWT 1 3 4
Verbal Ability 2 3 5
Numerical Ability 3 2 5
30 35 65
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
1
Shared on QualifyGate.com
CS-GATE-2015
GATE 2015
th
8 February 9:00 to 12:00
1. Let f(x) be a linear function such that f ( −2 ) = 29 and f ( 3) = 39. Find the value of f(5).
3. Consider a program code which was fed with 100 artificial errors. On analyzing the
errors, 159 errors were reported of which 75 were the artificial errors that were initially
seeded. What is the closest approximation of the number of errors in the program?
5. Consider a power set U of a set S = {1, 2,3, 4,5,6}. Let T ∈ U such that T’ denotes the
compliment of the set and |T| denote the number of elements in T. Let T/R denote the set
of elements which are T but not in R. Which of the following is true?
(A) ∀X ∈ U ( X = X′ )
(B) ∃X∃Y ∈ U ( X = 5, Y = 5, X ∩ Y = φ )
(C) ∀X∀Y ∈ U ( X = 2, Y = 3, X Y = φ )
(D) ∀X∀Y ∈ U ( X Y = Y′ X′ )
6. The maximum number of processes that can be in READY state on a processor with n
CPUs is?
(A) n (B) n − 1 (C) 2^n (D) Independent of n
Key: (D)
Exp: Number of processes which are in running proceses will be atmost n as there are n
processors. Maximum no. of processes that will be in ready state in independent of no. of
processors.
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
2
Shared on QualifyGate.com
CS-GATE-2015
8. Consider a hash table with 25 slots and 200 entries. What is the load factor α of the hash
table?
10. How many 4-digit numbers can be formed such that the digits are in non-decreasing order
(from left to right) using only digits {1, 2, 3}?
11. Question on critical section where two processes P1 and P2. It asks about mutual exclusion
and deadlock.
ii. θ( n3 )
iii. O ( n ^ 5 )
iv. Ω ( n ^ 5 )
Which of the above can correctly replace X?
(A) Only I (B) I and II (C) I, III and IV (D)
Key: (C)
n 2 (n + 1)2
Exp: X= sum of the cabes of n natural numbers = which is θ(n 4 ), 0(n 5 ) & Ω (n 3 ) .
4
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
3
Shared on QualifyGate.com
CS-GATE-2015
p = s1+2;
*p = ‘0’;
Printf(“%s”, s1);
}
(A) 12 (B) 120400 (C) 1204 (D)
Key: (1204)
Exp: 1 2 3 4 10
1 2 3 4
15. Consider the language L = Σ * 0011 Σ * where Σ = {0,1}. What is the minimum number of
states in the DFA of compliment of L i.e. L’?
16. The elements 71, 65, 84, 69, 67, 83 are inserted in a binary search tree. The element in the
lowest level is?
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
4
Shared on QualifyGate.com
CS-GATE-2015
Exp: 71
65 84
83
69
67
19. Given a relation (PQRTUV) and the following two functional dependencies:
PQ -> RS.
Which of the following is a trivial FD which can be implied from F+ over F?
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
5
Shared on QualifyGate.com
CS-GATE-2015
(or)
V = 0.2 × ω8 m / s
21. Consider a binary tree with 200 leaf nodes. What is the number of nodes having exactly
two children?
Key: 399
n +1
Exp: p=
2
p = 200
n +1
200 =
2
2(200) = n + 1
n = 400 − 1 = 399
A B C D E
A AB A
B C −
C − D
D − E
E E E
AB ABC A
ABC ABC AD
AD AB AE
AE ABE AE
ABE ABCE AE
ABCE ABCE ADE
ADE ABE AE
22. Consider a 2 ^ 20 byte addressable main memory and block size of 16 bytes with a direct
mapped cache of 2 ^12 cache lines. Two bytes are consecutively stored in the memory
addresses ( E201F )16 and ( E2020 )16 . What is the tag and cache line address of address
( E201F )16 ?
(A) E, 201 (B) E, E201 (C) F, 201 (D) ..
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
6
Shared on QualifyGate.com
CS-GATE-2015
23. There are types of people. Type 1 always tells the truth and Type 2 always tell the lie. A
coin is tossed by one person whose type is unknown. He does not tell the result of coin
toss till asked. Upon asking, he replies:
“The coin toss has resulted in heads if and only if I tell the truth”
Which is the following is true?
(A) Result is head
(B) Result is tail
(C) If person is Type 1, then result is tail
(D) If person is Type 2, then result is tail
g(5)
g(3)
g(1) g(−1)
g(1) g(−1)
g(3) g(1)
g(1) g(−1)
g(0) g(−2)
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
7
Shared on QualifyGate.com
CS-GATE-2015
25. Question about GoBackN and minimum number of bits in sequence number. W>= 1+2a
26. A language L1 is polynomial time reducible to L2. A language L3 is also polynomial time
reducible to L2, which in turn is polynomial time reducible to L4. Which of the following
statement are true?
i. If L4 ∈ P, then L2 ∈ P
ii.
iii.
iv. If L4 ∈ P, then L1∈ P and L3 ∈ P
Key: (C)
Exp: L 2 ≤ pL 4
L1 ≤ pL 2
If L 4 ∈ P then L 2 ∈ P hence L1 ∈ P hence option C.
27. Mergesort algorithm takes about 30 seconds on an input of 64 elements. What is the
correct approximation for the number of elements that can be sorted in 6 minutes using
mergesort?
Key: 256
Exp: Time complexity = 0(n log n)
0(n log n) = 30s.
n = 64
θ ( 64 × log 64 ) = 30
28. Consider a network 200.10.11.144/27. What is the value of the last octet (in decimal) of
the last host in this network?
Key:
Exp: Given IP address 200.10.11.144/27
To find out the loss address in a block, we have to set (32-4) no. of right most bits to 1.
n=27
32 − n = 32 − 27 = 5
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
8
Shared on QualifyGate.com
CS-GATE-2015
200.10.11.10011111
200.10.11.159
∴ CDR Address range is 200.10.11.128/27-200.10.11.159/27
But w.r.t the question, the volume of the last octet of last host in this n/w is
200.10.11.158.
30. Consider a relation R on ordered pair of integers such that (( p,q ) , ( r,s ) ) ∈ R If
p − s = q − r.
Which of the following is true about the relation R?
(A) Reflexive and Symmetric
(B) Not reflexive but symmetric
(C) Reflexive but not symmetric
(D) Not reflexive nor symmetric
Key: (B)
Exp: R is reflexive if (p,q) R (p,q) ∀ p,q ∈ z
(p,q) R (p,q) if p-q = q-p which is false
∴ R is not reflexive
R is symmetric is (p,q) R (r,s) then (r,s) R (p,q)
If (p,q) R (r,s) then p-s = q-r
If (r,s) R (p,q) then r-q = s-p which is true when p-s = q-r
∴ R is symmetric
31. A graph consists of 100 vertices and 300 edges. The minimum spanning tree of the graph
has a weight of 500. The weight of each edge is then increased by 5. The weight of the
new MST is___.
Key: 995
Exp: 100 vertices and weight 500
So there 99 edges with weight 500.
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
9
Shared on QualifyGate.com
CS-GATE-2015
32. Mccabe cyclomatic complexity of two modules A and B, and their combined cyclomatic
complexity: Answer: 4,4,7
33. Two hosts communicate using packet switched. The hosts are connected via a switch over
10^7 bit per second links. The propagation delay on both links is 20 microseconds. The
hosts send a total of 10000 bits in two packets of 5000 bits each. The switch waits for 35
microseconds between sending a frame and receiving a frame. What is the total delay (in
microseconds) between sending the last bit and receiving the first bit?
1 1 2
34. The function af ( x ) + bf = − 25. What is the value of ∫ f ( x ) dx ?
x x 1
1 47b
z (
(A) z
a ln 2 − 25 ) +
a −b 2
35. The maximum number of possible solutions to the equation ( 43) x = ( y3)8 are:
Key: (5)
Exp: (43)x = (y3)8
⇒ 3+4x = 3+8y ⇒ 4x = 8y
⇒ x = 2y
⇒ x≥5 and y≤7
∴ 5 solutions are possible which are (14,7), (12,6), (10,5), (8,4) and (6,3)
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
10
Shared on QualifyGate.com
CS-GATE-2015
main ( ){
int x = 1;
x + f1 ( ) + f2 ( ) + f3 ( ) + f2 ( )
pr int f ( "%d, x ) ;
return 0;
}
{a m
b n m = 2n + 1} This is CFL.
37. An array C =< c0 , c1..ck −1 > has elements from either 0 or 1. Consider the following code:
DoSomething(c,a,n)
{
z < −1
For i = 0 to k − 1
do
z < − z 2 mod n
if c [i ] = 1
z < −a * z mod n
end
return z;
}
If k − 4, c =< 1,0,1,1 >, a = 2, and n = 8 , what is the value returned?
Key: (0)
Exp: C i 0 1 1
2=0
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
11
Shared on QualifyGate.com
CS-GATE-2015
20something
{z = 1
k=0
for i = 0 + 0.3
z =1
do
Ans: z=0
ii. {a m
bn a m bn }
iii. {a m
b n 2m = n + 1 }
39. Consider a binary function F = P′ + QR such that P′ = !P. Which of the following is
correct for F?
i. F = Σ ( 4,5,6 )
ii. F = Σ ( 0,1, 2,3,7 )
iii. F = Π ( 4,5,6 )
iv. F = π ( 0,1, 2,3,7 )
(A) only A (B) only B (C) Both B & C (D) Both A & C
Key:
Exp: F = P ′ + QR
QR
00 01 11 10
P
0 1 1 1 1
1 0 0 1 0
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
12
Shared on QualifyGate.com
CS-GATE-2015
41. A B+ tree has a search value field of 12 Bytes, a record pointer of ..bytes, and a block
pointer of 8 bytes with block size 1024. What is the maximum number of keys that can be
accommodated in a non-leaf node?
Key: 50
Exp: Suppose that ‘k’ is order of the non-leaf node
k(8)+(k-1)12 ≤ 1024
20k≤1036
1036
k≤ ⇒ k ≤ 51
20
As the order is 51, maximum we can store 50 keys
ptr + +;
pr int f ( ''%d%d", ptr − p, **ptr ) ;
}
What is the output?
46. Question about computing Function point after providing all the parameter values
47. Question about smallest turnaround time in OS after providing four processes:
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
13
Shared on QualifyGate.com
CS-GATE-2015
AT BT LT TAT
P0 0 4 4 4
P1 1 6 15 14
P2 4 3 7 3
P3 6 2 9 3
24
=6
4
Gautt Chart
P0 P2 P3 P1
0 4 7 9 15
p1 − 6 p1 − 6 p1 − 6
p2 − 3 p3 − 2
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
14
Shared on QualifyGate.com
CS-GATE-2015
(C) SRTF
AT BT LT TAT
P0 0 4 4 4
P1 1 6 15 14
P2 4 3 7 3
P3 6 2 9 3
24
=6
Gautt Chart 4
P0 P2 P3 P1
0 4 7 9 15
P0 P0 P2 P2 P3 P1
0 1 4 6 7 9 15
p0 − 3 p1 − 6 p1 − 6 p1 − 6 p1 − 6
p1 − 6 p2 − 3 p2 − 1 p3 − 2
p3 − 2
AT BT LT TAT
P0 0 4 6 6
P1 1 6 15 14
P2 4 3 13 9
P3 6 2 12 6
35
= 8.7 ⇒ R.Q : Po P1P0 P2 P1P3 P2 P1
4
Gautt Chart
P0 P1 P0 P2 P1 P3 P2 P1
0 2 4 6 8 10 12 13 15
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
15
Shared on QualifyGate.com
CS-GATE-2015
51. Consider three random variables X i with i = {1, 2,3}. X i is either 0 or 1 for i = {1, 2,3}
Consider another variable Y = X1 .X 2 ⊕ X 3 . What is the probability of P Y = 0 X3 = 0 ?
Disclaimer – This paper analysis and questions have been collated based on the memory of some students who
appeared in the paper and should be considered only as guidelines. GATEFORUM does not take any responsibility for
the correctness of the same.
16
|CS| GATE-2016-PAPER-01 www.gateforum.com
General Aptitude
1. Out of the following four sentences, select the most suitable sentence with respect to grammar
and usage.
(A) I will not leave the place until the minister does not meet me.
(B) I will not leave the place until the minister doesn’t meet me.
(C) I will not leave the place until the minister meet me.
(D) I will not leave the place until the minister meets me.
Key: (D)
Key: (A)
3. Archimseedes said, “Give me a lever long enough and a fulcrum on which to place it, and I
will move the world.”
Key: (A)
4. If ‘relftaga’ means carefree, ‘otaga’ means careful and ‘fertaga’ means careless, which of the
following could mean ‘aftercare’?
Key: (C)
5. A cube is built using 64 cubic blocks of side one unit. After it is built, one cubic block is
removed from every corner of the cube. The resulting surface area of the body (in square
units) after the removal is.
Key: (D)
Exp: Four blocks are needed for each direction(totally 3 directions) to build a bigger cube
containing 64 blocks. So area of one side of the bigger cube= 4 × 4 = 16units
When cubes at the corners are removed they introduce new surfaces equal to exposes surfaces
so the area of the bigger cube does not change from 96
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
6. A shaving set company sells 4 different types of razors, Elegance, Smooth, Soft and
Executive.
Elegance sells at Rs. 48, Smooth at Rs. 63, Soft at Rs. 78 and Executive at Rs. 173 per piece.
The table below shows the numbers of each razor sold in each quarter of a year.
Which product contributes the greatest fraction to the revenue of the company in that year?
Key: (B)
7. Indian currency notes show the denomination indicated in at least seventeen languages. If this
is not an indication of the nation’s diversity, nothing else is.
Which of the following can be logically inferred from the above sentences?
(C) Indian currency notes have sufficient space for all the Indian languages.
Key: (D)
8. Consider the following statements relating to the level of poker play of four players P, Q, R and
S.
I. P always beats Q
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Which of the following can be logically inferred from the above statements?
(A) (i) only (B) (ii) only (C) (i) and (ii) (D) neither (i) nor (ii)
Key: (D)
Key: (B)
2x 7 + 3x − 5 = 0
2(1)7 + 3(1) − 5 = 0
5−5 = 0
So (x − 1) is a factor of f (x)
10. In a process, the number of cycles to failure decreases exponentially with an increase in load.
At a load of 80 units, it takes 100 cycles for failure. When the load is halved, it takes 10000
cycles for failure. The load for which the failure will happen in 5000 cycles is .
Key: (B)
exp onent
load =
log(cycles)
x
80 = ⇒ x = 160
log(10000)
x
40 = ⇒ x = 160
log(10000)
160
load = = 43.25
log 5000
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
q: x is a composite number
r: x is a perfect square
s: x is a prime number
Key: (11)
Exp: ~ ( ( p ⇒ q ) ∧ ( ~ r ∨ v ~ s ) ) =~ ( P ⇒ q ) ∨ ~ ( ~ r ∧ ~ s )
=~ ( p ⇒ q ) ∨ ~ ( r ∧ s )
=~ ( p ⇒ q ) ∨ ( r ∧ s )
=~ ( ~ p ∨ q ) ∧ ( r ∧ s )
= ( p∧ ~ q ) ∨ ( r ∧ s )
2. Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of
the following is the recurrence relation for an?
Key: (B)
a n −2
∴ a n = a n −1 + a n − 2
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
sin ( x − 4 )
3. lim = __________.
x →4
x−4
Key: (1)
Exp:
sin(x − 4)
lim
x →4 x−4
sin(x − 4)
= lim
x − 4→ 0 x−4
sin y
= lim (By taking y = x − 4)
y→0 y
=1
4. A probability density function on the interval [a, 1] is given by 1/x2 and outside this interval
the value of the function is zero. The value of a is____.
Key: (0.5)
1
f (x) = x ∈[a,1]
Exp: Given x2
= 0 other wise
'
We know that ∫ f (x)dx = 1
a
1
' 1 −1
⇒∫ dx = 1 ⇒ = 1
a x2
x a
1
⇒ −1 = 1
a
⇒ a = 0.5
Key: (15)
Exp: Given that 2 + −1 and 3 are two Eigen values of 3×3 real matrix is, 2 + i and 3 are Eigen
values.
But 2-i also Eigen values (∵ complex roots occurs in pair only )
= ( 2 + i ) × (2 − i) × 3 = 5 × 3 = 15
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (A)
7. The 16-bit 2’s complement representation of an integer is 1111 1111 1111 0101; its decimal
representation is _________.
Key: (-11)
Exp:
So result is -11
8. We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then
repeats. The minimum number of J-K flip-flops required to implement this counter is
________.
Key: (4)
9. A processor can support a maximum memory of 4 GB, where the memory is word-
addressable (a word consists of two bytes). The size of the address bus of the processor is at
least __________ bits.
Key: (31)
10. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are
performed efficiently. Which one of the following statements is CORRECT (n refers to the
number of items in the queue)?
(B) At most one operation can be performed in O(1) time but the worst case time for the
other operation will be Ω(n)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
(C) The worst case time complexity for both operations will be Ω(n)
(D) Worst case time complexity for both operations will be Ω(log n)
Key: (A)
b c
a f
d e
The number of different topological orderings of the vertices of the graph is __________.
Key: (6)
Exp:
abcdef
adebcf
abdcef
adbcef
abdecf
adbecf
void main()
int i = 100;
short s = 12;
short *p = &s;
Which one of the following expressions, when placed in the blank above, will NOT result in a
type checking error?
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (D)
Exp: Here function f takes two arguments one is int and the other is short and its return type is void.
So, in main function ‘P’ is a pointer to short and when we call f (i,*p) there won’t be any type
checking error.
13. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
(A) Θ(n log n), Θ(n log n), and Θ(n2)
Key: (D)
Quick sort θ(n log n) best case and θ(n 2 ) worst cases
14. Let G be a weighted connected undirected graph with distinct positive edge weights. If every
edge weight is increased by the same value, then which of the following statements is/are
TRUE?
(A) P only (B) Q only (C) Neither P nor Q (D) Both P and Q
Key: (A)
#include<stdio.h>
int *temp;
temp = ptrb;
ptrb = ptra;
ptra = temp;
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
int main() {
mystery(&a, &b);
if (a < c)
mystery(&c, &a);
mystery(&a, &d);
printf("%d\n", a);
Key: (2016)
Exp: Output is not affected by the function mystery () as it is just taking the address of a&b into
ptra & ptrb and contents of ptra & ptrb are swapped leaving a&b as it is.
S → aS bS ε
(A) {a b n m
| n,m ≥ 0}
(B) {w ∈{a,b} *
| w has equal number of a 's and b 's}
(C) {a n
| n ≥ 0} ∪ {bn | n ≥ 0} ∪ {a n bn | n ≥ 0}
Key: (D)
Exp: Given grammar generates all strings of a’s and b’s including null string
∴ L = ( a + b) *
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (C)
Exp: There is no known algorithm to check whether the language accepted by TM is empty.
Similarly there is no algorithm to check whether language CFG’s are equivalent.
18. Which one of the following regular expressions represents the language: the set of all binary
strings having two consecutive 0s and two consecutive 1s?
Key: (B)
Exp: (a) contains 00 & 11 consecutively which is not the required condition.
(c) Doesn’t guaranty that both 00 & 11 will be present in the string.
(d) Says string should start with 11 & ends with 00 or vice versa.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of total variables required to convert the above code segment to static
single assignment form is _________.
Key: (7)
20. Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths
submitted at the same time to a computer system. Which one of the following process
scheduling algorithms would minimize the average waiting time in the ready queue?
(B) Round-robin with time quantum less than the shortest CPU burst
(D) Highest priority first with priority proportional to CPU burst length
Key: (A)
Exp: SRTF is pre emptive SJF which produces less average waiting time.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
21. Which of the following is NOT a super key in a relational schema with attributes V ,
W , X , Y , Z and primary key V Y ?
Key: (B)
22. Which one of the following is NOT a part of the ACID properties of database transactions?
Key: (D)
23. A database of research articles in a journal uses the following schema. (VOLUME,
NUMBER, STARTPAGE, ENDPAGE, TITLE, YEAR, PRICE)
Which is the weakest normal form that the new database satisfies, but the old one does not?
Key: (A)
(Volume number) → year is a partial dependency. So original table is in 1NF but not in 2NF
24. Which one of the following protocols is NOT used to resolve one form of address to another
one?
Key: (C)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Exp: Except DHCP, remaining all the protocols are used to resolve one form of address to another
one.
25. Which of the following is/are example(s) of stateful application layer protocols?
Key: (C)
Key: (10)
3
Exp: (x 3
+ x 4 + x 5 + x 6 + ...)
3
= x 9 (1 + x + x 2 + ...)
3
= x 9 ( (1 − x)−1 )
= x 9 (1 − x)−3
∞
(n + 1)(n + 2) n
= x9 ∑ x
n =0 2
4×5
For coefficient of x12 put n=3 = = 10
2
Key: (198)
n = ( An + Bn + c ) n
Let the particular solution be a (b) 2
…(2)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
n + a n = C1 + ( 2n + 4n + 2 ) n
General solution is an = a (c) (b) 2
given a1 = B ⇒ B = c1 + B ⇒ c1 = 0
Given a 99 = k × 104
K=198
28. A function f : N+ → N+, defined on the set of positive integers N+, satisfies the following
properties
f (n) = f (n + 5) if n is odd
Let R = {i | ∃ j: f (j) = i} be the set of distinct values that f takes. The maximum possible size
of R is ____________.
Key: (2)
n
Exp: Given f (n) = f if n is even
2
= f(n+5) if n is odd
Clearly, the range of f(x) will contain two distinct elements only.
Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output N and
stop.
The probability that the output of the experiment is Y is (up to two decimal places)
__________.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (0.33)
Exp: From the given steps we can observe that probabilities of y are
2
1 1 1 1 1
, , ,.....
4 4 4 4 4
Required probability
1 1 1 1 1
2
= + × + × + ....
4 4 4 4 4
2 3
1 1 1
= + + + ...
4 4 4
1 1 1 1 1 1 4 1
2
= 1 + + + ... = = × = = 0.33
4 4 4 4
1− 1 4 3 3
4
30. Consider the two cascaded 2-to-1 multiplexers as shown in the figure.
R
0 0 0
2 − to − 1 X
2 − to − 1
MUX Y1 M UX
R 1 s 1 s
P Q
Key: (D)
31. The size of the data count register of a DMA controller is 16 bits. The processor needs to
transfer a file of 29,154 kilobytes from disk to main memory. The memory is byte
addressable. The minimum number of times the DMA controller needs to get the control of
the system bus from the processor to transfer the file from the disk to main memory is
__________.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (456)
29154kB
DMA controller needs ⇒ ⇒ 455.53125 = 456
Exp: 216 byte
32. The stage delays in a 4-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage
(with delay 800 picoseconds) is replaced with a functionally equivalent design involving two
stages with respective delays 600 and 350 picoseconds. The throughput increase of the
pipeline is _________ percent.
Key: (33.33)
Exp:
800 − 600
Throughput = ×100% = 33.33%
600
33. Consider a carry look ahead adder for adding two n-bit integers, built using gates of fan-in at
most two. The time to perform addition using this adder is
Key: (B)
34. The following function computes the maximum value contained in an integer array p[ ] of size
n (n >= 1).
while ( _________ ) {
else { b = b-1; }
return p[a];
Key: (D)
Exp: When a=b then P[a] will have the maximum value of the array
if(n>1) count(n-1);
void main(){
count(3);
m ain ( )
Key: (A)
Exp: C ount(3)
Pr(4)
Pr(3) Pr(1) C ount (2)
Pr(4)
Pr(2) Pr(2) C ount (1)
Pr(4)
Pr(1) Pr(3) C ount (0)
Output is 31 22 13 4 4 4
36. What will be the output of the following pseudo-code when parameters are passed by
reference and dynamic scoping is assumed?
a=3;
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (D)
Exp: Dynamic scoping looks for the definition of free variable in the reverse order of calling
sequence.
37. An operator delete (i) for a binary heap data structure is to be designed to delete the item in
the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of
the array. If the heap tree has depth d (number of edges on the path from the root to the
farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal
of the element?
(C) O(2d ) but not O(d) (D) O(d 2d ) but not O(2d )
Key: (B)
38. Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is
given by the entry Wi j in the matrix W.
0 2 8 5
2 0 5 8
W=
8 5 0 x
5 8 x 0
The largest possible integer value of x, for which at least one shortest path between some pair
of vertices will contain the edge with weight x is __________.
Key: (12)
8
Exp: d b
x 2
5 5
a c
8
If x=12 then the shortest path between d & c will contain edge with lable ‘x’.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
39. Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2,
3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can
have is ___________.
Key: (7)
Exp: 4 4
1 3 ⇒ 1
5 6
2 2
40. G = (V, E ) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE?
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
(A) I only (B) II only (C) both I and II (D) neither I nor II
Key: (B)
41. Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns
the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns
the element at the top of S without removing it from S. Consider the algorithm given below.
x := Dequeue(Q);
Push(S, x);
else
x := Pop(S);
Enqueue(Q, x);
end
end
The maximum possible number of iterations of the while loop in the algorithm is
_________.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (256)
Which one of the following pairs of languages is generated by G1 and G2, respectively?
Key: (D)
Lagrange’s generated by G 2 = a + b* \ b +
43. Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and
stack alphabet Γ = {X , Z}. Z is the initial stack symbol. Let L denote the language accepted
by the PDA.
a, X XX
a, Z XZ b, X ε
b, X ε ε, Z Z
(C) L is not accepted by any Turing machine that halts on every input
Key: (D)
44. Let X be a recursive language and Y be a recursively enumerable but not recursive language.
Let W and Z be two languages such that Y reduces to W , and Z reduces to X (reduction
means the standard many-one reduction). Which one of the following statements is TRUE?
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Key: (C)
45. The attributes of three arithmetic operators in some programming language are given below.
Key: (9)
Exp: 2 − 5 +1 − 7 *3
2 − ( 5 + 1) − 7*3
2 − 6 − 7 *3
2 − ( 6 − 7 ) *3
2 − ( − 1) *3
( 2 + 1) *3
3*3 = 9
46. Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S,
A} and terminals {a, b}.
S → aA {print 1}
S→a {print 2}
A → Sb {print 3}
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:
Key: (C)
Exp:
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
a A 2 print ( 3)
print ( 2) 1 S b
a
47. Consider a computer system with 40-bit virtual addressing and page size of sixteen
kilobytes. If the computer system has a one-level page table per process and each page table
entry requires 48 bits, then the size of the per-process page table is _________ megabytes.
Key: (384)
LAS 240
∴ No. of pages ( n ) = = = 226 = 64M
PS 214
48. Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11,
92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number
63, moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered
from 0 to 199. The total head movement (in number of cylinders) incurred while servicing
these requests is __________.
Key: (346)
24 5 29 70
101
1 27 9
∴ Total Head movements = 24 + 5 + 29 + 70 +181 +1 + 27 + 9 = 346
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
49. Consider a computer system with ten physical page frames. The system is provided with an
access sequence (a1, a2, . . . , a20, a1, a2, . . . , a20), where each ai is a distinct virtual page
number. The difference in the number of page faults between the last-in-first-out page
replacement policy and the optimal page replacement policy is __________.
Key: (1)
LIFO 0 a1
1 a2
2 a3
3 a4
4 a5
5 a6
6 a7
7 a8
8 a9
9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a 20
Now a1 to a9 Hit
Optimal 0 a1
1 a2
2 a3
3 a4
4 a5
5 a6
6 a7
7 a8
8 a9
9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a 20
Next a1 to a9 Hit
again a10 to a19 replace any location from 0 to 9 for a20 Hit.
Difference = 31 − 30 =1
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
50. Consider the following proposed solution for the critical section problem. There are n
processes: P0. . . Pn−1. In the code, function pmax returns an integer not smaller than any of
its arguments. For all i, t[i] is initialized to zero.
do {
while (c[j]);
Critical Section;
t[i]=0;
Remainder Section;
} while (true);
(A) At most one process can be in the critical section at any time
Key: (A)
51. Consider the following two phase locking protocol. Suppose a transaction T accesses (for
read or write operations), a certain set of objects {O1, . . . , Ok}. This is done in the following
manner:
Key: (A)
Exp: 2PL ensures serializability and here as we are following linear order in acquiring the locks
there will not be any deadlock.
52. Consider that B wants to send a message m that is digitally signed to A. Let the pair of private
and public keys for A and B be denoted by K −x and K +x for x = A, B, respectively. Let Kx(m)
represent the operation of encrypting m with a key Kx and H (m) represent the message
digest. Which one of the following indicates the CORRECT way of sending the message m
along with the digital signature to A?
(A) {m, K ( H ( m ) )}
+
B
(B) {m, K ( H ( m ) )}
−
B
(C) {m, K ( H ( m ) )}
−
A
(D) {m, K +A ( m )}
Key: (B)
Hash
M
function
Exp:
Senders private
H ( m)
key(K B − )
K B − ( H(m) )
Digital signature generator
+ M ⊕ K B − ( H(m) )
53. An IP datagram of size 1000 bytes arrives at a router. The router has to forward this packet on
a link whose MTU (maximum transmission unit) is 100 bytes. Assume that the size of the IP
header is 20 bytes.
The number of fragments that the IP datagram will be divided into for transmission is
________.
Key: (13)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
54. For a host machine that uses the token bucket algorithm for congestion control, the token
bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per
second. Tokens arrive at a rate to sustain output at a rate of 10 megabytes per second. The
token bucket is currently full and the machine needs to send 12 megabytes of data. The
minimum time required to transmit the data is __________ seconds.
Key: (1.2)
Exp: Given
C =1Mb
Max Output rate = 20 Mbps
Arrival rate = 10Mbps
c
∴ The minimum time required to transmit the data is S =
m−ρ
1 Mb 1
S= = = 0.1 sec
20 − 10Mbps 10
55. A sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames
are of size 1000 bytes and the transmission rate at the sender is 80 Kbps (1Kbps = 1000
bits/second). Size of an acknowledgement is 100 bytes and the transmission rate at the
receiver is 8 Kbps. The one-way propagation delay is 100 milliseconds.
Key: (2500)
Tp=100ms
Tx
n=
Tx + Tack + 2Tp
L 1000 Bytes
( msg ) Tx = = = 100ms
BS 10 × 103 BPS
L A 100 Bytes
( Ack ) TA = = =100ms
BR 1 ×103 BPS
Tp = 100ms
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-01 www.gateforum.com
Tn 100ms 1
∴ Channel Utilization = = =
Tn + Tack + 2Tp 100ms + 100ms + 200ms 4
1
∴ Throughput = η × B = ×10×103 = 2.5 Kbps ( or 2500 Bps )
4
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
General Aptitude
Q. No. 1 – 5 Carry One Mark Each
2. Nobody knows how the Indian cricket team is going to cope with the difficult and
seamer-friendly wickets in Australia.
Choose the option which is closest in meaning to the underlined phase in the above
sentence.
(A) put up with (B) put in with (C) put down to (D) put up against
Key: (A)
Key: (D)
5. In a quadratic function, the value of the product of the roots ( α, β ) is 4. Find the value of
α n + βn
α − n + β− n
(A) n 4 (B) 4 n (C) 22n −1 (D) 4 n −1
Key: (B)
Exp: Given αβ = 4
α n + βn α n + βn
=
α − n + β− n 1
+ n
1
n
α β
=
(α n
+ βn ) α n β n
(α n
+ βn )
= (αβ) n = 4n
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
6. Among 150 faculty members in an institute, 55 are connected with each other through
Facebook and 85 are connected through WhatsApp. 30 faculty members do not have
Facebook or WhatsApp accounts. The number of faculty members connected only
through Facebook accounts is ______.
(A) 35 (B) 45 (C) 65 (D) 90
Key: (A)
Exp: F → Facebook, W → WhatsApp, E → Total faculties
given
E, n(E) = 150
(
)
n(E) = 150, n F ∪ W = 30
55 85
n ( F ∪ W ) = n(E) − N ( F ∪ W ) = 150 − 30
n ( F ∪ W ) = 120
n ( f ∪ w ) = n ( f ) + [ n(w) − n(F∩ w ] F F∩ w W
n (F ∩ w )
120 = n(F) + 85 n(F) = 35 n(w) = 60
= 20
n(F) = 120 − 85 = 35
55 = n(F) + n ( F ∩ W )
= 30
n ( F ∩ w ) = 55 − n(F) = 55 − 35 = 20
n(w) = 85 − 20 = 65
(F ∪ W)
7. Computers were invented for performing only high-end useful computations. However, it
is no understatement that they have taken over our world today. The internet, for
example, is ubiquitous. Many believe that the internet itself is an unintended consequence
of the original invention with the advent of mobile computing on our phones, a whole
new dimension is now enabled. One is left wondering if all these developments are good
or more importantly, required.
Which of the statement(s) below is/are logically valid and can be inferred from the above
paragraph?
(i) The author believes that computers are not good for us
(ii) Mobile computers and the internet are both intended inventions
(A) (i) (B) (ii) only
(C) both (i) and (ii) (D) neither (i) nor (ii)
Key: (D)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (D)
9. In a 2 × 4 rectangle grid shown below, each cell is a rectangle. How many rectangles can
be observed in the grid?
(A) 21 (B) 27
(C) 30 (D) 36
Key: (C)
Exp: 1: (AEOK)
2: (AEJF), (FJOK) A B C D E
4: (ABLK), (BCML), (CDNM), (DEON)
2: ACMK, ADNK 2 : ECMD, EBLO 2 : ACHF, ADIF
F G H I J
2: ECHJ, EBGJ 2 : FHMK,FINK 2 : JHMD, JGLO
1: BDNL 2 : BDIG,GINL
8: ABGF, BCHJ, CDIH, EDI, FGLK, GHML, HINM K L M N O
Total = 1+2+4+2+2+2+2+2+2+1+2+8=30
25
f (x)
10. 2
1.5
1
0.5
0
0 2 3 X4
−4 −3 −2 −1 1
0.5
1
1.5
−2
25
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (4)
2. Let f (x) be a polynomial and g(x) = f ‘(x) be its derivative. If the degree of (f (x) + f (−x))
is 10, then the degree of (g(x) − g(−x)) is __________.
Key: (9)
Exp: If f(x) is polynomial of degree n,
then g(x) = f ′(x) is polynomial of degree n,
⇒ f (x) + f (− x) is polynomial of degree n,
But given f (x) + f ( − x) is polynomial of degree 10.
∴ n = 10.
⇒ g(x) is polynomial of 9.
∴ g(x) − g(− x) is polynomial of degree 9.
3. The minimum number of colours that is sufficient to vertex-colour any planar graph is
_________.
Key: (4)
Exp: Any planar graph is four-colourable.
(A) I, II and III are true (B) Only II and III are true
(C) Only III is true (D) None of them is true
Key: (C)
Exp: I is not correct
x+y+z=1
x+y+z=0
Has no solution, when no of equations is less than no of variables.
II is not correct
Eg:
x − 2y = 2
2x + 8y = 16
x+y=5
Has a solution (x=4, y=1).
III is correct
Eg:
x+y = 4,
x+2y=0
Has solutions (x=6, y=-2)
5. Suppose that a shop has an equal number of LED bulbs of two different types. The
probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7,
and given that it is of Type 2 is 0.4. The probability that an LED bulb chosen uniformly at
random lasts more than 100 hours is __________.
Key: (0.55)
Exp: E1 –event of selecting type-I bulb
E2-event of selecting type-II bulb
A- Event of selecting a bulb lasts more than 100 hours
Given P ( E1 ) = 0.5, P ( E 2 ) = 0.5
P ( A / E1 ) = 0.7, P ( A / E 2 ) = 0.4
Required probability,
P(A) = P(E1 )P(A / E1 ) + P(E 2 ) P ( A / E 2 )
= 0.5 × 0.7 + 0.5 × 0.4
= 0.55
6. Suppose that the eigen values of matrix A are 1, 2, 4. The determinant of (A−1) T
is
_________.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (0.125)
Exp: Given that 1,2,4 are eigen values of A>
1 1
⇒ A = 8 and A −1 = =
A 8
+ T 1
Now, ( A −1 ) = A −1 = A −1 = = 0.125
8
7. Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and
B are integers represented in 2’s complement form. If the decimal value of A is one, the
decimal value of B that leads to the longest latency for the sum to stabilize is
__________.
Key: (-1)
8. Let, x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0 where x1, x2, x3, x4 are Boolean variables, and ⊕ is the XOR
operator.
Which one of the following must always be TRUE?
(A) x1 x 2 x 3 x 4 = 0 (B) x1 x 3 + x 2 = 0
(C) x1 ⊕ x 3 = x 2 ⊕ x 4 (D) x1 + x 2 + x 3 + x 4 = 0
Key: (C)
9. Let X be the number of distinct 16-bit integers in 2’s complement representation. Let Y
be the number of distinct 16-bit integers in sign magnitude representation.
Then X − Y is __________.
Key: (1)
Exp:
X = − 216−1 to + 216−1 − 1
Y = − 216−1 − 1 to + 216−1 − 1
So [ X − Y =1]
10. A processor has 40 distinct instructions and 24 general purpose registers. A 32-bit
instruction word has an opcode, two register operands and an immediate operand. The
number of bits available for the immediate operand field is _________.
Key: (16)
6 bit 5 5 16
OP Code R.O R.O I.O
32 bit
11. Breadth First Search (BFS) is started on a binary tree beginning from the root vertex.
There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS
traversal, then the maximum possible value of n is _________.
Key: (31)
Exp:
void main(){
int i=5, j=10;
f(&i, j);
printf("%d", i+j);
}
Key: (30)
Exp: i’s address and j’s value are passed to the function of f. f modifies i value to 20. j value
remains same (as its value is passed not the reference).
∴ i + j = 30 will be printed
13. Assume that the algorithms considered here sort the input sequences in ascending order. If
the input is already in ascending order, which of the following are TRUE?
I. Quick sort runs in Θ(n2) time
II. Bubble sort runs in Θ(n2) time
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (D)
Exp: As input is already sorted quick sort runs in θ(n 2 ) & insertion sort runs in θ(n).
14. The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
(A) Greedy paradigm
(B) Divide-and-Conquer paradigm.
(C) Dynamic Programming paradigm.
(D) Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm
Key: (C)
Exp: Floyd - warshall algorithm follows dynamic programming paradigm.
15. N items are stored in a sorted doubly linked list. For a delete operation, a pointer is
provided to the record to be deleted. For a decrease-key operation, a pointer is provided to
the record on which the operation is to be performed.
An algorithm performs the following operations on the list in this order: Θ(N) delete,
O(log N) insert, O(log N) find, and Θ(N) decrease-key. What is the time complexity of
all these operations put together?
(A) O(log2N) (B)O(N) (C)O(N2) (D) Θ(N2 log N)
Key: (C)
16. The number of states in the minimum sized DFA that accepts the language defined by the
regular expression is _________.
(0 + 1)∗(0 + 1)(0 + 1)∗
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (C)
Exp: L1 = {a n b n / n ≥ 1} CFL but not regular
L 2 = (ab) + regular
18. Consider the following types of languages: L1: Regular, L2: Context-free, L3: Recursive,
L4: Recursively enumerable. Which of the following is/are TRUE?
I. L3 ∪ L 4 is recursively enumerable
II. L2 ∪ L3 is recursive
III. L*1 ∩ L2 is context-free
IV. L1 ∪ L2 is context-free
(A) I only (B) I and III only (C) I and IV only (D) I, II and III only
Key: (D)
Exp: L1 ∪ L2 is recursive but not CFL as CFL’s are not closed under complementation.
Key: (B)
20. In which one of the following page replacement algorithms it is possible for the page fault
rate to increase even when the number of allocated frames increases?
(A) LRU (Least Recently Used)
(B) OPT (Optimal Page Replacement)
(C) MRU (Most Recently Used)
(D) FIFO (First In First Out)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (D)
Exp: If page fault rate increases even when the number of allocated frames increases, then that
situation is called “Belady’s Anamoly”. It was happening with only FIFO among the
given options.
22. Suppose a database schedule S involves transactions T1, . . . , Tn. Construct the
precedence graph of S with vertices representing the transactions and edges representing
the conflicts. If S is serializable, which one of the following orderings of the vertices of
the precedence graph is guaranteed to yield a serial schedule?
(A) Topological order (B) Depth-first order
(C) Breadth-first order (D) Ascending order of transaction indices
Key: (A)
23. Anarkali digitally signs a message and sends it to Salim. Verification of the signature by
Salim requires
(A) Anarkali’s public key (B) Salim’s public key
(C) Salim’s private key (D) Anarkali’s private key
Key: (A)
Exp: In digital signature generation process using senders private key we can encrypt the
message and in verification process using senders public key we can decrypt the message.
24. In an Ethernet local area network, which one of the following statements is TRUE?
(A) A station stops to sense the channel once it starts transmitting a frame.
(B) The purpose of the jamming signal is to pad the frames that are smaller than the
minimum frame size.
(C) A station continues to transmit the packet even after the collision is detected.
(D) The exponential backoff mechanism reduces the probability of collision on
retransmissions.
Key: (D)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
25. Identify the correct sequence in which the following packets are transmitted on the
network by a host when a browser requests a webpage from a remote server, assuming
that the host has just been restarted.
(A) HTTP GET request, DNS query, TCP SYN
(B) DNS query, HTTP GET request, TCP SYN
(C) DNS query, TCP SYN, HTTP GET request
(D) TCP SYN, DNS query, HTTP GET request
Key: (C)
Exp: When a browser requests a webpage from a remote server then that requests (URL
address) will be mapped to IP address using DNS, then TCP synchronization takes place
after that HTTP verify whether it is existed in the web server or not.
27. Which one of the following well-formed formulae in predicate calculus is NOT valid?
(A) (∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬ p(x) ∨ ∀x q(x))
(B) (∃x p(x) ∨ ∃x q(x)) ⇒ ∃x ( p(x) ∨ q(x))
(C) ∃x ( p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))
(D) ∀x ( p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))
Key: (D)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
29. The value of the expression 1399(mod 17), in the range 0 to 16, is __________.
Key: (4)
30. Suppose the functions F and G can be computed in 5 and 3 nanoseconds by functional
units UF and UG, respectively. Given two instances of UF and two instances of UG, it is
required to implement the computation F (G (Xi)) for 1 ≤ i ≤ 10. Ignoring all other delays,
the minimum time required to complete this computation is _________ nanoseconds.
Key: (28)
31. Consider a processor with 64 registers and an instruction set of size twelve. Each
instruction has five distinct fields, namely, opcode, two source register identifiers, one
destination register identifier, and a twelve-bit immediate value. Each instruction must be
stored in memory in a byte-aligned fashion. If a program has 100 instructions, the amount
of memory (in bytes) consumed by the program text is _________.
Key: (500)
32. The width of the physical address on a machine is 40 bits. The width of the tag field in a
512 KB 8-way set associative cache is _________ bits.
Key: (24)
40 bit
33. Consider a 3 GHz (gigahertz) processor with a three-stage pipeline and stage latencies τ1,
τ2, and τ3 such that τ1 = 3τ2/4 = 2τ3. If the longest pipeline stage is split into two pipeline
stages of equal latency, the new frequency is ________ GHz, ignoring delays in the
pipeline registers.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (4)
4 2 2
z1 z1 z1 / 2 z1 z1 z1 z1 / 2
3 3 3
4
t p = z1 t p = z1
3
34. A complete binary min-heap is made by including each integer in [1, 1023] exactly once.
The depth of a node in the heap is the length of the path from the root of the heap to that
node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is
_________.
Key: (8)
Exp: nth smallest element will be present within ‘n’ levels of min heap
36. Consider the following New-order strategy for traversing a binary tree:
• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish
expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:
(A) + - 1 6 7 * 2 ˆ 5 - 3 4 * (B) - + 1 * 6 7 ˆ 2 - 5 * 3 4
(C) - + 1 * 7 6 ˆ 2 - 5 * 4 3 (D) 1 7 6 * + 2 5 4 3 * - ˆ -
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
Key: (C)
Exp: Given is the post fix expression the expression tree given below.
∧ +
* 1
− 2
6 7
* 5
3 4
3 5 2 6 4
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
main
return1
38. Let A1, A2, A3, and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5,
respectively. The minimum number of scalar multiplications required to find the product
A1 A2 A3A4 using the basic matrix multiplication method is __________.
Key: (1500)
2m C m
Exp: No. of ways of multiplying the chain of matrices =
m +1
Where m= no. of multiplications (not matrices)
6
C3
⇒ =5
3 +1
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
( A × ( B × ( C × D ))) , (A × (( B × C ) × D )
1750 1500
(( A × ( B × C ) × D )) ((( A × B ) × C ) × D )
2000
(( A × B ) × ( C × D ))
3000
39. The given diagram shows the flowchart for a recursive function A(n). Assume that all
statements, except for the recursive calls, have O(1) time complexity. If the worst case
time complexity of this function is O(nα ), then the least possible value (accurate up to
two decimal positions) of α is _________.
Start
A (n 2)
Return A (n 2) A (n 2) A (n 2) Return
A (n 2)
Return A (n 2) Return
Key: (2.32)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
40. The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty
binary search tree, such that the resulting tree has height 6, is _________.
Note: The height of a tree with a single node is 0.
Key: (64)
Exp: 64, 26 = 64
41. In an adjacency list representation of an undirected simple graph G = (V, E ), each edge
(u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency
list of v. These are called twins of each other. A twin pointer is a pointer from an
adjacency list entry to its twin. If |E | = m and |V | = n, and the memory size is not a
constraint, what is the time complexity of the most efficient algorithm to set the twin
pointer in each entry in each adjacency list?
(A) Θ ( n 2 ) (B) Θ ( n + m ) (C) Θ ( m 2 ) (D) Θ ( n 4 )
Key: (B)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
∴ L1 = CFL
For L2, we can’t build PDA [a’s & b’s should be equal & C′ should be double of that
count]
45. Which one of the following grammars is free from left recursion?
(A) S → AB (B) S → Ab | Bb |c
A → Aa |b A → Bd |ε
B→c B→e
(C) S → Aa |B (D) S → Aa | Bb |c
A → Bb | Sc |ε A → Bd |ε
B → Ae |ε
Key: (B)
Exp (C) & (D) are having indirect left recursion.
46. A student wrote two context-free grammars G1 and G2 for generating a single C-like
array declaration. The dimension of the array is at least one. For example,
int a[10][3];
The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.
Grammar G1 Grammar G2
D → int L; D → int L;
L → id [E L → id E
E → num] E → E [num]
E → num] [E E → [num]
Which of the grammars correctly generate the declaration mentioned above?
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
47. Consider the following processes, with the arrival time and the length of the CPU burst
given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-
time first.
Process Arrival Time Burst Time
P1 0 10
P2 3 6
P3 7 1
P4 8 3
P1 P2 P3 P4 P4 P1
0 3 7 8 10 13 20
P1 − 7 P1 − 7 P1 − 7 P1 − 7
P2 − 6 P2 − 2 P2 − 2 P4 − 3
P3 − 1 P4 − 3
The shared variable turn is initialized to zero. Which one of the following is TRUE?
(A) This is a correct two-process
two synchronization solution.
(B) This solution violates mutual exclusion requirement.
(C) This solution violates progress requirement.
(D) This solution violates bounded wait requirement.
Key: (C)
Exp: The given solution for two process synchronization using “Turn” variable,
v satisfies the
only mutual exclusion
ion and bounded waiting but progess
prog is violated.
The smallest cache size required to ensure an average read latency of less than 6 ms is
_________ MB.
Key: (30)
51. Consider the following database schedule with two transactions, T1 and T2.
S = r2(X ); r1(X ); r2(Y ); w1(X ); r1(Y ); w2(X ); a1; a2
where ri(Z) denotes a read operation by transaction Ti on a variable Z, wi(Z) denotes a
write operation byy Ti on a variable Z and ai denotes an abort by transaction Ti.
Which one of the following statements about the above schedule is TRUE?
ICP–Intensive
Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All
TarGATE India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part
part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
(A) S is non-recoverable
(B) S is recoverable, but has a cascading abort
(C) S does not have a cascading abort
(D) S is strict
Key: (C)
Exp: No transaction is reading the data item written by some other transaction. So the given
schedule is cascadeless.
53. A network has a data transmission bandwidth of 20 × 106 bits per second. It uses
CSMA/CD in the MAC layer. The maximum signal propagation time from one node to
another node is 40 microseconds. The minimum size of a frame in the network is
__________ bytes.
Key: (200)
Exp: B = 2× 106 bps
Tp = 40 µs
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2016-PAPER-02 www.gateforum.com
L= ?
L = 2 × Tp × B ⇒ L = 2 × 40 × 10−6 × 20 × 106
= 1600 bits (or) 200 bytes
L = 200 bytes
54. For the IEEE 802.11 MAC protocol for wireless communication, which of the following
statements is/are TRUE?
I. At least three non-overlapping channels are available for transmissions.
II. The RTS-CTS mechanism is used for collision detection.
III. Unicast frames are ACKed.
(A) All I, II, and III (B) I and III only (C) II and III only (D) II only
Key: (B)
Exp: In collision avoidance, we use RTS-CTS mechanism but not in collision detection, only
statement II is false.
55. Consider a 128 × 103 bits/second satellite communication link with one way propagation
delay of 150 milliseconds. Selective retransmission (repeat) protocol is used on this link
to send data with a frame size of 1 kilobyte. Neglect the transmission time of
acknowledgement. The minimum number of bits required for the sequence number field
to achieve 100% utilization is _________.
Key: (4)
Exp: B=128 kbps
Tp = 150ms
L = 1KB
w
η = 100% ⇒ 1 =
1 + 2a
L 8 × 103
Tx = = = 62.5ms
B 128 × 103
Tp 150ms
a= = = 2.4
Tx 62.5ms
2n 2n
⇒ w = 1 + 2a ⇒ = 1 + 2(2.4) ⇒ = 5.8 ⇒ 2n = 11.65
2 2
⇒ 2n = 11.6 ≈ 12 ≈ 24
n=4
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
1. Let X be a Gaussian random variable mean 0 and variance σ 2 .Let Y=max(X, 0) where max
(a,b) is the maximum of a and b. The median of Y is ____________.
Key: (0)
Exp: ‘X’ is Gaussian random variable
⇒ X ∼ N ( 0, σ 2 ) for −∞ < x < ∞
2. Consider the Karnaugh map given below, where x represents “don’t care” and blank
represents 0.
ba
dc
00 01 11 10
00 x x
01 1 x
11 1 1
10 x x
Assume for all inputs (a, b, c, d) the respective complements a, b,c,d are also available. The ( )
above logic is implemented 2-input NOR gates only. The minimum number of gates required
is ____________.
Key: (1)
Exp:
ba
dc 00 01 11 10
00 x x
01 1 x
11 1 1
10 x x
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
P → xQRS
Q → yz z
R→w∈
S→ y
*
7. Consider the language L given by the regular expression ( a + b ) b ( a+b ) over the alphabet
{a, b}. The smallest number of states needed in a deterministic finite-state automation (DFA)
accepting L is ___________.
Key: (4)
Exp: The regular expression can be described as “All strings over {a, b} ending with “ba” or “bb”.
The minimal DFA accepting L is having 4 states:
a b
b b
a a
8. Consider a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4
memory accesses per instruction on average. For this application, the miss rate of L1 cache
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
0.1, the L2 cache experiences, on average, 7 misses per 1000 instructions. The miss rate of L2
expressed correct to two decimal places is ___________.
Key: (0.05)
Number of memory access
Exp: = 1.4 × 1000 = 1,400
in 1000 instructions
7
∴ Miss Rate = = 0.05
1400 × 0.1
9. Consider the following CPU processes with arrival times (in milliseconds) and length of CPU
burst (in milliseconds) as given below:
Process Arrival time Burst time
P1 0 7
P2 3 3
P3 5 5
P4 6 2
If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the
processes., then the average waiting time across all processes is ________ milliseconds.
Key: (3)
Exp:
PID AT BT CT TAT WT
P1 0 7 12 12 5
P2 3 3 6 3 0
P3 5 5 17 12 7
P4 6 2 8 2 0
Gantt chart:
P1 P2 P2 P4 P1 P3
0 3 5 6 8 12 17
P1 − 7 P1 − 4 P1 − 4 P1 − 4 P1 − 4 P3 − 5
P2 − 3 P2 − 1 P3 − 5 P3 − 5
P3 − 5 P4 − 2
P1 P2 P4 P1 P3
0 3 8 6 12 17
5 + 0 + 7 + 0 12
∴ Average waiting time = = = 3ms
4 4
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
n
11. Let c1 ........c n be scalars, not all zero, such that ∑c a
i=l
i i = 0 where a i are column vectors in
Key: (B)
Exp: While loop in Join Procedure moves the pointer ‘p’ to the last node of the list “n”. And at the
last statement, we are initializing the next of the last node of list n to start of list “m”.
But in some cases it may dereference to null pointer.
13. The n-bit fixed-point representation of an unsigned real number real X uses f bits for the
fraction part. Let i = n –f. The range of decimal values for X in this representation is
(A) 2 − f to 2i (B) 2 − f to ( 2i − 2 − f ) (C) 0 to 2i (D) 0 to ( 2i − 2 − f )
Key: (D)
i=n–f . f
Exp:
Max value = 111.....1( i times ) .111........1( f times )
1 1 1 i 2f − 1
= 2i − 1 + + 2 + ... + f =2 − 1 + = 2i − 2 − f
2 2 2 2f
∴ 0 to ( 2i − 2− f )
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
char grade;
int cnumber;
};
struct data student;
The base address of student is available in register R1. The field student.grade can be
accessed efficiently using
(A) Post-increment addressing mode. (R1)+
(B) Pre-decrement addressing mode, -(R1)
(C) Register direct addressing mode, R1
(D) Index addressing mode, X(R1), where X is an offset represented in 2’s complement 16-
bit representation.
Key: (D)
Exp: Direct access is possible with only index addressing mode.
16. Consider a TCP client and a TCP server running on two different machines. After completing
data transfer, the TCP client calls close to terminate the connectional and a FIN segment is
sent to the TCP server. Server-side TCP responds by sending an ACK which is received by
the client-side TCP. As per the TCP connections state diagram (RFC 793), in which state does
the client-side TCP connection wait for the FIN from the sever-side TCP?
(A) LAST-ACK (B) TIME-WAIT (C) FIN-WAIT-1 (D) FIN-WAIT-2
Key: (D)
Exp: Client* Server*
*or vice-versa, though requests typically originate at clients.
5 Established 5 Established
The connection is open. Received acknowledgement.2
Data moves both directions. The connection is open.
Data moves both directions.
6 Fin − Wait.1
8 Close − wait
Sent close − request.a
Received close − request.a
Awaiting acknowledgement.a
Sent acknowledgement.a
Awaiting close − request.b
When finished sending data,
Will send close − request.b
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
7 Fin − wait.2
Received acknowledgement.a
Still awaiting close − request.b 9 Last − Ack
Or Sent close − request.b
10 closing Awaiting acknowledgement.b
Received close − request.b
Sent acknowledgement.b
Still awating acknowledgement.a
11 Time − wait
Received acknowledgement.a
Received close − request.b
Sent acknowledgement.b
Allowing time for delivery
Of acknowledgement.b
1 closed 2 Listening
A “fictional” state; Awaiting connection request.
There is no connection.
17. Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start
symbol.
S → abScT abcT
T → bT b
Which one of the following represents the language generated by the above grammar ?
(A) {( ab ) ( cb ) n ≥ 1}
n n
(B) {( ab ) cb cb ...cb }
n m1 m2 mn
n, m1 ,m 2 ,...m n ≥ 1
(C) {( ab ) (cb )n m n
m, n ≥ 1}
(D) {( ab ) ( cb ) n m
m, n ≥ 1}
n
Key: (B)
Exp: The given Grammar over Σ = {a, b, c} with S as the start symbol is
S → abScT | abcT
T→ bT | b
The minimum length string generated by the grammar is 1:
S→abcT→abcb ; hence all variable greater than 1.
Other cases
S → abScT→ ab abScT cT → ab ab abScT cT cT →........→ (ab)n (cT)n .
Here T can generate any number of b’s starting with single b.
Hence The language is L = {(ab)n cb m1 cb m2 cb m3 cb m4 ...............cb mn | m1,m2,m3,m4……mn n
≥1}
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
18. Consider the first-order logic sentence F :∀ z ( ∃yR ( x, y ) ) . Assuming non-empty logical
domains, which of the sentences below are implied by F?
I. ∃y ( ∃xR ( x, y ) ) II. ∃y ( ∀xR ( x, y ) )
∀x∃yR ( x, y ) ⇒ ∃y∀x R ( x, y )
¬∃x ( ∀y¬R ( x, y ) ) ⇔ ∀x∃y R ( x, y )
19. When two 8-bit numbers A 7 ....A 0 and B7 .....B0 in 2’s complement representation (with A0
and B0 as the least significant bits ) are added using a ripple-carry adder, the sum bits
obtained are S7….S0 and the carry bits are C7….C0. An overflow is said to have occurred if
(A) the carry bit C7 is 1 (B) all the carry bits (C7….C0) are 1
(C) (A 7 B7 .S7 + A 7 .B7 .S7 ) is 1 (D) (A 0 .B0 .S0 + A 0 .B0 .S0 ) is 1
Key: (C)
Exp: Overflow flag indicates an over flow condition for a signed operation. Some points to
remember in a signed operation:
* MSB is always reserved to indicate sign of the number.
* Negative numbers are represented in 2’s – complement.
* An overflow results in invalid operation.
2's complement overflow rules:
* If the sum of two positive numbers yields a negative result, the sum has- overflowed.
* If the sum of two negative number yields a positive result, the sum has overflowed.
* Otherwise, the sum has not overflowed.
Overflow for signed numbers occurs when the carry-in into the MSB (most significant bit) is
not equal to carry-out. Conveniently, an XOR-operation on these two bits can quickly
determine if an overflow condition exists.
Therefore, ( ( A .B )) ⊕ S
7 7 7 = A 7 .B7 .S7 + A7 .B7 .S7 = 1) has overflowed.
20. Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName).
An instance of the schema EMP and a SQL query on it are given below.
EMP
EmpId EmpName DeptName
1. XYA AA
2. XYB AA
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
3. XYC AA
4. XYD AA
5. XYE AB
6. XYF AB
7. XYG AB
8. XYH AC
9. XYI AC
10 XYJ AC
11. XYK AD
12. XYL AD
13. XYM AE
SELECT AVG(EC.Num)
FROM EC
WHERE(DeptName, Num)IN
(SELECTDeptName,COUNT(EmpId)AS
EC( DeptName, Num)
FROMEMP
GROUPBYDeptName)
13
Avg ( NUM ) = = 2.6
5
21. The following functional dependencies hold true for the relational schema R{V,W,X,Y,Z}:
V→W
VW → X
Y → VX
Y→Z
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
Which of the following is irreducible equivalent for this set of functional dependencies ?
(A) V → W (B) V → W (C) V → W (D) V → W
V→X W→X V→X W→X
Y→V Y→V Y→V Y→V
Y→Z Y→Z Y→X Y→X
Y→Z Y→Z
Key: (A)
Exp: V → W, VW → X, Y → V, Y → X,Y → Z ( W is extraneous )
V → W, V → X, Y → V, Y → X, Y → Z
∴ Y → X is redundant
∴{V → W, V → X, Y → V, Y → Z}
22. Consider the following functions from positive integers to real numbers:
100
10, n , n,log 2 n,
n
The CORRECT arrangement of the above functions in increasing order of asymptotic
complexity is:
100 100
(A) log 2 n, ,10, n , n (B) ,10,log 2 n , n ,n
n n
100 100
(C) 10, , n ,log 2 n, n (D) , log 2 n ,10, n, n
n n
Key: (B)
100
Exp: < 10 < log 2 n < n , n
n
23. Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.
Key: (18)
Exp: A tree with 10 vertices has 9 edges.
As ∑ d ( vi ) = 2 E
⇒ ∑ d ( vi ) = 2 × 9 = 18
24. Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of
T are :
Note: The height of a tree with a single node is 0.
(A) 4 and 15 respectively
(B) 3 and 14 respectively
(C) 4 and 14 respectively
(D) 3 and 15 respectively
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
Key: (B)
Exp:
min max
height height
15nodes total
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01
GATE www.gateforum.com
(C) is wrong, because dangling pointer is nothing but the pointer which is pointing to non-
existing memory (deallocated or deleted memory) which is not happening here.
(D) is the answer. When you are calling malloc second time, new location is assigned to x
and previous memory location is lost and now we don’t have no reference to th
that location
resulting in memory leak.
Initially, both Q0 and Q1 are set to 1 ( before the 1st clock cycle). The outputs
(A) Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 00 respectively
(B) Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 01 respectively
(C) Q1Q0 after the 3rd cycle are 00 and after the 4th cycle are 11 respectively
(D) Q1Q0 after the 3rd cycle are 01 and after the 4th cycle are 01 respectively
Key: (B)
Exp:
CLK Q1 Q0
0 1 1
1 0 1
2 1 0
3 1 1
4 0 1
27. The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is
______________.
Key: (271)
Exp: D3 = {integers between 1 to 500 divisible by 3}
28. Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and
unconditional branch instructions use PC- relative addressing mode with Offset specified in
bytes to the target location of the branch instruction. Further the Offset is always with respect
to the address of the next instruction in the program sequence. Consider the following
instruction sequence.
Instr. No. Instruction
i: add R2, R3, R4
i +1: sub R5, R6, R7
i + 2: cmp R1, R9, R10
i+3 beq R1, Offset
If the target of the branch instruction is i, then the decimal value of the Offset is __________.
Key: (-16)
Exp: I1 0−3
I2 4−7
I3 8 − 11
I4 12 − 15
16 −
I4 is the branch instruction & I1 is the target.
0 = 16+ relative value
∴ relative value = -16
}
return val ;
}
Invocations of foo (3) and bar (3) will result in:
(A) Return of 6 and 6 respectively.
(B) Infinite loop and abnormal termination respectively.
(C) Abnormal termination and infinite loop respectively.
(D) Both terminating abnormally
Key: (B)
Exp: Foo (3) calls foo (3) which in turn calls foo(3). This goes on infinite number of times which
causes memory overflow and causes abnormal termination.
Bar(3) → bar (2) → bar (1) → bar (0) (return 0) from here onwards bar (1) will call bar (0)
and bar (0) will return 0 to bar (1) & this goes on forever without causing memory overflow.
30. In a RSA cryptosystem a participant A uses two prime numbers p = 13 and q =17 to generate
her public and private keys. If the public key of A is 35. Then the private key of A is
__________.
Key: (11)
Exp:
Given Data As per RSA Algorithm
p=13 Step1:Calculate n = p × q = 13 × 17 = 221
31. Let A be an array of 31 numbers consisting of sequence of 0’s followed by a sequence of 1’s.
The problem is to find the smallest index i that A[i] is 1 by probing the minimum numbers of
locations in A. The worst case number of probes performed by an optimal algorithm is
_____________.
Key: (5)
Exp: In the given array the elements are 0’s followed by 1’s , which means array is already sorted.
low + high
So we can apply binary search. At each stage, we compare A .
2
[Assuming ‘A’ is an array of 31 elements] with ‘1’ and if it is 1 we check the left part
recursively and if it is ‘0’ we check the right part of the array recursively, which takes log 2 31
comparisons in the worst case.
where S is the start variable, then which one of the following is not generated by G?
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
x 7 − 2x 5 + 1
33. The value of lim
x →1 x 3 − 3x 2 + 2
34. Instructions execution in a processor is divided into 5 stages. Instruction Fetch (IF),
Instruction Decode (ID) , Operand Fetch (OF), Execute (EX), and Write Back (WB), These
stages take 5,4,20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of
the processor requires buffering between each pair of consecutive stages with a delay of 2ns.
Two pipelined implementations of the processor are contemplated.
(i) a naïve pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage id divided into stages OF1 and OF2
with execution times of 12 ns and 8 ns respectively.
The speedup (correct to two decimals places) achieved by EP over NP in executing 20
independent instructions with no hazards is ________________.
Key: (1.508)
Exp: Given,
For Navie pipeline (NP)
Number of stages (k) = 5
Tp = max (stage delay + buffer delay)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
35. Consider a database that has the relation schemas EMP(EmpId, EmpName, DepId). And
DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation
EMP. Consider the following queries on the database expressed in tuple relational calculus.
(I) {t ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∀v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
36. Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of
allocated frames increases. Now consider the following statements:
S1: Random page replacement algorithm (where a page chosen at random is replaced)
suffers from Belady’s anomaly
S2: LRU page replacement algorithm suffers from Belady’s anomaly
Which of the following is CORRECT ?
(A) S1 is true, S2 is true (B) S1 is true, S2 is false
(C) S1 is false , S2 is true (D) S1 is false, S2 is false
Key: (B)
Exp: Statement 1 is “TRUE”. Because there can be a case when page selected to be replaced is by
FIFO policy.
Statement 2 is “FALSE”. Because LRU page replacement algorithm does not suffers
from Belady’s Anomaly. Only FIFO page replacement algorithm suffers from Belady’s
Anomaly.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
Let L1 = {a n b n c m m, n ≥ 0} and L 2 = {a m b n c n m, n ≥ 0}
Which of the following are context-free languages ?
I. L1 ∪ L 2 II. L1 ∩ L 2
(A) I only (B) II only (C) I and II (D) Neither I nor II
Key: (A)
Exp: The language given over alphabets Σ = {a, b, c} as L1 ={anbncm|n,m≥0} and L2= {
ambncn|n,m≥0}.
L1 ∪ L2 = { anbmck|n=m or m =k , n,m≥0}is a context free language. The context free grammar
is:
S→AB|CD
A→aAb|ϵ
B→cB|ϵ
C→aC|ϵ
D→bSc|ϵ
L1 ∩ L2 ={ anbmck|n=m and m =k , n,m≥0}or { anbncn| n ≥0}is a non context free language.
40. Consider a 2-way set associative cache with 256 blocks and uses LRU replacement, Initially
the cache is empty. Conflict misses are those misses which occur due the contention of
multiple blocks for the same cache set. Compulsory misses occur due to first time access to
the block. The following sequence of accesses to memory blocks.
(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129)
is repeated 10 times. The number of conflict misses experienced by the cache is ___________.
Key: (76)
Exp: A miss is not considered a conflict miss if the block is accessed for the first time.
1st round: (2+2) misses
2nd round: (4+4) misses
∴ Total = 4 + ( 8 × 9 ) = 76 conflict misses
41. Let u and v be two vectors in R2 whose Euclidean norms satisfy u = 2 v . What is the value
of α such that w = u + αv bisects the angle between u and v ?
(A) 2 (B) 1/2 (C) 1 (D) -1/2
Key: (A)
2 0
Exp: Let u = and v =
0 1
2
⇒ u = z. v and w =
α
Now cos ( u, w ) = cos ( v, w )
4 α
⇒ = ⇒α=2
2
( 2) α +4 (1) α2 + 4
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
e2 e3
if if
e4 e4
e5 e5 e5 e5
43. In a database system, unique time stamps are assigned to each transaction using Lamport’s
logical clock . Let TS(T1) and TS(T2) be the timestamps of transactions T1 and T2
respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting
lock on the same resource R. The following algorithm is used to prevent deadlocks in the
database system assuming that a killed transaction is restarted with the same timestamp.
if TS(T2 ) < TS ( T1 ) then
T1 is killed
elseT2 waits.
Assume any transactions that is not killed terminates eventually. Which of the following is
TRUE about the database system that uses the above algorithm to prevent deadlocks?
(A) The database system is both deadlock-free and starvation- free.
(B) The database system is deadlock- free, but not starvation-free.
(C) The database system is starvation-free but not deadlock- free.
(D) The database system is neither deadlock- free nor starvation-free.
Key: (A)
Exp: Elder kills younger and youngers waits on elder. So both are not waiting for each other. Hence
no deadlock and there won’t be any starvation as well because the transaction who got killed
will be starting with same time stamp.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
44. Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total
functional from A* to B*. We say f is computable if there exists a Turning machine M which
given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language
{x #f (x) x ∈ A } .Which of the following statements is true:
*
*
45. Consider the expression ( a − 1) ( ( (b + c ) / 3) + d) ) . Let X be the minimum number of
registers required by an optimal code generation (without any register spill) algorithm for a
load/store architecture in which (i) only loads and store instructions can have memory
operands and (ii) arithmetic instructions can have only register or immediate operands. The
value of X is _________.
Key: (2)
Exp: 2
*
− 1 + 1
a 1 1 1 d
1 0 0
+
1 3
0
b c
1 0
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
46. Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in
E are positive and distinct. Consider the following statements:
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(A) (I) only (B) (II) only
(C) Both (I) and (II) (D) Neither (I) nor (II)
Key: (A)
Exp: A 1 B
2 3 5
C 4 D
Shortest path from B to C are two B-A-C and B-C both of weight '3'
47. A multithreaded program P executes with x number of threads and uses y number of locks for
ensuring mutual exclusion while operating on shared memory locations. All locks in the
program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l
without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes
available. The minimum value of x and the minimum value of y together for which execution
of P can result in a deadlock are:
(A) x = 1, y = 2 (B) x =2, y=1 (C) x = 2,y=2 (D) x = 1, y = 1
Key: (C)
Exp: As per given question, there 'x' number of threads and 'y' number of locks for ensuring mutual
exclusion while operating on shared memory locations
Option (A): x=1;y=2
Means that 1 thread and 2 locks clearly showing that no deadlock situation
Option (B): x=2;y=1
Means that 2 threads and 1 lock → No deadlock situation
After usage of lock by 1 thread, it can release that lock and then 2nd thread can be used that
lock. So no deadlock
Option(C):x=2;y=2
Means that 2 threads and 2 locks → Deadlock can arise
Both threads can hold 1 lock and can wait for release of another lock
Option(D) x=1; y=1
Means that 1 thread and 1 lock → No deadlock situation
Hence Option(C) is correct.
48. The values of parameters for the Stop-and – Wait ARQ protocol are as given below:
Bit rate of the transmission channel = 1Mbps
Propagation delay from sender to receiver = 0.75 ms
Time to process a frame = 0.25ms
Number of bytes in the information frame =1980
Number of bytes in the acknowledge frame = 20
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
L (1980 + 20 ) × 8 2 × 8 × 103
(i) Tx = = = = 16 ms
B 106 106
L A 20 × 8
(ii) TACK = = = 0.16 ms
B 106
In stop-and-wait ARQ, efficiency
Tx 16 ms
η= = = 0.8933 ≈ 89.33%
Tx + TACK + 2TP + Tproc 17.91ms
49. A computer network uses polynomials over GF(2) for error checking with 8 bits as
information bits and uses x 3 + x + 1 as the generator polynomial to generate the check bits. In
this network, the message 01011011 is transmitted as
(A) 01011011010 (B) 01011011011 (C) 01011011101 (D) 01011011100
Key: (C)
Exp: Given generator polynomial G ( x ) = x 3 + x + 1 ⇒ 1011
message m ( x ) = 01011011
1011) 0 1 0 1 1 0 11 0 0 0 ( 01000011
0000
0 1 0 11
1 0 11
0 0000
0000
0 0 0 01
0000
0 0 0 11
0000
0 0 11 0
0000
0 11 0 0
1 0 11
0 111 0
1 0 11
0 101
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
50. Let p, q, and r be propositions and the expression ( p → q ) → r be a contradiction. Then, the
expression ( r → p ) → q is
(A) a tautology (B) a contradiction
(C) always TRUE when p is FALSE (D) always TRUE when q is TRUE
Key: (D)
Exp: (p → q) → r is contradiction only when
p q r
T T F
F T F
F F F
And now for the above combination, the expression ( r → p ) → q is always true when q is
true. When q is false in the above combination (third one) ( r → p ) → q will be false.
51. A cache memory unit with capacity of N words and block size of B words is to be designed.
If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If the cache
unit is now designed as a 16-way set-associative cache, the length of the TAG field is
______bits.
Key: (14)
N
Exp: Total bits = 10 + log 2 + log 2 B
B
Offset
# of blocks
N
10 + log 2 ( N ) = log 2 + T
16
where T is the required length of TAG field
∴ T = 14
53. Consider a database that has the relation schema CR (StudentName, CourseName). An
instance of the schema CR is as given below.
CR
Student Name Course Name
SA CA
SA CB
SA CC
SB CB
SB CC
SC CA
SC CB
SC CC
SD CA
SD CB
SD CC
SD CD
SE CD
SE CA
SE CB
SF CA
SF CB
SF CC
n n
54. Let A be n × n real valued square symmetric matrix of rank 2 with ∑∑ A
i =1 j=1
2
ij = 50 . Consider
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
(II) The eigen value with the largest magnitude must be strictly greater than 5.
Which of the above statements about eigen values of A is/are necessarily CORRECT?
(A) Both (I) and (II) (B) (I) only
(C) (II) only (D) Neither (I) nor (II)
Key: (B)
Exp: ρ ( A ) < n ⇒ A = 0 ⇒ one eigen value must be '0' ∈ [ −5,5]
∴ (I) is true
5 0 0 3 3
Let A = 0 −5 0 ⇒ ∑∑ Aij2 = 50 and ρ ( A ) = 2
0 0 0
i =1 j=1
∴ (II) is false
55. Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-
terminals
G1 : S → aSb T,T → cT ∈
G 2 :S → bSa T,T → cT ∈
The language L ( G1 ) ∩ L ( G 2 ) is
(A) Finite. (B) Not finite but regular.
(C) Context-free but not regular. (D) Recursive but not context-free.
Key: (B)
Exp: The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals
are:
G1 : S→aSb | T, T→ cT | ϵ
G2 : S→bSa | T, T→ cT |ϵ
Lets L(G1) is the language for grammar G1 and L(G2) is the language for grammar G2
L(G1) = {ancmbn| n, m ≥0}
L(G1) = {bncman| n ,m≥0}
L1 ∩ L2 ={ cm|m ≥ 0 }; which is infinite and regular
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
General Aptitude
Q. No. 1 - 10 Carry One Mark Each
1. Research in the workplace reveals that people work for many reason ___________.
(A) money beside (B) beside money (C) money besides (D) besides money
Key: (D)
2. After Rajendra chola returned from his voyage to Indonesia, he _______ to visit the temple in
Thanjavur.
(A) was wishing (B) is wishing (C) wished (D) had wished
Key: (C)
3. Rahul Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of
Murali. Srinivas is sitting to the right of Arul. Which of the following pairs are seated
opposite each other ?
(A) Rahul and Murali (B) Srinivas and Arul
(C) Srinivas and Murali (D) Srinivas and Rahul
Key: (C)
Exp:
Srinivas
Rahul Arul
Murali
5. The probability that a k-digit number does NOT contain the digits 0,5,or 9 is
(A) 0.3k (B) 0.6k (C) 0.7k (D) 0.9k
Key: (C)
Exp:
k digits
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
Each digit can be filled in 7 ways as 0, 5 and 9 are not allowed. So each of these places can be
filled by 1, 2, 3, 4, 6, 7, 8.
k
7
So required probability is or 0.7 k .
10
6. A contour line joins locations having the same height above the mean sea level. The following
is a contour plot of a geographical region. Contour lines are shown at 25m intervals in this
plot. If in a flood, the water level rises to 525m, which of villages P,Q, R, S,T get submerged
?
7. “The hold of the nationalist imagination on our colonial past is such that anything
inadequately or improperly nationalist is just not history”
Which of the following statements best reflects the author’s opinion ?
(A) Nationalists are highly imaginative.
(B) History is viewed through the filter of nationalism.
(C) Our colonial past never happened.
(D) Nationalism has to be both adequately and properly imagined.
Key: (B)
( x + y) − x − y
8. The expression is equal to
2
(A) the maximum of x and y (B) the minimum of x and y
(C) 1 (D) None of the above
Key: (B)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-01 www.gateforum.com
9. Six people are seated around a circular table. There are at least two men and two women .
There are at least three right-handed persons. Every woman has a left-handed person to her
immediate right. None of the women are right-handed. The number of women at the table is
(A) 2 (B) 3
(C) 4 (D) Cannot be determined
Key: (A)
Exp: Out of six people, 3 place definitely occupied by right handed people as atleast 2 women are
there so these two will sit adjacently. Now as only one seat is left it will be occupied by a left
handed man because on right side of this seat is sitting an right handed man.
R (m)
R (m) R (m)
?
L(w)
L(w)
Therefore, answer should be 2 women.
10. Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured
red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the
colour white. Gulab and Neel like all the colours. In how many different ways can they
choose the shirts so that no one has a shirt with a colour he or she dislikes ?
(A) 21 (B) 18 (C) 16 (D) 14
Key: (D)
Exp: As there are 4 people A,G,N,S and 4 colours so without any restriction total ways have to be
4 × 4 = 16
Now, Arun → dislikes Red and
Shweta → dislikes white
So 16-2=14 ways
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
R ={( a,a ) , ( a,b ) , ( a,c ) , ( a,d ) , ( a,e ) , ( b,b ) , ( b,c ) , ( b,e) , ( c,c) , ( c,e) , ( d,d ) , ( d,e) , ( e,e)} .
The Hasse diagram of the partial order (X, R) is shown below.
e
o
c o
od
b o
o
a
The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is
________.
Key: (0)
Exp: Given POSET is already a lattice so no need to add any ordered pairs.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
(A) P-(ii), Q-(iv), R-(i), S-(iii) (B) P-(ii), Q-(i), R-(iv), S-(iii)
(C) P-(ii), Q-(iv), R-(iii), S-(i) (D) P-(iii), Q-(iv), R-(i), S-(ii)
Key: (A)
Exp: P. static char var:
var is defined as character variable whose associated storage class is static because of
this it is given memory from data segment .
Q. m = malloc (10 ) ;
m = NULL;
10 contiguous bytes of memory is allocated is address of first byte is stored in 'm' and
later it is updated with NULL. Now we lost the address of first bytes of that chunk of
memory completely. So we can't free that space as we need the address of first byte to
free it up
R. char * ptr [10]:
ptr is an array of 10 pointers pointing to character variables.
S. register int varl:
Suggesting the complier to store the var1 “value” in CPU register.
4. Let L1 , L 2 be any two context free languages and R be any regular language. Then which of
the following is/are CORRECT ?
I. L1 ∪ L 2 is context − free II. L1 is context − free
III. L1 − R is context − free IV. L1 ∩ L 2 is context − free
(A) I, II and IV only (B) I and III only
(C) II and IV only (D) I only
Key: (B)
Exp: Given L1 and L2 are context free languages and R is a regular language.
I. L1 ∪ L2 is context free is CORRECT, context free language are closed under union
operation.
II. L1 is context free is INCORRECT, context free languages are not closed under
complement operation.
III. L1 –R is Context free is CORRECT.
L1 – R = L1∩ R , Context free intersection Regular is always Context free.
IV. L1 ∩ L2 is context free is INCORRECT; context free languages are not closed under
complement operation.
5. G is undirected graph with n vertices and 25 edges such that each vertex of G has degree at
least 3. Then the maximum possible value of n is ___________.
Key: (16)
Exp: If every vertex has degree at least k then
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
K V ≤ 2(E)
3 V ≤ 2 × 25
50
V ≤
3
V ≤16
∴ ( ¬p ∧ r ) ∧ ( ¬r → ( p ∧ q ) )
7. The Breadth First Search (BFS) algorithm has been implemented using the queue data
structure. Which one of the following is a possible order of visiting the nodes in the graph
below?
M N O
R Q P
1 1 −1 −1 −2 −1
8. Let P = 2 −3 4 and Q = 6 12 6 be two matrices.
3 −2 3 5 10 5
Then the rank of P +Q is _____________.
Key: (2)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
Exp:
0 −1 12
P + Q = 8 9 10
8 8 8
8 9 10
R1 ↔ R 2 ∼ 0 −1 −2
1 1 1
R3
8
8 −9 10
8R 3 − R1 ∼ 0 −1 −2
0 −1 −2
8 −9 10
R 3 − R 2 ∼ 0 −1 −2
0 0 0
∴Rank is 2
9. Consider socket API on a Linux machine that supports connected UDP sockets. A connected
UDP socket is a UDP socket on which connect function has already been called. Which of the
following statements is/are CORRECT ?
I. A connected UDP socket can be used to communicate with multiple peers
simultaneously.
II. A process can successfully call connect function again for an already connected UDP
socket.
(A) I only (B) II only (C) Both I and II (D) Neither I nor IIs
Key: (B)
Exp: A process with a connected UDP socket can call connect again for that socket for one of two
reasons:
(1) To specify a new IP address and port.
(2) To unconnect the socket.
10. The minimum possible number of states of a deterministic automaton that accepts the regular
language
L = {w1aw 2 w1 , w 2 ∈{a,b}* , w1 = 2, w 2 ≥ 3} is ____________.
Key: (8)
Exp: The Given regular language is
L = {w1aw2|w1, w2 ∈{a,b}*, |w1| = 2 |w2|≥3}
The minimal Deterministic finite automata accepting L is:
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
a,b
R a,b
P Q R S
2 2 2 2
3 8 8 3
7 3 3 2
5 8 9 7
6 9 5 7
8 5 7 2
9 8
In table T1, P is the primary key and Q is the foreign key referencing R in table T2 with on-
delete cascade and on-update cascade. In table T2, R is the primary key and S is the foreign
key referencing P in table T1 on-delete set NULL and on-update cascade. In order to delete
record 3,8 from table T1, the number of additional records that need to be deleted from
table T1 is ______________.
Key: (0)
Exp: Only (8,3) will be deleted from T2.
12. Which of the following is/are shared by all the threads in a process ?
I. Program counter II. Stack
III. Address space IV. Registers
(A) I and II only (B) III only (C) IV only (D) III and IV only
Key: (B)
Exp:
C ode D a ta F ile
C ode D a ta F ile
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
13. A circular queue has been implemented using a single linked list where each node consists of
a value and a single pointer pointing to the next node. We maintain exactly two external
pointers FRONT and REAR pointing to the front node and the rear node of the queue,
respectively. Which of the following statements is/are CORRECT for such a circular queue,
so that insertion and deletion operation can be performed in O (1) time ?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
(A) I only (B) II only (C) Both I and II (D) Neither I nor II
Key: (B)
Exp: Next pointer of the front node would point to the second node, if any.
Front Rear
14. Given the following binary number in 32-bit (single precision) IEEE-754 format:
00111110011011010000000000000000
The decimal value closest to this floating- point number is
(A) 1.45 × 101 (B) 1.45 × 10 −1 (C) 2.27 × 10 −1 (D) 2.27 × 101
Key: (C)
Exp: Sign
0 01111100 11011010000000000000000
+1 124
−3
2−1 + 2−2 + − − − − −
+1 2 =0.227....
[1 +] 0.8515625
15. An ER model of a database consists of entity types A and B. These are connected by a
relationship R which does not have its own attribute. Under which one of the following
conditions, can the relational table for R be merged with that of A?
(A) Relationship R is one-to-many and the participation of A in R is total
(B) Relationship R is one-to-many and the participation of A in R is partial
(C) Relationship R is many-to one and the participation of A in R is total
(D) Relationship R is many-to one and the participation of A in R is partial
Key: (C)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
Exp:
A R m B
1
a b c d
A&R
a B c
b c d
Key: (C)
Exp: P. Towers of Hanoi ⇒ T ( n ) = 2T ( n − 1) + 1 ⇒ θ ( 2 n )
n
Q. Binary search ⇒ T ( n ) = T + C ⇒ θ ( log n )
2
R. Heap sort ⇒ θ ( n log n )
17. Match the following according to input (from the left column) to the complier phase (in the
right column) that processes it.
Column-1 Column-2
P. Syntax tree i. Code generator
Q. Character stream ii. Syntax analyzer
R. Intermediate representation iii. Semantic analyzer
S. Token stream iv. Lexical analyzer
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
18. Consider the following statements about the routing protocols, Routing Information Protocol
(RIP) and Open Shortest Path First (OSPF) in an IPv4 network.
I. RIP uses distance vector routing
II. RIP packets are sent using UDP
III. OSPF packets are sent using TCP
IV. OSPF operation is based on link-state routing
Which of the statements above are CORRECT?
(A) I and IV only (B) I, II and III only
(C) I, II and IV only (D) II, III and IV only
Key: (C)
Exp: Statement (1): RIP uses distance vector routing. “CORRECT”
RIP is one of the oldest DVR protocol which employ the hop count as a routing metric.
Statement (2): RIP packets are sent using UDP. “CORRECT”
RIP uses the UDP as its transport protocol, and is assigned the reserved port no 520.
Statement (3): OSPF packets are sent using TCP. “INCORRECT”
OSPF does not use a transport protocol , such as UDP (or) TCP, but encapsulates its data
directly in IP packets.
Statement (4): OSPF operation is based on link state routing. “CORRECT”
OSPF is a routing protocol which uses link state routing (LSR) and works within a single
autonomous system.
Hence Option “C” is correct.
πx 1 2R
19. If f ( x ) = R sin + S,f ' = 2 and ∫10 f ( x ) dx = , then the constants R and S are,
2
2 π
respectively
2 16 2 4 4 16
(A) and (B) and 0 (C) and 0 (D) and
π π π π π π
Key: (C)
Rπ πx
Exp: f1 (x)= cos
2 2
Rπ 4
⇒ f 1 (1 2 ) = 2 gives = 2 ⇒R=
2 2 π
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
1 1
2R −2R πx
Also ∫ f ( x ) dx = cos + S ( x )0 = 2 R π
1
gives
0
π π 2 0
⇒S= 0
20. In a file allocation system, which of the following allocation schemes(s) can be used if no
external fragmentation is allowed?
I. Contiguous II. Linked III. Indexed
(A) I and III only (B) II only (C) III only (D) II and III only
Key: (D)
Exp: Contiguous allocation suffer from external fragmentation. But linked and indexed allocation
schemes free from external fragmentation. Hence, option D is correct.
21. Consider a quadratic equation x 2 −13x + 36 = 0 with coefficients in a base b. The solutions of
this equation in the same base b are x = 5 and x = 6. Then b = ___________.
Key: (8)
Exp: Clearly 13 = 1 × 10 + 3 and 36 = 3 × 10 + 6 ⇒ base b = 10
The quadratic equation with solutions x = 5 and x = 6 is x 2 − 11x + 30 = 0
According to the given condition, we have b + 3 = 11 and 3b + 6 = 30 ⇒ b = 8
Answer is 8.
Alternate solution:
x 2 − 13x + 36 = 0 ( given quadratic equation )
In base b, 13= 1 × b1 + 3 × b0 = b + 3 and
36 = 3 × b1 + 6 × b 0 = 3b + 6
22. Identify the language generated by the following grammar, where S is start variable.
S → XY
X → aX a
Y → a Yb ∈
{
(A) a m b n m ≥ n, n > 0 } (B) {a m
b n m ≥ n, n ≥ 0 }
(C) {a m
bn m > n, n ≥ 0} (D) {a m
bn m > n, n > 0}
Key: (C)
Exp: The given grammar with S as start symbol is
S→XY
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
X→aX|a
Y→aYb|ϵ
From Non terminal X we can generate any number of a’s including a single ‘a’ and from Y
equal number of a’s and b’s.
Hence L ={ambn|m>n, n≥0}
23. The representation of the value of a 16-bit unsigned integer X in hexadecimal number system
is BCA9. The representation of the value of X in octal number system is
(A) 571244 (B) 736251 (C) 571247 (D) 136251
Key: (D)
Exp: ( BCA9 )16 → (136251)8
Convert hexadecimal to octal number system.
ptr 100
∴1,0 is pr int ed
25. The maximum number of IPv4 router addresses that can be listed in the record route (RR)
option field of an IPv4 header is _________.
Key: (9)
Exp: A record route option is used to record the internet routers that handles the datagram. It can
list up to nine router addresses. It can be used for debugging and management purpose.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
26. Consider a binary code that consists of only four valid code words as given below:
00000,01011,10101,11110
Let the minimum Hamming distance of the code be p and the maximum number of erroneous
bits that can be corrected by the code be q. Then the values of p and q are
(A) p = 3 and q = 1 (B) p = 3 and q = 2
(C) p = 4 and q = 1 (D) p = 4 and q = 2
Key: (A)
Exp: Given :
code1 00000
code2 01011
code3 10101
code4 11110
Hamming distance between code 1 and code 2 is 3.
Hamming distance between code 1 and code 3 is 3.
Hamming distance between code 1 and code 4 is 4.
Hamming distance between code 2 and code 3 is 4.
Hamming distance between code 2 and code 4 is 3.
Hamming distance between code 3 and code 4 is 3.
So, as per Hamming code, minimum Hamming distance of all code words is considered as
Hamming distance i.e., 3 (p).
Now, the max number of erroneous bits that can be corrected by the Hamming code is 2d + 1.
So,
2d + 1 = 3 ⇒ d = 1
So option A is correct.
27. A system shares 9 tape drives. The current allocation and maximum requirement of tape
drives for three processes are shown below:
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
Exp:
PID Current Allocation Max need Available Need
P1 3 3 2 4
P2 1 6 - 5
P3 3 5 - 2
With the above state of systems, we can get the following 2 safe sequences.
(1) < P3 , P2 , P1 >
(2) < P3 , P1 , P2 >
Hence, system is in safe state, no deadlocked option B is correct.
Total = 70 = 70 − (12 + 5 )
a, b, c,d a, b, c
before 2 before 2
Therefore, 53+1=54
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
29. If w, x, y, z are Boolean variables, then which one of the following is INCORRECT ?
(A) wx + w ( x + y ) + x ( x + y ) = x + wy
( )
(B) wx y + z + wx = w + x + yz
(C) (w x ( y + xz ) + w x) y = x y
( )
(B) L.H.S : wx y + z + wx = wx + yz
R.H.S : wx ( y + z ) + wx
( )
⇒ wx + y + z + wx x + y = x.y
( ) ( )
⇒ w + x + yz + wx
⇒ w + x + yz + wx
⇒ w + x + yz = R.H.S
L.H.S = R.H.S
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
c
100 p 100
strlen ( c + 2 [ p ] − 6 [ p ] − 1)
↓ ↓ ↓
100 + T − I −1
Note: Whenever we have characters in the arithmetic expressions, we can replace those with
their ASCII values
Strlen (100 + x + 11 − x − 1) [ assume x has the ASCII value of I ]
⇒ Strlen (110 )
∴ 2 is pr int ed
1
31. P and Q are considering to apply for a job. The probability that P applies for the job is .
4
1
The probability that P applies for the job given that Q applies for the job is , and the
2
1
probability that Q applies for the job given that P applies for the job . Then the probability
3
that P does not apply for the job given that Q does not apply for the job is
4 5 7 11
(A) (B) (C) (D)
5 6 8 12
Key: (A)
Exp: Let A,B be the events denote that P, Q respectively applies for a job
1 1 1
⇒ Pr ( A ) = ,Pr ( A B ) = − − − (1) and Pr ( B A ) = − −(2)
4 2 3
1
(2)gives Pr ( A ∩ B) =
12
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
1
∴ (1) gives Pr ( B ) =
6
1 1 1
∴Pr = =
(
A Pr A ∩ B 1 − P r ( A ∪ B ))=
1− + −
4 6 12 = 2 × 6 = 4
B
Pr B 1 − ( )
P r ( B ) 1−
1 3 5 5
6
P ( A ∩ B)
Here Pr is Probability and P ( A / B ) =
P ( B )
32. If the characteristics polynomial of 3 × 3 matrix M over R ( the set of real numbers) is
λ 3 − 4λ 2 + aλ + 30, a ∈ R, and one eigenvalue of M is 2, then the largest among the absolute
values of the eigenvalues of M is ________.
Key: (5)
Exp: E ( X ) = 5 ⇒ ( X 2 ) = 30, where X ∼ P ( λ ) , λ = 5
∴E ( X + 2 ) = E ( X 2 ) + 4.E ( X ) + 4 = 30 + 20 + 4 = 54
2
(∵ V ( X ) = E ( X ) − (E(X)) )
2 2
⇒ a = −11
∴Characteristic polynomial is
λ 3 − 4λ 2 − 11λ + 30 = 0
( λ − 2 )( λ − 5)( λ + 3) = 0
∴λ = 2,5, −3
L arg est absolute value of ' λ ' is 5
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
(C) E → TX (D) E → TX | ( TX )
X → − TX|∈ X →− TX | +TX |∈
T → FY T → id
Y → + FY |∈
F → ( E ) | id
Key: (C)
Exp: The rule for removal of left recursion is
A →Aα |β will be
A →β A’
A’ → αA’|ϵ
The given grammar is:
E → E – T | T; in this α is “– T” and β is T
T →T + F | F , In this α is “+ F” and β is F
F → (E) | id
Hence after removal of the left recursion:
E → TX
X → - TX|ϵ
T → FY
Y → +FY|ϵ
F → (E) | id
34. In a two-level cache system, the access times of L1 and L 2 caches are 1 and 8 clock cycles,
respectively. The miss penalty from L2 cache to main memory is 18 clock cycles . The miss
rate of L1 cache is twice that of L2. The average memory access time (AMAT) of this cache
system is 2 cycles. This miss rates of L1 and L2 respectively are :
(A) 0.111 and 0.056 (B) 0.056 and 0.111
(C) 0.0892 and 0.1784 (D) 0.1784 and 0.0892
Key: (A)
Exp: 2 = 1 + 2m × 8 + m × 18
1
∴m =
34
35. Consider two hosts X and Y, connected by a single direct link of rate 106 bits/sec . The
distance between the two hosts is 10,000 km and the propagation speed along the link is
2 × 108 m sec . Host X sends a file of 50,000 bytes as one large message to host Y
continuously. Let the transmission and propagation delays be p milliseconds and q
milliseconds, respectively . Then the values of p and q are
(A) p = 50 and q = 100 (B) p = 50 and q = 400
(C) p = 100 and q = 50 (D) p = 400 and q = 50
Key: (D)
Exp: Given data
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
L = 50,000 Bytes
L 50,000 × 8
∴ Transmission time (p) = = = 400 ms
B 106
d 107
∴ Propagation Time (q) = = = 50 ms
v 2 × 108
Key: (B)
Exp: T ( n ) = 2T ( n ) +1
Put n = 2K
T ( 2K ) = 2T ( 2K 2 ) + 1
Assume T ( 2K ) = δ ( K )
K
⇒δ ( K ) = 2δ + 1
2
By master's theorem
δ(K) = θ(K)
T ( 2K ) = θ ( K )
T ( n ) = θ ( log n ) ∵ 2k = n
37. If a random variable X has a Poisson distribution with mean 5, then the expectation
E ( X + 2 ) equals ______________.
2
Key: (54)
Exp: E ( X ) = 5 ⇒ E ( X 2 ) = 30, where X ∼ P ( λ ) , λ = 5
∴ E ( X + 2 ) = E ( X 2 ) + 4E ( X ) + 4
2
= 30 + 20 + 4 = 54
(∵ V ( X ) = E ( X ) − ( E ( X )) )
2 2
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
Key: (C)
Exp: for i = 1
j will run from 1 to n by incrementing by '1' in each step ⇒ 'j 'will run for n times
For i = 2
n
j will run from 1 ton by incrementing by ‘2’ in each step ⇒ j will run for times and so on
2
n n n
Time Complexity ( Tc ) = n + + + ...... +
2 3 n
1 1 1
= n 1 + + + .... + = θ ( n log n )
2 3 n
39. The pre-order transversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19,
17, 20. Then the post-order traversal of this tree is:
(A) 2,6,7,8,9,10,12,15,16,17,19,20 (B) 2,7,6,10,9,8,15,17,20,19,16,12
(C) 7,2,6,8,9,10,20,17,19,15,16,12 (D) 7,6,2,10,9,8,15,16,17,20,19,12
Key: (B)
Exp: Given: Preorder ! 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20
In order! 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
Note: BST In order will give ascending order
Corresponding BST is
12
8 16
6 9 15 19
2 7 10 17 20
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
40. Consider the C program fragment below which is meant to divide x by y using repeated
subtractions. The variables x, y, q and r are all unsigned int.
while (r >= y) {
r = r – y;
q = q +1;
}
Which of the following conditions on the variables x, y, q and r before the execution of the
fragment will ensure that the loop terminates in a state satisfying the condition x = = (y*q +
r)?
(A) (q = = r) && (r = =0)
(B) (x > 0) && (r = =x) && (y > 0)
(C) (q = = 0) && (r = = x) && (y > 0)
(D) (q = = 0) && (y > 0)
Key: (C)
Exp: Given, program is:
while ( r ≥ y ){
r = r − y;
q = q + 1;
}
If we want to final value as x = = ( y × q + r ) . Then initial value of r should be equal to x
(Since y is subtracted from r each time in given code). q incremented by 1 (q is quotient here).
To avoid undefined behavior , value of y should be greater than zero.
Therefore, ( q == 0 ) & & ( r == x ) & & ( y > 0 )
41. A message is made up entirely of characters from the set X= {P,Q,R,S,T}. The table of
probabilities for each of the characters is shown below:
Character Probability
P 0.22
Q 0.34
R 0.17
S 0.19
T 0.08
Total 1.00
If a message of 100 characters over X is encoded using Huffman coding, then the expected
length of the encoded message in bits is_____
Key: (225)
Exp: Huffman tree is as follows
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
1.0
0.59
0.41
0.25 0.17
S 0.19 0.22 Q
P
0.08 0.17
T R
42. The next state table of a 2-bit saturating up-counter is given below.
Q1 Q 0 Q1+ Q 0+
0 0 0 1
0 1 1 0
1 0 1 1
1 1 1 1
The counter is built as a synchronous sequential circuit using T flip-flops. The expression for
T1 and T0 are
(A) T1 = Q1Q 0 , T0 = Q1 Q 0
(B) T1 = Q1Q 0 , T0 = Q1 + Q 0
(C) T1 = Q1 + Q 0 , T0 = Q1 + Q 0
(D) T1 = Q1Q 0 , T0 = Q1 + Q 0
Key: (B)
Exp:
Q1 Q0 Q1+ Q0+ T1 T0
0 0 0 1 0 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 0 0
T1 = Q1Q 0
T0 = Q1 + Q 0
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
43. Consider the set of processes with arrival time (in milliseconds). CPU burst time (in
milliseconds), and priority (0 is the highest priority) shown below. None of the processes have
I/O burst time.
Process Arrival Time Burst Time Priority
P1 0 11 2
P2 5 28 0
P3 12 2 3
P4 2 10 1
P5 9 16 4
The average waiting time (in milliseconds) of all the processes using preemptive priority
scheduling algorithm is __________
Key: (29)
Exp:
PID AT BT Priority CT TAT Waiting Time
P1 0 11 2 49 49 38
P2 5 28 0 33 28 0
P3 12 2 3 51 39 37
P4 2 10 1 40 38 28
P5 9 16 4 67 58 42
Gantt Chart:
P1 P4 P2 P4 P1 P3 P6
0 2 5 33 40 49 51 67
44. For any discrete random variable X, with probability mass function
N
P ( X = j) = p j , p j ≥ 0, j ∈ {0,.....N} and ∑p
j= 0
j = 1, define the polynomial function
N
g x ( z ) = ∑ p jz j For a certain discrete random variable Y, there exists a scalar β∈ [ 0,1] such
j= 0
that g Y ( z ) = (1 − β + β z )
N
. The expectation of Y is
(A) Nβ (1 − β )
(B) Nβ
(C) N (1 − β )
(D) Not expressible in terms of N and β alone
Key: (B)
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
45. The read access times and the hit ratios for different caches in a memory hierarchy are as
given below.
The read access time of main memory is 90 nanoseconds. Assume that the caches use the
referred word-first read policy and the write back policy. Assume that all the caches are direct
mapped caches. Assume that the dirty bit is always 0 for all the blocks in the caches. In
execution of a program, 60% of memory reads are for instruction fetch and 40% are for
memory operand fetch. The average read access time in nanoseconds (up to 2 decimal places)
is______.
Key: (4.72)
Exp: Given,
Cache I-Cache D-Cache L2-Cache Main Memory
Read Access Time 2 2 8 90
(in ns)
Hit Ratio 0.8 0.9 0.9 1.0
And in execution of program 60% of memory reads are for instruction fetch and 40% are for
memory operand fetch.
Now,
Average instruction fetch time=I-cache access time+ I-cache miss ratio * L2-cache access time
+ I-cache miss rate * L2-cache miss ratio * main memory access time
= 2 + (1 − 0.8 ) × 8 + (1 − 0.8 ) × (1 − 0.9 ) × 90 = 5.4n sec
And average data fetch time = D-cache access time +D-cache miss ratio* L2-cache access
time+ D-cache miss ratio *L2-cache miss ratio* main memory access time
2 + (1 − 0.9 ) × 8 + (1 − 0.9 ) × (1 − 0.9 ) × 90 = 3.7n sec
Therefore, average memory access time = Fraction of instruction fetch * average instruction
fetch time + fraction of data fetch * Average data fetch time
= 0.6 × 5.4 + 0.4 × 3.7 = 4.72 ( in n sec )
∞ 1+ z
46. If the ordinary generating function of a sequence {a n }n =0 is , then a 3 − a 0 is equal to
(1 − z )
3
______.
Key: (15)
1
Exp: f (z) = = 1 + z + z 2 + .....
1− z
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
1
f '( z ) = = 1 + 2z + 3z 2 + ....
(1 − z )
2
1+ z 1 2z
Consider = +
(1 − z ) (1 − z ) (1 − z )
3 2 3
1
= 1 + 2z + 3z 2 + 4z3 ...
(1 − z )
2
2
f "( z ) = = +2 + 6z + 12z 2 .....
(1 − z )
3
1 2z
+ = (1 + 2z + 3z 2 + 4z3 − ...) + ( 2z + 6z 2 + 12z3 ....)
(1 − z ) (1 − z )
2 3
= 1 + 4z + 9z 2 + 16z3 .....
= a 0 + a1z + a 2 z 2 + a 3z3 .......
a0 = 1
a 3 = 16
a 3 − a 0 = 16 − 1 = 15
47. Consider the following snippet of a C program. Assume that swap (&x, &y) exchanges the
contents of x and y.
int main ( ) {
int array[]={3,5,1,4,6,2};
int done =0 ;
int i ;
while (done = = 0) {
done = 1;
for (i = 0; i <=4; i ++) {
if (array [i] < array [i +1]) {
swap (& array [i], &array [i+1]);
done = 0;
}
}
for (i = 5 ; i > =1; i --) {
if (array [i] > array [ i-1]) {
swap ( & array [i] , &array [i-1]);
done = 0;
}
}
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
}
printf ( “ %d “ , array [3] );
}
The output of the program is ____________.
Key: (3)
Exp: The final contents of the array is
6 5 4 3 2 1
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
Fontaine France 13
Pele Brazil 12
Klinsmann Germany 11
Kocsis Hungary 11
Batistuta Argentina 10
Cubillas Peru 10
Lato Poland 10
Lineker England 10
T Miller Germany 10
Rahn Germany 10
Key: (7)
Exp: Player
K lose
Ronaldo
G Muller
Fontaine
Pele
Klinsmann
Kocsis
50. Given f (w,x,y,z) = ∑ m (0,1,2,3,7,8,10) + ∑ d (5,6,11,15), where d represents the don’t care
condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS)
form of f(w,x,y,z) ?
(
(A) f = w + z x + z)( ) ( )
(B) f = w + z ( x + z )
Key: (A)
Exp:
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
yz
wx 00 01 11 10
00 1 1 1 1
01 0 x 1 x
11 0 0 x 0 (x + z)
10 1 0 x 1
(w + z )
(
= w+z x+z )( )
51. In a B+ tree, if the search –key value is 8 bytes long, the block size is 512 bytes and the block
pointer size is 2 bytes, then maximum order of the B+ tree is _______________.
Key: (52)
Exp: Let ‘K’ be the order
K ( 2 ) + ( K − 1)( 8 ) ≤ 512
⇒ 2K + 8k − 8 ≤ 512
520
⇒ 10K ≤ 520 ⇒ K ≤
10
∴ K ≤ 52
52. Let L(R) be the language represented by regular expression R. Let L(G) be the language
generated by a context free grammar G. Let L (M) be the language accepted by a Turning
machine M. Which of the following decision problems are undecidable ?
I. Given a regular expression R and a string w, is w ∈L(R)?
II. Given a context-free grammar G, L ( G ) =∅ ?
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
III. A given context free grammar G, is L(G) is Σ* for some alphabet Σ?, is undecidable
problem. We can’t check whether L(G) = Σ* or not but rather we can check complement
of L(G) is ϕ .Since context free language are not closed under complement operation
L ( G ) may be language accepted by Turing Machine and we can’t check emptiness for
Turing machine.
IV. Given a Turing Machine M and a string w, is w ∈ L(M)? , is a membership problem for
TM. Membership problem is not a decidable problem for TM.
53. Consider a machine with a byte addressable main memory of 232bytes divided into blocks of
size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this
machine. The size of the tag field in bits is ______.
Key: (18)
Exp:
32 − ( 5 + 9 ) = 18
54. Let δ denote that transition function and δ̂ denote the extended transition function of the
∈− NFA whose transition table is given below:
δ ∈ a b
→ q0 {q 2 } {q1} {q 0 }
q1 {q 2 } {q 2 } {q 3 }
q2 {q 0 } ∅ ∅
q3 ∅ ∅ {q 2 }
Then δˆ ( q 2 ,aba ) is
(A) ∅ (B) {q 0 , q1 , q 3 } (C) {q 0 , q1 , q 2 } (D) {q 0 , q 2 , q 3 }
Key: (C)
Exp:
The given table for NFA-ϵ Transition is
δ ϵ a b
→q0 {q2} {q1} {q0}
q1 {q2} {q2} {q3}
q2 {q0} Φ Φ
q3 Φ Φ {q2}
The process is we start with ϵ-closure of q2 then for each input first take the transition then
calculate ϵ-closure
q2 is the start for processing we take ϵ-closure which is {q0,q2}and process “aba”
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
q1 ϕ Calculate ϵ-closure
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
General Aptitude
Q. No. 1 - 5 Carry One Mark Each
1. There are 3 red socks, 4 green socks and 3 blue socks, you choose 2 socks. The probability
that they are of the same colour is ___________.
(A) 1 5 (B) 7 30 (C) 1 4 (D) 4 15
Key: (D)
3C2 + 4C2 + 3C2 4
Exp: Required probability = =
10C2 15
3. There are five buildings called V, W, X, Y and Z in a row (not necessarily in that order). V is
to the west of W. Z is to the East of X and the West of V. W is to the West of Y. Which is the
building in the middle ?
(A) V (B) W (C) X (D) Y
Key: (A)
Exp: From the given data, the following is formed
X Z V W Y N
W E
West East S
∴ The building ‘V’ is in the middle
4. A test has twenty questions worth 100 marks in total. There are two types of questions,
multiple choice questions are worth 3 marks each and essay questions are worth 11 marks
each. How many multiple choice questions does the exam have?
(A) 12 (B) 15 (C) 18 (D) 19
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
Key: (B)
Exp: x + y = 20 ( x = MCQ, y = Essay type )
3x + 11y = 100
⇒ x = 15, y = 5
6. “We lived in a culture that denied any merit to literary works, considering them important
only when they were handmaidens to something seemingly more urgent - namely ideology.
This was a country where all gestures, even the most private, were interpreted in political
terms."
The author's belief that ideology is not as important as literature is revealed by the word:
(A) ‘culture’ (B) ‘seemingly’ (C) ‘urgent’ (D) ‘political’
Key: (B)
7. X is a 30 digit number starting with the digit 4 followed by the digit 7, then the number X3
will have
(A) 90 digits (B) 91 digits (C) 92 digits (D) 93 digits
Key: (A)
Exp: X = ( 47...........) 30 digits
8. There are three boxes, one contains apples, another contains oranges and the last one contains
both apples and oranges. All three are known to be incorrectly labelled. If you are permitted
to open just one box and then pull out and inspect only one fruit, which box would you open
to determine the contents of all three boxes?
(A) The box labelled ‘Apples’ (B) The box labelled ‘Apples and Oranges’
(C) The box labelled 'Oranges' (D) Cannot be determined
Key: (B)
Exp: The person who is opening the boxes, he knew that all 3 are marked wrong.
Suppose if 3 boxes are labelled as below.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
If he inspected from Box(1), picked one fruit, found orange, then he don’t know whether box
contains oranges (or) both apples and oranges.
Similarly, if he picked one fruit from box(2), found apple then he don’t know whether box
contain apples (or) both apples and oranges.
But if he picked one fruit from box(3), i.e., labelled is “apples and oranges’, if he found apple
then he can decide compulsorily that box(3) contains apples and as he knew all boxes are
labelled as incorrect, he can tell box(2) contains both apples and oranges, box(1) contain
remaining oranges. So, he should open box labelled ‘Apples and Oranges’ to determine
contents of all the three boxes.
9. An air pressure contour line joins locations in a region having the same atmospheric pressure .
The following is an air contour plot of a geographical region . Contour lines are shown at 0.05
bar intervals in this plot.
R
0.65
0.7 0.9
0.95 0.08
S
P0.9
0.8
0.8 Q 0.75
If the possibility of a thunderstorm is given by how fast air pressure rises or drops over a
region, which of the following regions is most likely to have a thunderstorm?
(A) P (B) Q (C) R (D) S
Key: (C)
Exp:
Region Air pressure difference
P 0.95 – 0.90 = 0.05
Q 0.80 – 0.75 = 0.05
R 0.85 – 0.65 = 0.20
S 0.95 – 0.90 = 0.05
In general thunder storms are occurred in a region where suddenly air pressure changes (i.e.,)
sudden rise (or) sudden fall of air pressure. From the given contour map in ‘R’ region only
more changes in air pressure. So, the possibility of a thunder storms in this region.
So option (C) is correct.
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.
|CS| GATE-2017-PAPER-02 www.gateforum.com
ICP–Intensive Classroom Program eGATE-Live Internet Based Classes DLP TarGATE-All India Test Series
Leaders in GATE Preparations 65+ Centers across India
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this booklet may be reproduced or utilized in any form without the written permission.