GATE 2015 Solved Paper

CSIT: Computer Science and Information Technology

Set – 1
Number of Questions: 65 Total Marks:100.0

Wrong answer for MCQ will result in negative marks, (−1/3) for 1 Mark Questions and (−2/3) for 2 Marks
Question.

General Aptitude
Number of Questions: 10 Section Marks: 15.0
Question 1 to Question 5 carry 1 mark each and (iii) He failed to make many of his good starts count.
Question 6 to Question 10 carry 2 marks each. (iv) Improving his technical skills will guarantee
Question Number: 1 Question Type: MCQ success.
Alexander turned his attention towards India, since he (A) (iii) and (iv) (B) (ii) and (iii)
had conquered Persia. (C) (i), (ii) and (iii) (D) (ii) only
Which one of the statements below is logically valid Solution: Form the given passage only statement (ii)
and can be inferred from the above sentence? and (iii) can be inferred. Whereas, statement (i) is con-
(A) Alexander would not have turned his atten- tradicting the main essence of the passage and (iv) is a
tion towards India and had he not conquered farfetched conclusion.
Persia. Hence, the correct option is (B).
(B) Alexander was not ready to rest on his laurels,
Question Number: 3 Question Type: NAT
and wanted to march to India.
The exports and imports (in crores of Rs.) of a country
(C) Alexander was completely in control of his
from the year 2000 to 2007 are given in the follow-
army and could command it to move towards
ing bar chart. In which year is the combined percentage
India.
increase in imports and exports the highest?
(D) Since Alexander’s kingdom extended to
Indian borders after the conquest of Persia, he Exports Imports
120
was keen to move further. 110
100
Solution: The logically consistent form of the above 90
given statement is implicit only from (A). 80
70
Hence, the correct option is (A). 60
50
Question Number: 2 Question Type: MCQ 40
Most experts feel that in spite of possessing all the 30
technical skills required to be a batsman of the high- 20
10
est order, he is unlikely to be so due to lack of req- 0
uisite temperament. He was guilty of throwing away 2000 2001 2002 2003 2004 2005 2006 2007
his wicket several times after working hard to lay a
strong foundation. His critics pointed out that until he
Solution: From 2005 to 2006, the combined imports
addressed this problem, success at the highest level will
and exports increased by `60 crores. ∴ The combined
continue to elude him.
percentage increase in imports and imports in 2006
Which of the statement(s) below is/are logically valid 60
and can be inferred from the above passage? (over the previous year) was (100) % i.e., (37.5).
160
(i) He was already a successful batsman at the highest This was the maximum combined percentage increase
level. in imports and exports in any year over the given period.
(ii) He has to improve his temperament in order to Hence, the correct Answer is (2006).
become a great batsman.
lviii | GATE 2015 Solved Paper CSIT: Set – 1

Question Number: 4 Question Type: MCQ (B) R-Home, S-Power, P-Defense, Q-Telecom,
T-Finance.
y
(C) P-Home, Q-Power, T-Defense, S-Telecom,
U-Finance.
(D) Q-Home, U-Power, T-Defense, R-Telecom,
(2, 0) x
P-Finance.
Solution: Only option (B) is complying with all the
(0, –1) rules and constrictions.
Hence, the correct option is (B).
Question Number: 6 Question Type: MCQ
Choose the most appropriate equation for the function Extreme focus on syllabus and studying for tests has
drawn as a thick line, in the plot below. become such a dominant concern of Indian students
(A) x = y – |y| (B) x = –(y – |y|) that they close their minds to anything ________ to the
(C) x = y + |y| (D) x = –(y + |y|) requirements of the exam.
(A) related (B) extraneous
Solution: Given,
(C) outside (D) useful
x=0 for y > 0
Solution: The sentence implies that students study
x = – 2y for y ≤ 0
only that which is prescribed within the syllabus and
Going from the options, nothing beyond it. ‘Extraneous’ means ‘not important’.
Choice (A) ⇒ x=0 for y ≥ 0 ‘Outside; cannot be used as ‘to’ is present after the
blank. ‘Outside to’ is ungrammatical. The other choices
x = 2y for y ≤ 0 are irrelevant to the given sentence.
Choice (B) ⇒ x=0 for y ≥ 0 Hence, the correct option is (B).
x = –2y for y ≤ 0 Question Number: 7 Question Type: MCQ
Choice (C) ⇒ x = 2y for y ≥ 0 Select the pair that best expresses a relationship similar
to that expressed in the pair:
x=0 for y ≤ 0 Children: Pediatrician
Choice (D) ⇒ x = –2y for y≥0 (A) Adult: Orthopedist
x=0 for y ≤ 0 (B) Females: Gynecologist
∴ x = –(y − y ) (C) Kidney: Nephrologist
(D) Skin: Dermatologist
Hence, the correct option is (B).
Solution: A pediatrician treats children. In the same
Question Number: 5 Question Type: MCQ
context, a gynecologist treats females. Though a
The head of a newly formed government desires to nephrologist treats kidneys and a dermatologist treats the
appoint five of the six selected members P, Q, R, S, T skin, kidneys and skin are not living beings or humans.
and U to portfolios of Home, Power, Defense, Telecom
and Finance. U does not want any portfolio if S gets Hence, the correct option is (B).
one of the five. R wants either Home or Finance or no
portfolio. Q says that if S gets either Power or Telecom, Question Number: 8 Question Type: MCQ
then she must get the other one. T insists on a portfolio The Tamil version of ______ John Abraham-starrer
if P gets one. Madras Café ______ cleared by the Censor Board with
Which is the valid distribution of portfolios? no cuts last week, but the film’s distributor’s _______
(A) P-Home, Q-Power, R-Defense, S-Telecom, no takers among the exhibitors for a release in Tamil
T-Finance. Nadu _____ this Friday.
 GATE 2015 Solved Paper CSIT: Set – 1 | lix

(A) Mr., was, found, on (B) a, was, found, at Then,

(C) the, was, found, on (D) a, being, find, at S W A N
+3 +3 +3 +3
Solution: The use of ‘the’ shows that only a certain
John Abraham is being referred to ‘Was’ and ‘found’ fit ↓ ↓ ↓ ↓
the next two blanks. ‘On’ is correct over ‘at’. Though, V Z D Q
the last blank can be deleted as well. Hence, the correct option is (B).
Hence, the correct option is (C). Question Number: 10 Question Type: MCQ
Question Number: 9 Question Type: MCQ A function f(x) is linear and has a value of 29 at x = –2
If ROAD is written as URDG, then SWAN should be and 39 at x = 3. Find its value at x = 5.
written as: (A) 59 (B) 45 (C) 43 (D) 35
(A) VXDQ (B) VZDQ Solution: Let f (x) = ax + b where a and b are constants
(C) VZDP (D) UXDQ f (–2) = 29 and f (3) = 39
Solution: R O A D is written as U R D G a (–2) + b = 29 and a (3) + b = 39
R O S D Solving these,
+3 +3 +3 +3
a = 2 and b = 33
↓ ↓ ↓ ↓
⇒ f(x) = 2x + 33
U R D G
∴ f(5) = 2(5) + 33 = 43
Applying the same logic to SWAN
Hence, the correct option is (C).

Computer Science and Information Technology

Number of Questions: 55 Section Marks: 85.0
Question 11 to Question 35 carry 1 mark each and 108

Question 36 to Question 65 carry 2 marks each. = 2 ×1×

1250 × 8
Question Number: 11 Question Type: MCQ V = 20000 km/sec
Consider a CSMA/CD network that transmits data at
Hence, the correct option is (D).
a rate of 100 Mbps (108 bits per second) over a 1 km
(kilometer) cable with no repeaters. If the minimum Question Number: 12 Question Type: NAT
frame size required for this network is 1250 bytes, what The velocity v (in kilometer/minute) of a motorbike
is the signal speed (km/sec) in the cable? which starts from rest is given at fixed intervals of
(A) 8000 (B) 10000 time t (in minutes) as follows:
(C) 16000 (D) 20000 t 2 4 6 8 10 12 14 16 18 20
Solution: The condition for the minimum packet size v 10 18 25 29 32 20 11 5 2 0
in Ethernet (CSMA/CD) is
The approximate distance (in kilometers) rounded to
Transmission delay = Round trip time two places of decimals covered in 20 minutes using
Simpson’s 1/3rd rule is _____.
L d Solution: The velocity V of a motorcycle at fixed
= 2×
B V intervals of time t is given as
B
V=2×d× t 2 4 6 8 10 12 14 16 18 20
L V 10 18 25 29 32 20 11 5 2 0
lx | GATE 2015 Solved Paper CSIT: Set – 1

20 Options (A)
The distance travelled in 20 minutes = ∫ Vdt
256 log2 256 = 6 minutes
t =0
1
By Simpson’s – rule, we have 256 log 256 = 360 seconds
3
360
20
h 256 = = 45 time units
∫ Vdt = ⎡⎣(V0 + V10 ) + 4 (V1 + V3 + V5 + V7 + V9 ) 8
0
3
Option (B)
+ 2 (V2 + V4 + V6 + V8 )⎤⎦ 512 log 512 = 360 seconds
360
Here, h = 2, V0 = Vat t = 0 = 0 (∵ starting from rest) 512 = = 40 time units
9
∴ from (1),
Elements – 64 = 26 = 5 time units
20
2 Elements – 128 = 27 = 10 time units
∫ Vdt = 3 [(0 + 0) + 4(10 + 25 + 32 + 11 + 2) Elements – 256 = 28 = 20 time units
0

+ 2 (18 + 29 + 20 + 5)] Elements – 512 = 29 – 40 time units

Therefore, 512 is the maximum input size of a problem
= 309.33 km that can be solved in 6 minutes.
Hence, the correct Answer is (308 to 310). Hence, the correct option is (B).
Question Number: 13 Question Type: MCQ Question Number: 14 Question Type: MCQ
Assume that a merge-sort algorithm in the worst case Consider the following recursive C function
takes 30 seconds for an input of size 64. Which of the void get (int n)
following most closely approximates the maximum
{
input size of a problem that can be solved in 6 minutes?
if (n < 1) return;
(A) 256 (B) 512
get (n – 1);
(C) 1024 (D) 2048
get (n – 3);
Solution: Time complexity of merge sort is θ(n log n) printf(“%d”, n);
For 64 elements, the algorithm took 30 seconds to sort }
⇒ (n log n) = 30 seconds
If get (6) function is being called in main ( ) then how
(64 log 64) = 30 seconds many times will the get ( ) function be invoked before
returning to the main ( )?
Lets convert the time taken to sort ‘n’ element into
some time units. (A) 15 (B) 25
64 log 64 = 30 (C) 35 (D) 45
30
64 =
log 64
30
⇒ 64 = = 5 time units
6
 GATE 2015 Solved Paper CSIT: Set – 1 | lxi

get (6)

get (5) get (3)

get (2) get (0)

get (4) get (2)

get (1) get (–1)

get (1)
get (3) get (1) get (–1)

get (0) get (–2)

get (0) get (-2)
get (2) get (0) get (0) get (–2)

get (1) get (–1)

get (0) get (–2)

Solution: Total calls: 25

Hence, the correct option is (B).

Question Number: 15 Question Type: NAT Example:

Consider a B+ tree in which the search key is 12 bytes Keys = 2
long, block size is 1024 bytes, record pointer is 10 bytes
long and block pointer is 8 bytes long. The maximum
number of keys that can be accommodated in each non-
leaf node of the tree is ________.
p=3
Solution: Search key = 12 bytes
Block size = 1024 bytes Hence, the correct Answer is (50).
Record pointer = 10 bytes
Question Number: 16 Question Type: MCQ
Block pointer = 8 bytes
Given the function F = P′ + QR, where F is a func-
The order (P) of the internal node in a B−+ tree,
tion in three Boolean variables P, Q and R and P′ = !P,
P ∗ 8 + (P – 1) (12) ≤ 1024 consider the following statements.
8P + 12 P – 12 ≤ 1024 (S1) F = Σ(4,5,6)
(S2) F = Σ(0,1,2,3,7)
20p ≤ 1024 + 12
(S3) F = ∏(4,5,6)
1036 (S4) F = ∏(0,1,2,3,7)
P≤ = 51.8 ≅ 51
20 Which of the following is true?
P = 51 (A) (S1) – False, (S2) – True, (S3) – True, (S4) –
If the order p = 51, then the keys would be 50. False
lxii | GATE 2015 Solved Paper CSIT: Set – 1

(B) (S1) – True, (S2) – False, (S3) – False, (S4) – {

True int x = 1;
(C) (S1) – False, (S2) – False, (S3) – True, (S4) – x += f1( ) + f2 ( ) + f3 ( )
True + f2 ( );
(D) (S1) – True, (S2) – True, (S3) – False, (S4) – printf(“%d”, x);
False return 0;
}
Solution: F = P′ + QR
int f1 () {int x = 25; x++;
The given statements are in canonical form, by con- return x;}
verting F to canonical form. int f2 () {static int x = 50;
F = P′(Q + Q′) (R + R′) + (P + P′)QR x++; return x;}
= P′(QR + Q′R + QR′ + Q′R′) + PQR + P′QR int f3 () {x *= 10; return x};

= P′QR + PQ′R + P′Q R′ + P′Q′R′ + PQR The output of the program is ______.

= ∑ m(0, 1, 2, 3, 7) Solution:
x=x + f1 ( ) + f2 ( )
= πM(4, 5, 6)
only (S2) and (S3) are true. 51 100
f1 ( ) f2 ( ) f3 ( )
Hence, the correct option is (A). 26
x = 25 x = 50 X = x∗ 10 52
Question Number: 17 Question Type: MCQ x=x+1 x=x+1 return (x)
Language L1 is polynomial time reducible to language return (x) return (x)
L2. Language L3 is polynomial time reducible to L2,
which in turn is polynomial time reducible to language
L4. Which of the following is/are true?
(A) if L4 ∈ P, then L2 ∈ P In f 2( ), x is a static variable it is initialized only once
i.e., x = 50 it increments the x with ‘1’. (x = 51). When
(B) if L1 ∈ P or L3 ∈ P, then L2 ∈ P
f 2( ) is called once again, x retains the previous value
(C) L1 ∈ P, if and only if L3 ∈ P
and is incremented.
(D) if L4 ∈ P, then L1 ∈ P and L3 ∈ P
In f 3 ( ), ‘x’ is not declared, but ‘C’ implements static
Solution: L1 → L2 scoping, it takes global value of ‘x’ [which is 10].
L3 → L2 ∴ x = 1 + 26 + 51 + 100 + 52 ⇒ 230
Hence, the correct Answer is (230).
L3 → L4
Question Number: 19 Question Type: NAT
L2 ≤p L4
Consider the following C program
L1 ≤p L2 #include<stdio.h>
Hence, the correct option is (C). int main ( )
Question Number: 18 Question Type: NAT {
static int a[ ] = {10, 20, 30,
Consider the following C program
40, 50};
#include<stdio.h> static int *p[ ] = {a, a+3,
int f1(void); a+4, a+1, a+2};
int f2(void); int **ptr = p;
int f3(void); ptr++;
int x = 10; printf(“%d%d”, ptr-p, **ptr);
}
int main ( ) The output of the program is _______
 GATE 2015 Solved Paper CSIT: Set – 1 | lxiii

Solution: Question Number: 21 Question Type: MCQ

Consider the following policies for preventing dead-
a 10 20 30 40 50
lock in a system with mutually exclusive resources.
I. Processes should acquire all their resources at the
beginning of execution. If any resource is not avail-
able, all resources acquired so far are released.
II. The resources are numbered uniquely, and pro-
cesses are allowed to request for resources only in
increasing resource numbers.
a III. The resources are numbered uniquely, and pro-
cesses are allowed to request for resources only in
decreasing resource numbers.
IV. The resources are numbered uniquely. A process is
ptr will point to (p + 1)
allowed to request only for a resource with resource
after ptr + +
number larger than it’s currently held resources.
Which of the above policies can be used for preventing
ptr deadlock?
(A) Any one of I and III but not II or IV
ptr – p = [pointer Arithmetic] (B) Any one of I, III and IV but not II
∗∗ptr will contain 140 (C) Any one of II and III but not I or IV
∴ it prints 140. (D) Any one of I, II, III and IV
Hence, the correct Answer is (140). Solution: Option I, II, III and IV are deadlock preven-
Question Number: 20 Question Type: MCQ tion policies. Implementing any one of these can make
Which of the following languages are context-free? system deadlock free.
L1 = {ambnanbm | m, n ≥ 1} Hence, the correct option is (D).

L2 = {ambnambn | m, n ≥ 1} Question Number: 22 Question Type: NAT

In the network 200.10.11.144/27, the fourth octet (in
L3 = {ambn | m = 2n + 1} decimal) of the last IP address of the network which
(A) L1 and L2 only (B) L1 and L3 only can be assigned to a host is _______
(C) L2 and L3 only (D) L3 only Solution: Given network 200.10.11.144/27
Solution: L1 = {am bn an bm|m, n ≥ 1} To find the last IP-address of the network
L1 is context free language Set ((32 – 27) = 5) the last 5 bits to ‘1’ in the given
IP-address.
Consider a stack, push the ‘a’ elements followed by ‘b’
element, then for every ‘a’ pop the elements should be 200.10.11.144
‘b’], for every b pop the elements [The element should 200.10.11.100 10000
be ‘a’] Last 5 bits set to 1
L2 = {am bn am bn|m, n ≥ 1} 200.10.11.100 11111
L2 is not context free 200 . 10 . 11 . 159

Two stacks should be maintained for the element count Octet 1 octet 2 octet 3 octet 4
of ‘a’ and ‘b’.
The fourth octet value in the last IP-address is 159, but
L3 = {am bn|m = 2n + 1} last address cannot be assigned to a host hence we have
L3 is context free language. to assign 158 to a host.
Hence, the correct option is (B). Hence, the correct Answer is (158).
lxiv | GATE 2015 Solved Paper CSIT: Set – 1

Question Number: 23 Question Type: NAT Solution: The time slot info for stage 1 – 10001
Consider a network connecting two systems located Time Slot info for stage 2 – 1010
8000 kilometers apart. The bandwidth of the network is Time slot info for stage 3 – 00100
500 × 106 bits per second. The propagation speed of the From the above, the average latency will be 3.
media is 4 × 106 meters per second. It is needed to design
Hence, the correct Answer is (3).
a Go-Back-N sliding window protocol for this network.
The average packet size is 107 bits. The network is to be Question Number: 25 Question Type: MCQ
used to its full capacity. Assume that processing delays Consider the following code sequence having five
at nodes are negligible. Then, the minimum size in bits instructions l1 to l5. Each of these instructions has the
of the sequence number field has to be _______ following format.
packet size L 10 × 106 OP Ri, Rj, Rk
Solution: TT = = = = 0.02 sec
Bandwidth B 500 × 106 Where operation OP is performed on contents of reg-
distance d 8000 × 103 8 × 106 isters Rj and Rk and the result is stored in register Ri.
TP = = = = = 2 sec l1: ADD R1, R2, R3
velocity v 4 × 106 4 × 106
l2: MUL R7, R1, R3
Link utilization is 100% (η = 100)
l3: SUB R4, R1, R5
T 2
a= P = = 100 l4: ADD R3, R2, R4
TT 0.02
l5: MUL R7, R8, R9
W
In Go-Back-N-Protocol, Efficiency = η = Consider the following three statements.
1 + 2a
S1: There is an anti-dependence instruction between
(W = 2n – 1) (η = 100%) instructions l2 and l5
2 −1n
S2: There is an anti-dependence between instructions
η=
1 + 2a l2 and l4
2n − 1 S3: Within an instruction pipeline anti-dependence
1= always creates one or more stalls
1 + 2a
Which one of the above statements is/are correct?
⇒ 1 + 2a = 2n – 1
(A) Only S1 is true
1 + 2(100) = 2n – 1
(B) Only S2 is true
201 + 1 = 2n
(C) Only S1 and S3 are true
2n = 202
(D) Only S2 and S3 are true
2n ≅ 28
n=8 Solution: An anti–dependency between instructions
can also be refereed as WAR hazard. There is no WAR
In sequence number, minimum bit required is 8. between l2 and l5 .There is anti–dependency between l2
Hence, the correct Answer is (8). and l4 as l4 writes R3 which is read by l2.
Question Number: 24 Question Type: NAT An anti–dependency may or may not create a stall.
Consider the following reservation table for a pipeline Hence, the correct option is (B).
having the stages S1, S2 and S3. Question Number: 26 Question Type: MCQ
Time → Consider the following two C code segments. Y and X
1 2 3 4 5 are one and two dimensional arrays of size n and n ×
S1 X X
n respectively, where 2 ≤ n ≤ 10. Assume that in both
code segments, elements of Y are initialized to 0 and
S2 X X
each element X[i] [j] of array X is initialized to i + j.
S3 X Further assume that when stored in main memory all
The minimum average latency (MAL) is ______. elements of X are in same main memory page frame.
 GATE 2015 Solved Paper CSIT: Set – 1 | lxv

Code segment 1: Transaction – id

//initialize elements of Y to 0 Time Instance T1 T2
//initialize elements X[i] [j] of 1 read(A)
X to i + j 2 write(A)
3 read(C)
for (i = 0; i < n; i++) 4 write(C)
Y[i] += X[0] [i]; 5 read(B)
Code Segment 2: 6 write(B)
//initialize elements of Y to 0 7 read(A)
//initialize elements X[i] [j] of 8 commit
X to i + j 9 read(B)

Schedule S
for (i = 0; i < n; i++) Suppose that the transaction T1 fails immediately after
Y[i] += X[i] [0]; time instance 9. Which one of the following statements
Which of the following statements is/are correct? is correct?
S1: Final contents of array Y will be same in both code (A) T2 must be aborted and then both T1 and
segments T2 must be re-started to ensure transaction
S2: Elements of array X accessed inside the for loop atomicity.
shown in code segment 1 are contiguous in main (B) Schedule S is non-recoverable and cannot
memory ensure transaction atomicity.
S3: Elements of array X accessed inside the for loop (C) Only T2 must be aborted and then re-started
shown in code segment 2 are contiguous in main to ensure transaction atomicity.
memory.
(D) Schedule S is recoverable and can ensure
(A) Only S2 is correct atomicity and nothing else needs to be done.
(B) Only S3 is correct
Solution:
(C) Only S1 and S2 are correct
(D) Only S1 and S3 are correct Transaction-Id
T1 T2
Solution: Both the code segments will be initialized
1 read(A)
first [Y to 0, & X[i][j] with i + j] the values of Y[i] will
2 write(A)
be same in both segments as it is assigned i + j values
to Y[i]. 3 read(C)

As the elements of X are in page frame, in code seg- 4 write(C)

ment 1 the elements of X belong to same row, therefore 5 read(B)
they are stored in one frame. 6 write(B)
In code segment 2 the elements of X belong to different 7 read(A)
column, it needs to access different page frames. 8 Commit
Hence, the correct option is (C). 9 read(B)

Question Number: 27 Question Type: MCQ There is one RW-conflict (2 → 7)

Consider the following partial schedule S involving In the RW-conflict, the transaction T1 is performing
two transactions T1 and T2. Only the read and the write write operation, so T1 has to commit first, T2 is per-
operations have been shown. The read operation on forming read operation so it has to commit later.
data item P is denoted by read(P) and the write opera-
⇒ It is not recoverable.
tion on data item P is denoted by write(P)
Hence, the correct option is (B).
lxvi | GATE 2015 Solved Paper CSIT: Set – 1

Question Number: 28 Question Type: MCQ {

If the following system has non-trivial solution, switch(i + k)
px + qy + rz = 0 {
case 1:
qx + ry + pz = 0
case 2: printf
rx + py + qz = 0, (“\n%d”, i + k);
then which one of the following options is TRUE? case 3: printf
(A) p – q + r = 0 or p = q = –r (“\n%d”, i + k);
(B) p + q – r = 0 or p = –q = r default: printf(
(“\n%d”, i + k);
(C) p + q + r = 0 or p = q = r
}
(D) p – q + r = 0 or p = –q = –r }
Solution: Given system of equations is return 0;
px + qy + rz = 0 }
qx + ry + pz = 0 (1) The number of times printf statement is executed is
_______.
rx + py + qz = 0
Solution:
which can be written in matrix form as
j=2∗ 3 / 4 + 2.0 / 5 + 8 / 5;
AX = 0
6 | 4 +
 2.0 | 5
+8|5
⎡p q r⎤ ⎡x⎤ ⎡0 ⎤
Where A = ⎢⎢ q r p ⎥⎥ ; X = ⎢⎢ y ⎥⎥ and O = ⎢⎢0 ⎥⎥
⎢⎣ r p q ⎥⎦ ⎢⎣ z ⎥⎦ ⎢⎣0 ⎥⎦ 1 + 0 + 1
1+0+1
Given (1) has non-trivial solutions
=2
p q r
K = K– (– – j)
⇒ Det A = 0 ⇒ q r p =0 K=0–1
r p q K=–1
⇒ pqr – p3 – q3 + pqr + pqr – r3 = 0 i=0
⇒ p3 + q3 + r3 – 3 pqr = 0 i+k⇒0–1⇒–1
only one print f( ) is executed
⇒ p3 + q3 + r3 = 3pqr
i=1
which is possible only when i + k ⇒ –1 + 1 ⇒ 0
p + q + r = 0 (OR) p = q = r. only one printf( ) is executed
Hence, the correct option is (C). i=2
Question Number: 29 Question Type: NAT i+k⇒2–1⇒1
Consider the following C program: the printf( ) is executed 3 times.
#include<stdio.h> i=3
int main( ) i+k⇒3–1⇒2
{ The printf( ) is executed 3 times
int i, j, k = 0; i=4
j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5; i+k⇒4–1⇒3
k -= --j; the printf( ) is executed 2 times
for (i = 0; i < 5; i ++) ∴ The printf( ) is executed 10 times.
Hence, the correct Answer is (10).
 GATE 2015 Solved Paper CSIT: Set – 1 | lxvii

Question Number: 30 Question Type: MCQ Question Number: 31 Question Type: NAT
⎛ 1⎞ 1 Let G be a connected undirected graph of 100 verti-
If for non-zero x, af(x) + bf ⎜ ⎟ = - 25 where a ≠ b ces and 300 edges. The weight of a minimum spanning
2
⎝ x⎠ x
tree of G is 500. When the weight of each edge of G is
then ∫ f ( x ) dx is
increased by five, the weight of a minimum spanning
1
1 ⎡ 47b ⎤ tree becomes______.
(A)
a − b2
2 ⎢ a (ln 2 − 25) + 2 ⎥ Solution: Vertices = 100
⎣ ⎦
1 ⎡ 47b ⎤ Edges = 300
(B)
a − b2
2 ⎢ a ( 2 ln 2 − 25) − 2 ⎥ Minimum spanning tree weight = 500
⎣ ⎦
In minimum spanning tree, if there are n-vertices there
1 ⎡ 47b ⎤
⎢ a ( 2 ln 2 − 25) + 2 ⎥
(C) will be (n – 1) edges.
a − b2
2
⎣ ⎦ ∴ For 100 vertices, we will have 99 edges in the
1 ⎡ 47b ⎤ minimum spanning tree.
(D)
a − b2
2 ⎢ a (ln 2 − 25) − 2 ⎥ 99 Edges, Weight is 500,
⎣ ⎦
Now each edge weight is increased by 5
⎛ 1⎞ 1
Solution: Given af(x) + b f ⎜ ⎟ = − 25 (1) ⇒ 99 × 5 = 495
⎝ x⎠ x
Total weight = 500 + 495 = 995
1 ⎛ 1⎞
Replacing x by , we have af ⎜ ⎟ + b f(x) Hence, the correct Answer is (995).
x ⎝ x⎠
= x – 25 (2) Question Number: 32 Question Type: NAT
Two hosts are connected via a packet switch with 107 bits
a(1) – b(2) ⇒ per second links. Each link has a propagation delay of 20
⎛ 1⎞ ⎛1 ⎞ microseconds. The switch begins forwarding a packet 35
a2 f(x) + abf ⎜ ⎟ = a ⎜ − 25⎟
⎝ x⎠ ⎝x ⎠ microseconds after it receives the same. If 10000 bits of
⎛ 1⎞ data are to be transmitted between the two hosts using a
abf ⎜ ⎟ + b2 f(x) = b(x – 25) packet size of 5000 bits, the time elapsed between the
⎝ x⎠
––––––––––––––––––––––––––––––––––– transmission of the first bit of data and the reception of
the last bit of the data in microseconds is _______.
⎛1 ⎞
a2 f(x) – b2 f(x) = a ⎜ − 25⎟ − b ( x − 25)
⎝x ⎠ Solution:
⎛a ⎞ Host 1
⇒ (a2 – b2) f(x) = ⎜ − bx ⎟ – (a – b)25
⎝x ⎠ 5000 bits Switch Host 2

1 ⎡a ⎤
⇒ f(x) =
a − b2
2 ⎢ x − bx − ( a − b ) 25⎥ 35
⎣ ⎦

Now
2 2
⎡ 1 ⎛a ⎞⎤
∫ f ( x ) dx = ∫ ⎢ 2 2 ⎜⎝ − bx − ( a − b ) 25⎟⎠ ⎥
1 ⎣a −b
1
x ⎦
2
1 ⎡ b 2 ⎤
=
a − b2
2 ⎢ a ln x − 2 x − ( a − b ) 25 x ⎥
⎣ ⎦1
Transmission Time (TT) = The time taken to put the
1 ⎡ 47b ⎤ packet on line:
= 2 2
a −b ⎢ a (ln 2 − 25) + 2 ⎥
⎣ ⎦ packet size 5000
TT = = = 500 micro seconds
Hence, the correct option is (A). Bandwidth 107
lxviii | GATE 2015 Solved Paper CSIT: Set – 1

Tp = 20 micro seconds Turnaround

Tp = The amount of time taken for the packet to transfer Arrival Burst Completion Time
Process Time Time Time (TAT)
from one end to another.
A 0 3 3 3
1. One packet is kept on line in 500 micro seconds.
B 1 6 9 8
2. Immediately second packet is also kept on line
(Tp = 20 micro seconds of first packet is merged C 4 4 13 9

with TT = 500 micro seconds of second packet) D 6 2 15 9

⇒ 500 micro seconds 29

Average TAT = = 7.25
3. First packet’s, processing delay 35 micro seconds 4
is also merged with TT = 500 micro seconds of
SJF
second packet.
4. Second packet takes TP = 20 micro seconds to Arrival Burst Completion Turnaround
switch (mean while packet 1 will be traversing Time Time Time Time
towards host 2) Process (A.T) (B.T) (C.T) (TAT)
5. At switch, second packet is held for 35 micro A 0 3 3 3
seconds, then sent for TP = 20 micro seconds. B 1 6 9 8
6. Last bit of second packet takes TT = 500 micro C 4 4 15 11
seconds to reach host 2. D 6 2 11 5
Total time = 500 + 500 + 20 + 35 + 20 + 500
= 1575 27
Average TAT = = 6.75
4
Hence, the correct Answer is (1575).
Question Number: 33 Question Type: MCQ A B C D
For the processes listed in the following table, which of 0 3 9 11 15
the following scheduling schemes will give the lowest
average turnaround time? SRTF

Arrival Processing
Process Time Time A A B C C D B

A 0 3 0 1 3 4 6 8 10 15
B 1 6
C 4 4 Process A.T B.T C.T T.A.T
D 6 2 A 0 3 5 3
B 1 6 15 14
(A) First come first serve C 4 4 8 4
(B) Non-preemptive shortest job first D 6 2 10 4
(C) Shortest remaining time
25
(D) Round Robin with quantum value two Average T.A.T = = 6.25
4
Solution:
Round Robin
FCFS
A B A C B D C B
A B C D
0 2 4 5 7 9 11 13 15
0 3 9 12 14
 GATE 2015 Solved Paper CSIT: Set – 1 | lxix

Process A.T. B.T. C.T. T.A.T. Solution:

A 0 3 5 5 Program X:
B 1 6 15 14 Cyclomatic complexity of program X is the number of
C 4 4 13 9 conditions +1.
D 6 2 11 5 There are 2 ‘if’ conditions and 1 ‘while’ condition

33 ∴ program ‘X’ = 4
Average T.A.T. = = 8.25
4 Control flow diagram for program – X:
Shortest remaining first has less average T.A.T.
Hence, the correct option is (C).
Question Number: 34 Question Type: MCQ
Consider three software items: Program-X, Control
Flow Diagram of Program-Y and Control Flow
Diagram of Program-Z as shown below:

Program-X: Control flow diagram Edges = 10

of program-Y: Vertices = 8
Sumcal (int maxint, int value)
{
int result=0, i=0;
if (value < 0)
{
value = –value;
}
while ((i<value) AND (result If condition
<= maxint))
{
i=i+1;
result = result + 1;
}
if (result <= maxint)
{
print (result);
} While condition
else
{
print (”large”);
}
printf (”end of program”);
}

Control flow diagram

of program-Z:
If-else condition:
Control flow diagram
of program-X:

Control flow diagram

of program-Y:

The value of McCabe’s Cyclomatic complexity of Program y:

program-X, Program-Y, and Program-Z respectively
Edges = 10
are
Vertices = 8
(A) 4, 4, 7 (B) 3, 4, 7
Cyclomatic complexity = 10 – 8 + 2 = 4
(C) 4, 4, 8 (D) 4, 3, 8
∴ program ‘Y’ = 4
lxx | GATE 2015 Solved Paper CSIT: Set – 1

Program Z: (C) Not reflexive but symmetric

(D) Neither reflexive nor symmetric
Control flow
E = 10 Solution: The relation R on the set of ordered pairs of
diagram of
V=8
program-X positive integers given by

E=1 R = {((p, q), (r, s))/p – s = q – r}

Consider ((a, b), (a, b))
Control flow
E = 10
diagram of
V=8 ((a, b), (a, b)) ∈ R only if a – b = b – a
program-Y
which is NOT true always
Cyclomatic complexity ∴ R is NOT reflexive (1)
Total number of edges = 10 + 1 + 10 = 21 Let ((a, b), (c, d)) ∈ R
Total number of vertices = 8 + 8 = 16 ⇒ a–d=b–c
⇒ 21 – 16 + 2 = 7 (By definition of R)
⇒ d–a=c–b
∴ program ‘Z’ = 7
⇒ c–b=d–a
Hence, the correct option is (A). ⇒ ((c, d), (a, b)) ∈ R
Question Number: 35 Question Type: MCQ ⇒ R is symmetric (2)
Consider the equation (43)x = (y3)8 where x and y are Hence from (1) and (2), R is NOT reflexive but
unknown. The number of possible solutions is _______. symmetric.
Solution: (43)x = (y3)8 Hence, the correct option is (C).
By converting to decimal system Question Number: 37 Question Type: NAT
4x1 + 3.x0 = y.81 + 3.8° Suppose Xi for i = 1,2,3 are independent and identically
4x + 3 = 8y + 3 distributed random variables whose probability mass
4x = 8y functions are Pr[Xi = 0] = Pr[Xi = 1] = ½ for i = 1,2,3.
Define another random variable Y = X1 X2 ⊕ X3, where
x = 2y
⊕ denotes XOR. Then,
x is base of number system x > 4 Pr[Y = 0|X3 = 0] = ______.
y is number in the number system with base 8, so y < 8.
Solution:
x y
x1 x2 x3 x1 x2 x1 x2 ⊕ x3
6 3
0 0 0 0 0
8 4
0 0 1 0 1
10 5
0 1 0 0 0
12 6
0 1 1 0 1
14 7
1 0 0 0 0
Number of possible solutions = 5 1 0 1 0 1
Question Number: 36 Question Type: MCQ 1 1 0 1 1
Let R be a relation on the set of ordered pairs of positive 1 1 1 1 0
integers such that ((p, q),(r, s)) ∈ R if and only if p – s =
q – r. Which one of the following is true about R? Pr [Y = 0/x3 = 0] is the probability of Y = 0, when x3 = 0
(A) Both reflexive and symmetric from the truth table, x3 = 0, 4 times, and Y = x1 x2 ⊕
x3 = 0 3 times.
(B) Reflexive but not symmetric
 GATE 2015 Solved Paper CSIT: Set – 1 | lxxi

3 if (C[0] = 1)
So Pr[Y = 0/x3 = 0] = = 0.75
4 z = 1 × 2 mod 8 = 2
Hence, the correct Answer is (0.75).
i = 1:-
Question Number: 38 Question Type: NAT z = 22 mod 8 = 4
The total number of prime implicants of the function i = 2
f(w, x, y, z) = Σ(0, 2, 4, 5, 6, 10) is ______.
z = 42 mod 8 = 0
Solution: f(w, x, y, z) = Σm(0, 2, 4, 5, 6, 10) z = (0 × 2)mod 8 = 0
yz i = 3
wx 00 01 11 10 z = 02 mod 8 = 0
z = (0 × 2) mod 8 = 0
00 1 1
z = 0
01 1 1 1 Hence, the correct Answer is (0).
Question Number: 40 Question Type: MCQ
11 Let f(n) = n and g(n) = n(1 + sin n), where n is a posi-
tive integer. Which of the following statements is/are
10 1 correct?
I. f(n) = O(g(n))
II. f(n) = (g(n))
f = w′ xy′ + w′ z′ + x′ yz′ (A) Only I (B) Only II
3 prime implicants (2 pairs, 1 Quad) (C) Both I and II (D) Neither I nor II
Hence, the correct Answer is (3). Solution: f(n) = n
Question Number: 39 Question Type: NAT g(n) = n(1+sin n)
Suppose c = <c[0], …, c[k – 1]> is an array of length n = positive integer
k, where all the entries are from the set {0, 1}. For any
–1 ≤ sin n ≤ 1
positive integers a and n, consider the following pseudo
code. Suppose if we take ‘–1’ in the place of (sin n) then
DOSOMETHING (c, a, n) g(n) = n° = 1
z ← 1 Suppose If we take ‘1’ in the place of (sin n) then
g(n) = n2
for i ← 0 to k – 1
g(n) value keeps changing. So neither I nor II can be
do z ← z2 mod n
correct.
if c[i] = 1
Hence, the correct option is (D).
then z ← (z × a) mod n
return z Question Number: 41 Question Type: MCQ
Consider the following grammar G
If k = 4, c = <1,0,1,1>, a = 2 and n = 8, then the output
S→F|H
of DOSOMETHING(c, a, n) is ______.
F→p|c
Solution:
H→d|c
K = 4; C = <1, 0, 1, 1>; a = 2; n = 8
Where S, F and H are non-terminal symbols, p, d
z = 1
and c are terminal symbols. Which of the following
statement(s) is/are correct?
at i = 0:- S1. LL(1) can parse all strings that are generated using
z = 12 mod 8 = 1 grammar G
lxxii | GATE 2015 Solved Paper CSIT: Set – 1

S2. LR(1) can parse all strings that are generated using {
grammar G char s1[7] = “1234”, *p;
(A) Only S1 p = s1 + 2;
(B) Only S2 *p = ‘0’;
(C) Both S1 and S2 printf(“%s”, s1);
(D) Neither S1 nor S2 }
What will be printed by the program?
Solution:
(A) 12 (B) 120400
S → F|H
(C) 1204 (D) 1034
F → |C
H → d|c Solution:
0 1 2 3
LR(1)
S1 1 2 3/0 4 \0
S S1 → S., $

S1 →. S, $ E S → F., $
S →. F, $
S →. H, $ H
S → H., $
F →. p, $
p
F →. c, $ P
F → p., $
H →. d, $ d P = S1 = 2
H →. c, $
F → d., $ P is a pointer pointing to the 3rd character of S1
c
∗ P = ‘0’;
F → c., $
H → c., $ RR conflict it rewrites the value of S1[2] (‘3’ is replaced with 0)
S1 had ‘1204’, when S1 is printed, it prints 1204.
Hence, the correct option is (C).
The above grammar is having RR conflict therefore it is
Question Number: 43 Question Type: MCQ
not LR(1) grammar.
Suppose U is the power set of the set S = {1,2,3,4,5,6}.
LL(1)
For any T ∈ U, let |T| denote the number of elements in
S→F T and T′ denote the complement of T. For any T, R ∈
S→H U, let T \R be the set of all elements in T which are not
F → p|c in R. Which one of the following is true?
H → d|c (A) ∀ X ∈ U (|X| = |X ′|)
(B) ∃X ∈ U ∃Y ∈ U (|X| = 5, |Y| = 5 and X ∩ Y = ϕ)
First (S) = {p, c, d}
The productions of S → F, S → H will be at (C) ∀X ∈ U ∀Y ∈ U(|X| = 2, |Y| = 3 and X \ Y = ϕ)
M[S, c] (D) ∀X ∈ U ∀Y ∈ U (X \ Y = Y ′ \ X ′)

i.e., at M[S, c] there will be multiple productions. Solution: Given S = {1, 2, 3, 4, 5, 6}

∴ it is not LL(1). U = P(S)
Hence, the correct option is (D). Consider the set X\Y = {x/x ∈ S, x ∈ X and x ∉ Y}
Question Number: 42 Question Type: MCQ = {x/x ∈ S, x ∈ X and x ∉ Y ′}
Consider the following C program segment. = {x/x ∈ S, x ∈ Y ′ and x ∉ X′}
#include <stdio.h> = Y ′\X′, ∀ X ∈ U, ∀ Y ∈ U
int main() Hence, the correct option is (D).
 GATE 2015 Solved Paper CSIT: Set – 1 | lxxiii

Question Number: 44 Question Type: MCQ Question Number: 47 Question Type: MCQ
Consider the relation X(P, Q, R, S, T, U) with the Let # be a binary operator defined as
following set of functional dependencies X # Y = X ′ + Y ′ where X and Y are Boolean variables.
F = { Consider the following two statements.
{P, R} → {S, T} (S1) (P # Q) # R = P # (Q # R)
{P, S, U} → {Q, R} (S2) Q#R=R#Q
} Which of the following is/are true for the Boolean vari-
Which of the following is the trivial functional depend- ables P, Q and R?
ency in F+, where F+ is closure of F? (A) Only S1 is true
(A) {P, R} → {S, T} (B) {P, R} → {R, T} (B) Only S2 is true
(C) {P, S} → {S} (D) {P, S, U} → {Q} (C) Both S1 and S2 are true
Solution: (D) Neither S1 nor S2 are true
Trivial: Solution: X # Y = X ′ + Y ′ = (XY) ′ – this is NAND gate.
If A → B
(S1) = (P # Q) # R ≠ P # (Q # R)
B has to be subset of A
NAND gate does not obey associative law
{P, S} → {S}
{S} is subset of {P, S} ((PQ) ′.R) ′ ≠ (P.(QR) ′) ′
Hence, the correct option is (C). PQ + R ′ ≠ P ′ + QR
(S2) Q # R = R # Q
Question Number: 45 Question Type: MCQ
The maximum number of processes that can be in Commutative law is, true for NAND gate
Ready state for a computer system with n CPUs is (QR) ′ = (RQ) ′
(A) n (B) n2 Q′ + R′ = R′ + Q′
(C) 2 n
(D) Independent of n (S2) is true.
Hence, the correct option is (B).
Solution: The maximum number of processes that are
running will be ‘n’, with each process assigned to CPU, Question Number: 48 Question Type: NAT
but the number of processes present in ready queue is Consider a software project with the following
independent of the number of CPU’s. information domain characteristics for calculation of
Hence, the correct option is (D). function point metric.
Question Number: 46 Question Type: MCQ Number of external inputs (I) = 30
Among simple LR (SLR), canonical LR, and look- Number of external outputs (O) = 60
ahead LR (LALR), which of the following pairs iden- Number of external inquiries (E) = 23
tify the method that is very easy to implement and the Number of files (F) = 08
method that is the most powerful, in that order? Number of external interfaces (N) = 02
(A) SLR, LALR It is given that the complexity weighting factors for I,
(B) Canonical LR, LALR O, E, F and N are 4, 5, 4, 10 and 7, respectively. It is
(C) SLR, canonical LR also given that, out of fourteen value adjustment factors
that influence the development effort, four factors are
(D) LALR, canonical LR not applicable, each of the other four factors has value
Solution: CLR is more powerful among all the parsers. 3, and each of the remaining factors has value 4. The
SLR parser is easy to implement, as it works on only computed value of function point metric is ______.
LR(0) items, CLR parser works on LR(0) items and Solution: Number of external inputs (I) = 30
their corresponding look – ahead’s.
Number of external outputs (O) = 60
Hence, the correct option is (C).
Number of external enquires (E) = 23
lxxiv | GATE 2015 Solved Paper CSIT: Set – 1

Number of files (F) = 08 Solution: <base href: “http: //www.yourname.com/”>

Number of external interfaces (N) = 2 It reflects to the given data;
The weighting factors for I, O, E, F and N are 4, 5, 4, Hence, the correct option is (B).
10 and 7.
Question Number: 50 Question Type: MCQ
Total Count = 30 × 4 + 60 × 5 + 23 × 4 + 8 × 10 + 2 × 7
Consider the following statements
= 120 + 300 + 92 + 80 + 14
I. TCP connections are full duplex
= 606
II. TCP has no option for selective acknowledgement
Function Point = Total Count ∗ EAF III. TCP connections are message streams
(A) Only I is correct
Effort adjustment factor (EAF) = 0.65 + 0.01 ∗ Σfi (B) Only I and III are correct
EAF = 0.65 + 0.01 ∗ Σfi (C) Only II and III are correct
Σfi = sum of the fourteen adjustment factors (D) All of I, II and III are correct
Out of 14, we will consider only 10 [given in problem, Solution: TCP connections are full duplex.
4 are neglected] Hence, the correct option is (A).
Σfi = 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 6 Question Number: 51 Question Type: MCQ
Σfi = 4 × 3 + 6 × 4 n
Consider the equality ∑ i 3 = X and the following
= 12 + 24 choices for X i=0

= 36 I. θ(n4) II. θ(n5)

EAF = 0.65 + 0.01 × 36
5
III. O(n ) IV. (n3)
The equality above remains correct if X is replaced by
= 1.01
(A) Only I
FP = 606 ∗ 1.01
(B) Only II
= 612.06 (C) I or III or IV but not II
Hence, the correct Answer is (612 to 613). (D) II or III or IV but not I
n
Question Number: 49 Question Type: MCQ
In a web server, ten web pages are stored with the
Solution: ∑ i3
i=0
URLs of the form http://www.yourname.com/var.html;
⇒ 03 + 13 + 23 + 33 + 43 + … + n3
where, var is a different number from 1 to 10 for each
web page. Suppose, the client stores the web page with ⇒ 13 + 23 + … + n3
var = 1 (say W1) in local machine, edits and then tests. It is sum of cubes of 1st ‘n’ natural numbers
Rest of the web pages remain on the web server. W1
n2 ( n + 1)
2
contains several relative URLs of the form ‘var.html’ ⇒
referring to the other web pages. Which one of the fol- 4
n2 ( n + 1)
2
lowing statements needs to be added in W1, so that all
It is θ(n4) as n4 ≤ ≤ 4n4
the relative URLs in W1 refer to the appropriate web 4
pages on the web server? n ( n + 1) 2
2

(A) <a href:http://www.yourname.com/”, href: It is O(n5) as ≤ C n5

4
“var.html”> (C = constant, C > 0)
(B) <base href:http://www.yourname.com/”> n2 ( n + 1)
2

(C) <a href:http://www.yourname.com/”> It is (n3) as ≥ n3

4
(D) <base href:http://www.yourname.com/”, But it is not θ(n5)
range: “var.html”> Hence, the correct option is (C).
 GATE 2015 Solved Paper CSIT: Set – 1 | lxxv

Question Number: 52 Question Type: NAT ⎡ x1 ⎤

Consider a binary tree T that has 200 leaf nodes. ⎢ ⎥
Let X = ⎢ x2 ⎥ be an Eigen vector of A corresponding to
Then, the numbers of nodes in T that have exactly two
⎢⎣ x3 ⎥⎦
children are ______.
the Eigen value λ = 1
Solution: Let us consider the following Trees.
⇒ (A – λI) X = 0
⇒ (A – I)X = 0
⎡0 −1 2⎤ ⎡ x1 ⎤ ⎡0 ⎤
⇒ ⎢0 0 0 ⎥ ⎢ x ⎥ = ⎢0 ⎥
⎢ ⎥ ⎢ 2⎥ ⎢ ⎥
4 – leaves ⎢⎣1 2 0 ⎥⎦ ⎢⎣ x3 ⎥⎦ ⎣⎢0 ⎥⎦
(3 – nodes has exactly 2 children)
⇒ – x2 + 2x3 = 0
x
⇒ x3 = 2
2
and x1 + 2x2 = 0
2 – leaves ⇒ x1 = –2x2
(1 – node has exactly 2 children)
Let x2 = k, where K is arbitrary
∴ 200 leaf nodes ⇒ 199 nodes will have exactly
k
2 – children ∴ x1 = – 2k and x3 =
Hence, the correct Answer is (199). 2
∴ The Eigen vector of A corresponding to the Eigen
Question Number: 53 Question Type: NAT
Given a hash table T with 25 slots that stores 2000 ⎡ ⎤
⎢ −2k ⎥ ⎡ −4α ⎤
elements, the load factor ∝ for T is _______ . ⎢ ⎥
value λ = 1 is X = ⎢ k ⎥ ⇒ = ⎢⎢ 2α ⎥⎥ ,
Solution: ⎢ k ⎥ ⎢⎣ α ⎥⎦
Load factor =
Number of elements 2000
= = 80 ⎢ ⎥
slots 25 ⎣ 2 ⎦
Hence, the correct Answer is (80). where k = 2 α , α being arbitrary

Question Number: 54 Question Type: MCQ ⎡ −4 ⎤

= α ⎢⎢ 2 ⎥⎥
⎡1 −1 2⎤
⎢⎣ 1 ⎥⎦
In the given matrix ⎢⎢0 1 0 ⎥⎥ , one of the Eigen
Hence, the correct option is (B).
⎢⎣1 2 1 ⎥⎦
values is 1. The eigenvectors corresponding to the Question Number: 55 Question Type: MCQ

( )
−x
Eigen value 1 are 2 e
The value of limx→∞ 1 + x is
(A) {∞(4, 2, 1)|∞ ≠ 0, ∞ ∈ R} 1
(A) 0 (B)
(B) {∞(–4, 2, 1)|∞ ≠ 0, ∞ ∈ R} 2
(C) {∞( 2 , 0, 1)|∞ ≠ 0, ∞ ∈ R} (C) 1 (D) ∞
( )
e− x
(D) {∞(– 2 , 0, 1)|∞ ≠ 0, ∞ ∈ R} Solution: Let y = Lim 1 + x 2
x →∞
⎡1 −1 2⎤ ⎛
( ) ⎞
e− x
⇒ ln y = ln ⎜ lim 1 + x 2
Solution: Let A = ⎢⎢0 1 0 ⎥⎥ ⎝ x →∞ ⎟⎠
⎢⎣1 2 1 ⎥⎦ ⎡ ⎛ ⎞⎤
( )
e− x
= lim ⎢ln ⎜ 1 + x 2 ⎟⎠ ⎥
Given λ = 1 is an eigen value of A. x →∞ ⎣ ⎝ ⎦
lxxvi | GATE 2015 Solved Paper CSIT: Set – 1

⇒ x →∞ ⎣
(
= lim ⎡e − x ln 1 + x 2 ⎤
⎦ ) (A)
(B)
The result is head
The result is tail

= lim ⎢
(
⎡ ln 1 + x 2 ) ⎤⎥ (C) If the person is of Type 2, then the result is tail
x →∞ ⎢ ex ⎥ (D) If the person is of Type 1, then result is tail
⎣ ⎦
Solution: Let us assume that the person is of Type 1 –
⎡ 2x ⎤
( )
a truth teller. His statement is ‘The result of the toss is
⎢ 1+ x 2 ⎥ head if and only if I am telling the truth.’ We can sym-
⇒ = lim ⎢ ⎥
x →∞ ⎢ ex ⎥ bolize this as S: ‘p if q’.
⎢⎣ ⎥⎦ S is true, q is true.
(By L’Hospitals Rule) ∴ p is true.
⎡ ⎤ Let us assume that the person is of Type 2 – a liar.
⎢1 2 x ⎥ His statement is S: ‘p iff q’
= lim ⎢ x . ⎥
x →∞ ⎢ e ⎛ 1 ⎞⎥ S is false, q is false.
⎢ ⎜⎝1 + 2 ⎟⎠ ⎥
⎣ x ⎦ ∴ p has to be true.
⇒ ln y = 0 In either case, P is true, the result of the toss is head.
⇒ y = e0 = 1 Hence, the correct option is (A).

( )
e− x
⇒ lim 1 + x 2 =1 Question Number: 58 Question Type: MCQ
x →∞
While inserting the elements 71, 65, 84, 69, 67, 83
Hence, the correct option is (C). in an empty binary search tree (BST) in the sequence
shown, the element in the lowest level is
Question Number: 56 Question Type: NAT
(A) 65 (B) 67 (C) 69 (D) 83
The number of 4 digit numbers having their digits in
non-decreasing order (from left to right) constructed by 71
using the digits belonging to the set {1, 2, 3} is _____.
Solution: Following are the 4 digit numbers having 65 84
their digits in non-decreasing order (from left to right)
69 83
constructed by using the digits 1, 2 and 3.
1111 1122 1222 1333 2233
67
1112 1123 1223 2222 2333
1113 1133 1233 2223 3333 Solution: The element in the lowest level is 67.
∴ The number of such 4 digit numbers = 15. Hence, the correct option is (B).
Hence, the correct Answer is (15). Question Number: 59 Question Type: MCQ
Question Number: 57 Question Type: MCQ The result of evaluating the postfix expression 10 5 +
In a room there are only two types of people, namely 60 6 / * 8 – is
Type 1 and Type 2. Type 1 people always tell the truth (A) 284 (B) 213 (C) 142 (D) 71
and Type 2 people always lie. You give a fair coin to a
Solution:
person in that room, without knowing which type he
is from and tell him to toss it and hide the result from 10 5 + 60 6 / ∗ 8 –
you till you ask for it. Upon asking, the person replies + 6 / ∗ –
the following 5 60 60 10 8
‘The result of the toss is head if and only if I am telling
10 15 15 15 150 142
the truth.’
Which of the following options is correct? Result: 142
Hence, the correct option is (C).
 GATE 2015 Solved Paper CSIT: Set – 1 | lxxvii

Question Number: 60 Question Type: MCQ

T4 A4 200 ≥ 100
Consider the following relation
200
Cinema (theater, address, capacity)
Which of the following options will be needed at the 150
end of the SQL QUERY? ∴ A4 is retrieved
200
SELECT P1.address
FROM Cinema P1 Option (A) always finds the addresses of theaters with
such that it always finds the addresses of theaters with maximum capacity.
maximum capacity? Hence, the correct option is (A).
(A) WHERE P1.capacity >= All (select P2. Question Number: 61 Question Type: MCQ
Capacity from Cinema P2)
Consider the following array of elements
(B) WHERE P1.capacity >= Any (select P2.
Capacity from Cinema P2) <89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100>
(C) WHERE P1.capacity > All (select max(P2. The minimum number of interchanges needed to con-
capacity) from Cinema P2) vert it into a max-heap is
(D) WHERE P1.capacity > Any (select max(P2. (A) 4 (B) 5
capacity) from Cinema P2) (C) 2 (D) 3
Solution: Consider the Relation cinema, with some Solution:
sample tuples:
89 10
Theater Address Capacity
T1 A1 100 19 10 19 89
T2 A2 200 ⇒
T3 A3 150 17 12 50 2 17 12 50 2
T4 A4 200
5 7 11 6 9 15 5 7 11 69 15
P1 capacity ≥ ALL (P2. Capacity) (Inter change 100 and 89)
100
T1 A1 100 ≥ ∴ 3 Interchanges are required to convert it into a max
200 – Heap.
Hence, the correct option is (D).
∴ A1 is not retrieved 150
Question Number: 62 Question Type: MCQ
200
Two processes X and Y need to access a critical section.
T2 A2 200 ≥ 100 Consider the following synchronization construct used
by both the processes.
200

∴ A2 is retrieved 150 Process X Process Y

/* other code /* other code
200
for process X */ for process Y */
while (true) while (true)
T3 A3 150 ≥ 100
{ {
200 varP = true; varQ = true;
150 while(varQ == while (varP ==
∴ A3 is not retrieved true) true)
200
lxxviii | GATE 2015 Solved Paper CSIT: Set – 1

{ { Y are in critical section which violates mutual exclu-

sion principle. There is no deadlock between process X
/* /*
and Y with these solution.
Critical Section Critical Section
Hence, the correct option is (A).
*/ */
varP = false; varQ = false; Question Number: 63 Question Type: MCQ
} } Let L be the language represented by the regular
} } expression Σ* 0011 Σ* where Σ = {0, 1}. What is the
minimum number of states in a DFA that recognizes L
/* other code /* other code
(complement of L)?
for process X */ for process Y */
(A) 4 (B) 5
Here, varP and varQ are shared variables and both are (C) 6 (D) 8
initialized to false. Which one of the following state-
ments is true? Solution: The language ‘L’ accepts all the strings with
the substring 0011.
(A) The proposed solution prevents deadlock but
fails to guarantee mutual exclusion. The DFA for language ‘L’ is
(B) The proposed solution guarantees mutual 1 0 0, 1
exclusion but fails to prevent deadlock.
0 0 1 1
(C) The proposed solution guarantees mutual A B C D E
exclusion and prevents deadlock.
1 0
(D) The proposed solution fails to prevent dead-
lock and fails to guarantee mutual exclusion.
The DFA for L will be
Solution:
1 0
Process X Process Y 0, 1
while (true) while(true) 0 0 1 1
A B C D E
{ {
1. var P = true; 1. var Q = true; 1 0
2. while (var Q 2. while(varP =
= = true) = true) Number of states for L is 5.
{ { Hence, the correct option is (B).
/* critical /*critical
Question Number: 64 Question Type: NAT
section”/ section */
Consider a software program that is artificially seeded
var P = varQ =
with 100 faults. While testing this program, 159 faults
false; false;
are detected, out of which 75 faults are from those
} } artificially seeded faults. Assuming that both real and
} } seeded faults are of same nature and have same distri-
bution, the estimated number of undetected real faults
The process X has executed instruction (1) and got is _________.
preempted and given chance to process Y, simi-
lar to process X it executes instruction (1) and got Solution: Number of artificial seeds = 100 faults
preempted, given chance to process X. Process X exe- Number of faults detected (artificial) = 75
cutes (2) instruction and enters into critical section, and Number of faults detected = 159
got preempted when it is in critical section and given Number of real faults = 159 – 75
chance to process Y. Process Y executes (2) instruction
= 84
and enters into critical section in which process X and
 GATE 2015 Solved Paper CSIT: Set – 1 | lxxix

As the real and seeded faults are of same nature then Solution: Given,
1
number of undetected real faults = × 84 Block size = 24 B
3 So word offset = 4 bits
= 28 Number of lines = 212 so line field length = 12 bits
Hence, the correct Answer is (28). Main memory address is (E201F)16 and main memory
Question Number: 65 Question Type: MCQ has 20–bits length address:
Consider a machine with a byte addressable main
TAG Lines Offset
memory of 220 bytes, block size of 16 bytes and a direct
mapped cache having 212 cache lines. Let the addresses In the address last 4 bits will be offset that is F
of two consecutive bytes in main memory be (E201F)16
Next 12 bits from and will be line field that is 201 and
and (E2020)16. What are the tag and cache line address
remaining bits, tag as E.
(in hex) for main memory address (E201F)16?
Hence, the correct option is (A).
(A) E, 201 (B) F, 201
(C) E, E20 (D) 2, 01F