GATE 2017(set02)
Question 1 
The representation of the value of a 16bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is
136251  
736251  
571247  
136252 
Each hexadecimal digit is equal to a 4bit binary number. So convert
X = (BCA9)_{16} to binary
Divide the binary data into groups 3 bits each because each octal digit is represented by 3bit binary number.
X = (001 011 110 010 101 001)_{2}
Note: Two zeroes added at host significant position to make number bits of a multiple of 3 (16 + 2 = 18)
X = (136251)_{8}
Question 2 
P→(ii), Q→(iv), R→(i), S→(iii)  
P→(ii), Q→(i), R→(iv), S→(iii)  
P→(ii), Q→(iv), R→(iii), S→(i)  
P→(iii), Q→(iv), R→(i), S→(ii) 
⇾ A variable located in Data Section of memory
P→(ii), Q→(iv), R→(i), S→(iii)
Question 3 
Match the algorithms with their time complexities:
Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ(n^{2}) (Q) Binary search given n stored numbers (ii) Θ(n log n) (R) Heap sort given n numbers at the worst case (iii) Θ(2^{n}) (S) Addition of two n×n matrices (iv) Θ(log n)
P→(iii), Q→(iv), R→(i), S→(ii)  
P→(iv), Q→(iii), R→(i), S→(ii)  
P→(iii), Q→(iv), R→(ii), S→(i)  
P→(iv), Q→(iii), R→(ii), S→(i) 
→ Tower of Hanoi with n disks takes θ(2^{n}) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^{n}1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log_{2} n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n^{2})
Question 4 
Let L_{1}, L_{2} be any two contextfree languages and R be any regular language. Then which of the following is/are CORRECT?
I, II and IV only  
I and III only  
II and IV only  
I only 
CFL is not closed under complementation.
So L_{1} compliment may or may not be CFL. Hence is Context free, is a false statement.
L_{1} – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L_{1} ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L_{1}∩R is context free.
CFL is not closed under INTERSECTION, so L_{1} ∩ L_{2} may or may not be CFL and hence IV^{th} is false.
Question 5 
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:
P→(ii), Q→(iii), R→(iv), S→(i)  
P→(ii), Q→(i), R→(iii), S→(iv)  
P→(iii), Q→(iv), R→(i), S→(ii)  
P→(i), Q→(iv), R→(ii), S→(iii) 
Token stream is forwarded as input to Syntax analyzer which produces syntax tree as output. So, S → (ii).
Syntax tree is the input for the semantic analyzer, So P → (iii).
Intermediate representation is input for Code generator. So R → (i).
Question 6 
Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than Canonical LR.
I only  
II only  
III only  
II and III only 
The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
Question 7 
Which of the following is/are shared by all the threads in a process?

I. Program counter
II. Stack
III. Address space
IV. Registers
I and II only  
III only  
IV only  
III and IV only 
A process, in the simplest terms, is an executing program.
One or more threads run in the context of the process.
A thread is the basic unit to which the operating system allocates processor time.
A thread can execute any part of the process code, including parts currently being executed by another thread.
Each thread has its own stack, register and PC.
So here address space that is shared by all thread for a single process.
Question 8 
In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed?

I. Contiguous
II. Linked
III. Indexed
I and III only  
II only  
III only  
II and III only 
Advantage:
i) Both sequential and direct access is possible.
ii) Extremely fast.
Disadvantage:
i) Suffers from both internal and external fragmentation.
ii) Increasing file size is difficult, because it depends on the availability of contiguous memory at a particular instance.
→ Linked list allocation:
Advantage:
i) Flexible in terms of size.
ii) Does not suffers from external fragmentation.
Disadvantage:
i) Allocation is slower.
ii) Does not support random or direct access.
iii) Pointers require some extra overhead.
→ Indexed allocation:
Advantage:
i) Support direct access, so provides fast access to the file blocks.
ii) No external fragmentation.
Disadvantage:
i) The pointer overhead for indexed allocation is greater than linked allocation.
ii) Inefficient in terms of memory utilization.
Question 9 
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 linkstate routing
Which of the statements above are CORRECT?
I and IV only  
I, II and III only  
I, II and IV only  
II, III and IV only 
RIP is one of the oldest DVR protocol which employ the hop count as a routing metric.
II: RIP packets are sent using UDP. “TRUE”
RIP uses the UDP as its transport protocol, and is assigned the reserved port no 520.
III: OSPF packets are sent using TCP. “FASLE”
OSPF encapsulates its data directly into IP Packets and does not use either TCP or UDP.
IV: OSPF operation is based on link state routing. “TRUE”
OSPF is a routing protocol which uses link state routing (LSR) and works within a single autonomous system.
Hence correct is answer “C”.
Question 11 
Let p, q, r denote the statements “It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by
(¬p ∧ r) ∧ (¬r → (p ∧ q))  
(¬p ∧ r) ∧ ((p ∧ q) → ¬r)  
(¬p ∧ r) ∨ ((p ∧ q) → ¬r)  
(¬p ∧ r) ∨ (r → (p ∧ q)) 
q: It is cold
r: It is pleasant
“If it is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold.”
We can divide the statement into two parts with “Conjunction”.
i.e., ¬r→(p∧q) ⇾(2)
From (1) & (2), the given statement can be represented as
Question 12 
Given the following binary number in 32bit (single precision) IEEE754 format:
The decimal value closest to this floatingpoint number is
1.45 × 10^{1}  
1.45 × 10^{1}  
2.27 × 10^{1}  
2.27 × 10^{1} 
For singleprecision floatingpoint representation decimal value is equal to (1)^{5} × 1.M × 2^{(E127)}
S = 0
E = (01111100)_{2} = (124).
So E – 127 =  3
1.M = 1.11011010…0
= 2^{0} + 2^{(1)} + 2^{(1)} + 2^{(4)} + 2^{(5)} + 2^{(7)}
= 1+0.5+0.25+0.06+0.03+0.007
≈ 1.847
(1)^{5} × 1.M × 2^{(E127)}
= 1^{0} × 1.847 × 2^{3}
≈ 0.231
≈ 2.3 × 10^{1}
Question 13 
A circular queue has been implemented using a singly 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 operations 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.
I only  
II only  
Both I and II  
Neither I nor II 
2. Next pointer of rear points to the front node.
So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
Question 14 
Consider the following function implemented in C:
void printxy (int x, int y) { int *ptr; x = 0; ptr = &x; y = *ptr; *ptr = 1; printf("%d,%d",x,y); }
The output of invoking printxy(1, 1) is
0, 0  
0, 1  
1, 0  
1, 1 
{
int *ptr;
x = 0;
ptr = &x;
y = *ptr;
*ptr = 1;
}
printxy (1, 1)
Question 15 
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?
MNOPQR  
NQMPOR  
QMNROP  
POQNMR 
(Do it by option Elimination)
(a) MNOPQR – MNO is not the proper order R must come in between.
(b) NQMPOR – QMP is not the order O is the child of N.
(C) QMNROP – M is not the child of Q, so QMN is false.
(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).
Question 16 
Identify the language generated by the following grammar, where S is the start variable.
S → XY X → aXa Y → aYbϵ
{a^{m} b^{n} │ m ≥ n, n > 0}  
{a^{m} b^{n} │ m ≥ n, n ≥ 0}  
{a^{m} b^{n} │ m > n, n ≥ 0}  
{a^{m} b^{n} │ m > n, n > 0} 
So the production S→XY can generate any number of a’s (≥1) in the beginning (due to X) and then Y will generate equal number of a’s and b’s.
So, the number of a’s will always be greater than number of b’s and number of b’s must be greater than or equal to 0 (as Y → ϵ, so number of b’s can be zero also).
Hence the language is {a^{m} b^{n}│m>n,n≥0}.
Question 17 
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?
Relationship R is onetomany and the participation of A in R is total.  
Relationship R is onetomany and the participation of A in R is partial.  
Relationship R is manytoone and the participation of A in R is total.  
Relationship R is onetomany and the participation of A in R is partial. 
The relational table for R be merged that of A, if the relationship R is Manytoone and the participation of A in R is total.
Question 18 
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 statement 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.
I only  
II only  
Both I and II  
Neither I nor II 
I. A connected UDP socket can be used to communicate with only one peer.
A DNS client can be configured to use one or more servers, normally by listing the IP addresses of the servers in the file /etc/resolv.conf.
If a single server is listed, the client can call connect, but if multiple servers are listed the client cannot call connect.
II. A process with a connected UDP socket can call connect function again for that socket for one of two reasons:
(a) To specify a new IP address and port.
(b) To unconnect the socket.
Hence, the correct answer is (B).
Question 19 
In table T1, P is the primary key and Q is the foreign key referencing R in table T2 with ondelete cascade and onupdate cascade. In table T2, R is the primary key and S is the foreign key referencing P in table T1 with ondelete set NULL and onupdate 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 _________.
0  
1  
2  
3 
Therefore, no. of additional records deleted from the table T1 is 0 (zero).
Question 20 
The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is _________.
9  
10  
11  
12 
In IPv4 header, 40 bytes are reserved for OPTIONS.
For Record Route to stores, 1 byte is used to store type of option, 1 byte for length and 1 byte for pointer. Out of 40 bytes, 37 bytes are left.
Each IP4 address takes 32 bits or 4 bytes.
Therefore, it can store at most floor (37/4) = 9 router addresses.
Hence correct answer is 9 router address.
Question 21 
Consider the set X = {a,b,c,d e} under the partial ordering

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.
The minimum number of ordered pairs that need to be added to R to make (X,R) a lattice is _________.
0  
1  
2  
3 
As per the definition of lattice, each pair should have GLB, LUB.
The given ‘R’ has GLB, LUB for each and every pair.
So, no need to add extra pair.
Thus no. of required pair such that Hasse diagram to become lattice is “0”.
Question 22 
2  
3  
4  
5 
R_{2}→R_{2}+R_{1}
The number of nonzero rows of P + Q = 2,
So Rank = 2
Note: “Rank” is the number of independent vectors.
Method1:
Each vector is a row in matrix.
Echelon form of a matrix has no. of zeroes increasing each rows.
The total nonzero rows left give the rank.
Method2:
Find determinant of matrix, for 3×5, if determinant is ‘0’, the max rank can be 2.
If determinant of any n×n is nonzero, then rows proceed with (n1)×(n1).
Question 23 
G is an 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 ___________.
16  
17  
18  
19 
Degree of each vertex ≥ 3
v = 2E
The relation between max and min degree of graph are
m ≤ 2E / v ≤ M
Given minimum degree = 3
So, 3 ≤2 E / v
3v ≤ 2E
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
Question 24 
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=________.
8  
9  
10  
11 
Generally if a, b are roots.
(x  a)(x  b) = 0
x^{2}  (a + b)x + ab = 0
Given that x=5, x=6 are roots of (1)
So, a + b = 13
ab=36 (with same base ‘b’)
i.e., (5)_{b} + (6)_{b} = (13)_{b}
Convert them into decimal value
5_{b} = 5_{10}
6_{10} = 6_{10}
13_{b} = b+3
11 = b+3
b = 8
Now check with ab = 36
5_{b} × 6_{b} = 36_{b}
Convert them into decimals
5_{b} × 6_{b} = (b×3) + 6_{10}
30 = b × 3 + 6
24 = b × 3
b = 8
∴ The required base = 8
Question 25 
The minimum possible number of a deterministic finite automation that accepts the regular language L = {w_{1}aw_{2}  w_{1}, w_{2} ∈ {a,b}*, w_{1} = 2,w_{2} ≥ 3} is _________.
8  
9  
10  
11 
So we have four possibilities of w_{1} = {aa, ab, ba, bb}.
w_{2}  ≥ 3 means the w_{2} will have at least three length string from {a,b}.
w_{2} will have {aaa, aab, aba, abb, baa, bab, bba, bbb, ……….}
So, the required DFA is
Question 26 
Probability that ‘P’ applies for the job given that Q applies for the job = P(p/q) = 1/2 ⇾ (2)
Probability that ‘Q’ applies for the job, given that ‘P’ applies for the job = P(p/q) = 1/3 ⇾ (3)
Bayes Theorem:
(P(A/B) = (P(B/A)∙P(A))/P(B) ; P(A/B) = P(A∩B)/P(B))
⇒ P(p/q) = (P(q/p)∙P(p))/p(q)
⇒ 1/2 = (1/3×1/4)/p(q)
p(q) = 1/12×2 = 1/(6) (P(q) = 1/6) ⇾ (4)
From Bayes,
P(p/q) = (P(p∩q))/(P(q))
1/2 = P(p∩q)/(1⁄6)
(p(p∩q) = 1/12)
We need to find out the “probability that ‘P’ does not apply for the job given that q does not apply for the job = P(p'/q')
From Bayes theorem,
P(p'/q') = (P(p'∩q'))/P(q') ⇾ (5)
We know,
p(A∩B) = P(A) + P(B)  P(A∪B)
also (P(A'∩B') = 1  P(A∪B))
P(p'∩q') = 1  P(p∪q)
= 1  (P(p) + P(q)  P(p∩q))
= 1  (P(p) + P(q)  P(p) ∙ P(q))
= 1  (1/4 + 1/6  1/12)
= 1  (10/24  2/24)
= 1  (8/24)
= 2/3
(P(p'∩q') = 2/3) ⇾ (6)
Substitute in (5),
P(p'⁄q') = (2⁄3)/(1P(q)) = (2⁄3)/(11/6) = (2⁄3)/(5⁄6) = 4/5
(P(p'/q') = 4/5)
Question 27 
If w, x, y, z are Boolean variables, then which one of the following is INCORRECT?
wx + w(x + y) + x(x + y) = x + wy  
(w + y)(wxy + wyz) = wxy + wyz 
wx + w(x + y) + x(x + y)
= (wx + wx) + wy + (x + xy)
= wx + wy + x(1 + y)
= wx + wy + x
= (w + 1)x + wy
= x + wy
OptionB:
OptionC:
OptionD:
(w + y)(wxy + wyz) = wxy + wyz + wxy + wyz = wxy + wyz
Question 28 
Given f(w,x,y,z) = Σ_{m}(0,1,2,3,7,8,10) + Σ_{d}(5,6,11,15), where d represents the don’tcare condition in Karnaugh maps. Which of the following is a minimum productofsums (POS) form of f(w,x,y,z)?
KMap for the function f is
Consider maxterms in Kmap to represent function in productofsums (POS) form
f(w,x,y,z) = (w' + z')(x' + z)
Question 29 
In a twolevel cache system, the access times of L_{1} and L_{2} caches are 1 and 8 clock cycles, respectively. The miss penalty from the L_{2} cache to main memory is 18 clock cycles. The miss rate of L_{1} cache is twice that of L_{2}. The average memory access time (AMAT) of this cache system is 2 cycles. The miss rates of L_{1} and L_{2} respectively are:
0.111 and 0.056  
0.056 and 0.111  
0.0892 and 0.1784  
0.1784 and 0.0892 
AMAT = (L_{1} hit rate)*(L_{1} access time) + (L_{1} miss rate)*(L_{1} access time + L_{1} miss penalty)
= L_{1} hit rate * L_{1} access time + L_{1} miss rate * L_{1} access time + L_{1} miss rate * L_{1} miss penalty
We can write,
L_{1} miss rate = 1  L_{1} hit rate
AMAT = L_{1} hit rate * L_{1} access time + (1  L_{1} hit rate) * L_{1} access time + L_{1} miss rate * L_{1} miss penalty
By taking L_{1} access time common,
= (L_{1} hit rate + 1  L_{1} hit rate)* L_{1} access time + L_{1} miss rate * L_{1} miss penalty
AMAT = L_{1} access time + L_{1} miss rate * L_{1} miss penalty
We access L_{2} only when there is a miss in L_{1}.
So, L_{1} miss penalty is nothing but the effective time taken to access L_{2}.
L_{1}_miss_penalty = Hit_rate_of_L_{2}* Access time of L_{2} + MissRate of L_{2} *(Access time of L_{2}+ miss penalty L_{2})
= Hit_rate_of_L_{2}* Access time of L_{2} + MissRate of L_{2} *Access time of L_{2} + MissRate of L_{2} * miss penalty L_{2}
By taking Access time of L_{2} common we get,
= Access time of L_{2} * (Hit_rate_of_L_{2} + MissRate of L_{2} ) + MissRate of L_{2} * miss penalty L_{2}
We know, MissRate of L_{2} = 1  Hit_rate_of_L_{2} → Hit_rate_of_L_{2} + MissRate of L_{2} = 1
So, the above formula becomes,
L_{1}_miss_penalty = Access time of L_{2} + (MissRate of L_{2} * miss penalty L_{2})
It is given,
access time of L_{1} = 1,
access time of L_{2} = 8,
miss penalty of L_{2} = 18,
AMAT = 2.
Let, miss rate of L_{2} = x.
Since it is given that L_{1} miss rate is twice that of 12 miss rate, L_{1} miss rate = 2 * x.
Substituting the above values,
L_{1}_miss_penalty = Access time of L_{2} + (MissRate of L_{2} * miss penalty L_{2})
L_{1}_miss_penalty = 8 + (x*18)
AMAT = L_{1} access time + L_{1} miss rate * L_{1} miss penalty
2 = 1 + (2*x) (8+18*x)
36*x^{2}+ 16*x 1 = 0
By solving the above quadratic equation we get,
x = Miss rate of L_{2} = 0.056
Miss rate of L_{1} = 2*x = 0.111
Question 30 
Θ(loglogn)  
Θ(logn)  
Θ(√n)  
Θ(n) 
(or)
T(n) = 2T(n^{(1⁄2)}) + 1
Here, Assume n = 2^{k}
T(2^{k}) = 2T(2^{k})^{(1⁄2)} + 1
T(2^{k}) = 2T(2^{(k/2)} ) + 1
Assume T(2^{k}) = S(k)
S(k) = 2S(k/2) + 1
Apply Master’s theorem Case1
a=2, b=2
S(k) = k^{(log22 )}
S(k) = θ(k')
but S(k) = T(2^{k})
T(2^{k}) = θ(k')
but n = 2^{k}
k = logn
T(n) = θ(logn)
Question 31 
Nβ (1  β)  
Nβ  
N (1  β)  
Not expressible in terms of N and β alone 
Given g_{y} (z) = (1  β + βz)^{N} ⇾ it is a binomial distribution like (x+y)^{n}
Expectation (i.e., mean) of a binomial distribution will be np.
The polynomial function ,
given
Mean of Binomial distribution of b(x_{j},n,p)=
The probability Mass function,
Given:
Question 32 
Consider the following expression grammar G:

E → E  T  T
T → T + F  F
F → (E)  id
Which of the following grammars is not left recursive, but is equivalent to G?
S→Sα  β
The equivalent production (after removing left recursion) is
S→βS_{1}
S_{1}→αS_{1}  ϵ
Hence after removing left recursion from: E→ ET  T, here α = T and β = T
E→TE_{1}
E_{1}→ TE_{1}  ϵ
After removing left recursion from: T→T+F  F, here α=+F and β=F
T→FT_{1}
T_{1}→ +FT_{1}  ϵ
Replace E_{1} = X and T_{1} = Y
We have,
E→TX
X→TX  ϵ
T→FY
Y→+FY  ϵ
F→(E) id
Question 33 
A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below:
Which of the following best describe current state of the system?
Safe, Deadlocked  
Safe, Not Deadlocked  
Not Safe, Deadlocked  
Not Safe, Not Deadlocked 
Available: (9  (3 + 1 + 3)) = 2, P3 can be satisfied.
New available = 3 + 2 = 5
Now, P2 can be satisfied.
New available: 5 + 1 = 6
Now, P1 can be satisfied. Thus safe sequence: P3 → P2 → P1
That is not deadlocked.
Question 34 
Consider a binary code that consists of only four valid code words as given below:
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
p=3 and q=1  
p=3 and q=2  
p=4 and q=1  
p=4 and q=2 
Minimum Distance = p = 3
Error bits that can be corrected = (p1)/2 = (31)/2 = 1
∴ p=3 and q=1
Question 35 
Consider two hosts X and Y, connected by a single direct link of rate 10^{6}bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 × 10^{8}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
p=50 and q=100  
p=50 and q=400  
p=100 and q=50  
p=400 and q=50 
B = 10^{6} bits/sec
L = 50000 Bytes
d = 10000 Km = 10^{7} m
v = 8×10^{8} m/sec
Transmission time,
P = L/B = 50000×8bits/ 10^{6} bits/sec = 0.4sec = 400msec
Propagation time,
q = d/v = 10^{7}m/ 2×10^{8} m/s = 0.05sec = 50 msec
Question 36 
The preorder traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the postorder traversal of this tree is:
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20  
2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12  
7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12  
7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 
From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree.
From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.
From <17, 19, 20>, 19 as root.
Hence, 2,7,6,10,9,8 ,15,17,20,19,16 12 is the postorder traversal.
Question 37 
Consider the C program fragment below which is meant to divide x and 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)?
(q == r) && (r == 0)  
(x > 0) && (r == x) && (y > 0)  
(q == 0) && (r == x) && (y > 0)  
(q == 0) && (y > 0) 
x, y, q, r are unsigned integers.
while (r >= y)
{
r = r – y;
q = q + 1;
}
Loop terminates in a state satisfying the condition
x == (y * q + r)
y ⇒ Dividend = Divisor * Quotient + Remainder
So, to divide a number with repeated subtractions, the Quotient should be initialized to 0 and it must be incremented for every subtraction.
So initially q=0 which represents
x = 0 + r ⇒ x = r
and y must be a positive value (>0).
Question 38 
Consider the following C function.
int fun (int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j < n; j += i) { printf("%d %d",i,j); } } }
Time complexity of fun in terms of Θ notation is
Θ(n√n)  
Θ(n^{2} )  
Θ(n logn)  
Θ(n^{2} logn) 
int fun(int n)
{
int i, j;
for (i = 1; i <= n ; i++) /* It is independent loop. So, it takes O(n) time */
{
for (j = 1; j < n; j += i) /* It is dependent loop, It always incrementing with the help of i. It will take approximately O(log n) times*/
{
printf("%d %d", i, j); /* It takes O(1) time */
}
}
}
So, the overall complexity of the program is θ(n logn) times.
Question 39 
∅  
{q_{0},q_{1},q_{3}}  
{q_{0},q_{1},q_{2}}  
{q_{0},q_{2},q_{3}} 
If δ is our transition function, then the extended transition function is denoted by δ.
The extended transition function is a function that takes a state q and a string w and returns a state p (the state that the automaton reaches when starting in state q and processing the sequence of inputs w).
The starting state is q_{2}, from q_{2}, transition with input “a” is dead so we have to use epsilon transition to go to other state.
With epsilon transition we reach to q_{0}, at q_{0} we have a transition with input symbol “a” so we reach to state q_{1}.
From q_{1}, we can take transition with symbol “b” and reach state q_{2} but from q_{2}, again we have no further transition with symbol “a” as input, so we have to take another transition from state q_{1}, that is, the epsilon transition which goes to state q_{2}.
From q_{2} we reach to state q_{0} and read input “b” and then read input “a” and reach state q_{1}. So q_{1} is one of the state of extended transition function.
From q_{1} we can reach q_{2} by using epsilon transition and from q_{2} we can reach q_{0} with epsilon move so state q_{2} and q_{0} are also part of extended transition function.
So state q_{0},q_{1},q_{2}.
Question 40 
Consider the following languages:

L_{1} = {a^{p}│p is a prime number}
L_{2} = {a^{n} b^{m} c^{2m}  n ≥ 0, m ≥ 0}
L_{3} = {a^{n} b^{n} c^{2n} │ n ≥ 0}
L_{4} = {a^{n} b^{n} │ n ≥ 1}
Which of the following are CORRECT?

I. L_{1} is contextfree but not regular.
II. L_{2} is not contextfree.
III. L_{3} is not contextfree but recursive.
IV. L_{4} is deterministic contextfree.
I, II and IV only  
II and III only  
I and IV only  
III and IV only 
L_{2} = {a^{n} b^{m} c^{2m}│n ≥ 0, m ≥ 0} is a context free as we have to do only one comparison (between b’s and c’s) which can be done by using PDA, so L^{2} is Context free and II is true.
L_{3} = {a^{n} b^{n} c^{2n}│n≥0} is context sensitive.
The reason it has more than one comparison (at a time) as we have to compare number of a’s, b’s and c’s.
So this cannot be done using PDA. Hence III is false.
L_{4} = {a^{n} b^{n}│n ≥ 1} is Context free (as well as Deterministic context free).
We can define the transition of PDA in a deterministic manner.
In beginning push all a’s in stack and when b’s comes pop one “a” for one “b”.
If input and stack both are empty then accept.
Question 41 
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 Turing 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 contextfree grammar G, is L(G) = ∅?
III. Given a contextfree grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
I and IV only  
II and III only  
II, III and IV only  
III and IV only 
Emptiness problem for Context free language is decidable, so II is decidable.
Completeness problem (i.e. L(G) = Σ* for a CFG G) is undecidable.
Membership problem for recursive enumerable language (as language of Turing Machine is recursive enumerable) is undecidable.
So IV is undecidable.
Question 42 
The next state table of a 2bit saturating upcounter is given below.
The counter is built as a synchronous sequential circuit using T flipflops. The expressions for T_{1} and T_{0} are
By using above excitation table,
Question 43 
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[i1]) { swap(&array[i], &array[i1]); done=0; } } } printf("%d", array[3]); }
The output of the program is ___________.
3  
4  
5  
6 
(1) ⇒ 1st for i = 0 <= 4
a[0] < a[1] ≃ 3<5 so perform swapping
done =
(1) ⇒ no swap (3, 1)
(2) ⇾ perform swap (1, 4)
(1) ⇒ perform swap (1, 6)
(1) ⇒ perform swap (1, 2)
(1) ⇒ (done is still 0)
for i = 5 >= 1 a[5] > a[4] ≃ 1>2 – false. So, no swapping to be done
(2) ⇾ no swap (6, 2)
(3) ⇾ swap (4, 6)
(1) ⇒ Swap (3, 6)
(1) ⇒ Swap (5, 6)
⇒ Done is still 0. So while loop executes again.
(1) ⇾ no swap (6, 5)
done = 1
(2) ⇾ No swap (5, 3)
(3) ⇾Swap (3, 4)
So, array [3] = 3
Question 44 
Two transactions T_{1} and T_{2} are given as

T_{1}: r_{1}(X)w_{1}(X)r_{1}(Y)w_{1}(Y)
T_{2}: r_{2}(Y)w_{2}(Y)r_{2}(Z)w_{2}(Z)
where r_{i}(V) denotes a read operation by transaction T_{i} on a variable V and w_{i}(V) denotes a write operation by transaction T_{i} on a variable V. The total number of conflict serializable schedules that can be formed by T_{1} and T_{2} is ____________.
54  
55  
56  
57 
= 8!/(4×3×2×4×3×2)
= (8×7×6×5×4×3×2×1)/(4×3×2×4×3×2)
= 70
Following two conflict actions are possible:
∴# Permutations = 4 × 3 = 12
#permutations = 4 × 1 = 4
∴ Total no. of conflict serial schedules possible = 70  12  4 = 54
Question 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 referredwordfirst 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 ___________.
4.72  
4.73  
4.74  
4.75 
Hierarchical memory (Default case):
For 2level memory:
The formula for average memory access time = h_{1} t_{1} + (1h_{1})(t_{1} + t_{2})
This can be simplified as
t_{1} + (1h_{1})t_{2}
For 3level memory:
h_{1} t_{1} + (1h_{1})(t_{1} + h_{2} t_{2} + (1h_{2})(t_{2} + t_{3}))
This can be simplified as
t_{1} + (1h_{1})t_{2} + (1h_{1})(1h_{2})t_{3}
Instruction fetch happens from Icache whereas operand fetch happens from Dcache.
Using that we need to calculate the instruction fetch time (Using Icache and L_{2}cache) and operand fetch time (Using Dcache and L_{2}cache) separately.
Then calculate 0.6 (instruction fetch time) + 0.4(operand fetch time) to find the average read access time.
The equation for instruction fetch time = t_{1} + (1h_{1} ) t_{2} + (1h_{1} )(1h_{2} ) t_{3}
= 2 + 0.2*8 + 0.2*0.1*90 = 5.4ns
Operand fetch time = t_{1} + (1h_{1})t_{2} + (1h_{1})(1h_{2})t_{3} = 2 + 0.1*8 + 0.1*0.1*90 = 3.7ns
The average read access time = 0.6*5.4 + 0.4*3.7 = 4.72ns
Question 46 
7  
8  
9  
10 
In the given database table top_scorer no players are there from ‘Spain’.
So, the query (1) results 0 and ALL (empty) is always TRUE.
The query (2) selects the goals of the players those who are belongs to ‘Germany’.
So, it results in ANY (16, 14, 11, 10).
So, the outer most query results the player names from top_scorer, who have more goals.
Since, the minimum goal by the ‘Germany’ player is 10, it returns the following 7 rows.
Question 48 
If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)^{2}] equals _________.
54  
55  
56  
57 
Mean = Variance
E(X) = E(X^{2})  (E(X))^{2} = 5
E(X^{2}) = 5 + (E(X))^{2} = 5 + 25 = 30
So, E[(X + 2)^{2}] = E[X^{2} + 4 + 4X]
= E(X^{2}) + 4 + 4E(X)
= 30 + 4 + 4 × 5
= 54
Question 49 
In a B^{+} tree, if the searchkey value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B^{+} tree is _________.
52  
53  
54  
55 
Block size = 512 bytes
Block pointer = 2 bytes
Search key = 8 bytes
Let Maximum order of B^{+} tree = n
n(P_{b}) + (n  1)(k) ≤ 512
n(2) + (n  1)(8) ≤ 512
2n + 8n  8 ≤ 512
10n ≤ 520
n ≤ 520/10
(n = 52)
Question 50 
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:
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.
225  
226  
227  
228 
General procedure to solve Huffman coding problem
Step1: Arrange into either descending/ ascending order according to that profits.
Step2: Apply optimal merge pattern procedure.
Step3: Make left subtree value either 0 or 1, for right subtree, viceversa.
= 2 × 0.34 + 2 × 0.22 + 2 × 0.19 + 3 × 0.17 + 3 × 0.08
= 2.25
∴ So, for 100 characters, 2.25 * 100 = 225
Question 51 
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.
The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is __________.
29  
30  
31  
32 
Waiting Time = 0 + (33  5) + (40  2) + (49  12) + (51  9) = 145
Average waiting time: 145/5 = 29
Question 52 
If the characteristic polynomial of a 3 × 3 matrix M over R (the set of real numbers) is λ^{3}  4λ^{2} + aλ + 30, a ∈ ℝ, and one eigenvalue of M is 2, then the largest among the absolute values of the eigenvalues of M is ________.
5  
6  
7  
8 
λ^{3}  4λ^{2} + aλ + 30 = 0 ⇾ (1)
One eigen value is ‘2’, so substitute it
2^{3}  4(2)^{2} + a(2) + 30 = 0
8  16 + 2a + 30 = 0
2a = 22
a = 11
Substitute in (1),
λ^{3}  4λ^{2}  11 + 30 = 0
So, (1) can be written as
(λ  2)(λ^{2}  2λ  15) = 0
(λ  2)(λ^{2}  5λ + 3λ  15) = 0
(λ  2)(λ  3)(λ  5) = 0
λ = 2, 3, 5
Max λ=5
Question 53 
Consider a machine with a byte addressable main memory of 2^{32} bytes 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 _____________.
18  
19  
20  
21 
So the physical address is 32 bits long.
Each block is of size 32(=2^{5}) Bytes. So block offset 5.
Also given that there are 512(=2^{9}) cache lines, since it is a direct mapped cache we need 9 bits for the LINE number.
When it is directed mapped cache, the physical address can be divided as
(Tag bits + bits for block/LINE number + bits for block offset)
So, tag bits + 9 + 5 = 32
Tag bits = 32  14 = 18
Question 54 
Consider the following C program.
#include<stdio.h> int main () { int m = 10; int n, n1; n = ++m; n; n1; n = n1; printf("%d", n); return 0; }
The output of the program is _________.
0  
1  
2  
3 
n = ++m; (pre)
n = 11
n1 = m++ (post)
Here, n1 = 11, but m will be updated to 12.
n & n1 decrements 11 to 10 & subtracting gives us zero.
Question 55 
Consider the following C program.
#include<stdio.h> #include<string.h> int main () { char* c = "GATECSIT2017"; char* p = c; printf("%d", (int) strlen (c + 2[p]  6[p]  1)); return 0; }
The output of the program is __________.
1  
2  
4  
6 
char * P = C;
(int) strlen (C + 2[P] – 6[P] – 1)
C + 2[P]  6[P] – 1
∵2[P] ≃ P[2]
100 + P[2] – P[6] – 1
100 + T – I – 1
100 + 84 – 73 – 1
ASCII values: T – 84, I – 73
100 + 11 – 1
= 110
(int) strlen (110)
strlen (17) ≃ 2
Question 56 
Choose the option with words that are not synonyms.
aversion, dislike  
luminous, radiant  
plunder, loot  
yielding, resistant 
Resistant means offering a resistance to something or someone.
Question 57 
Saturn is __________ to be seen on a clear night with the naked eye.
enough bright  
bright enough  
as enough bright  
bright as enough 
With adjectives and adverbs enough is comes after an adjectives and adverbs.
So, here we use bright enough to complete the sentence.
Question 58 
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?
V  
W  
X  
Y 
Z is to East of X and west of V = XZV ........(ii)
W is to west of Y = WY .........(iii)
From (i) and (ii) ⇒ VWY .........(iv)
From (ii) and (iv) ⇒ XZVWY
→ While building V is in the middle.
Question 59 
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?
12  
15  
18  
19 
No. of 4 marks questions = Y say
No. of questions X + Y = 20
Total no. of marks = 100
⇒ 3X + 11Y = 100
Option I:
If X=12; Y=8 ⇒ 3(12)+11(8) ⇒ 36+88 ≠ 100
Option II:
If X=15; Y=5 ⇒ 3(15)+11(5) ⇒ 100 = 100
Option III:
If X=18; Y=2 ⇒ 3(18)+11(2) ≠ 100
Option IV:
If X=19; Y=1 ⇒ 3(19)+11(1) ≠ 100
Question 60 
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
1⁄5  
7⁄30  
1⁄4  
4⁄15 
The probability of selecting same colour is
⇒ ^{3}C_{2} / ^{10}C_{2} * ^{4}C_{2} / ^{10}C_{2} * ^{3}C_{2} / ^{10}C_{2}
⇒ 3/45 + 6/45 + 3/45
⇒ 12/45
= 4/15
Question 61 
“We lived in a culture that denied any merit to literary works, considering them important only when they are 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:
‘culture’  
‘seemingly’  
‘urgent’  
‘political’ 
(or)
As to give the impression of having a certain quality.
Question 62 
There are three boxes. One contains apples, another contains oranges and the last one contains both apple and oranges. All three are known to be incorrectly labeled. 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?
The box labeled ‘Apples’  
The box labeled ‘Apples and Oranges’  
The box labeled ‘Oranges’  
Cannot be determined 
If we open a box labeled as apples and oranges that contains either apples (or) oranges:
Case I:
If it contains apples, then the box labeled oranges can contain apples and oranges and box labeled apples can contain oranges.
Case II:
If it contains oranges, then box labeled apples can contains apples and oranges and box labeled oranges can contains apples.
Question 63 
X is a 30 digit number starting with the digit 4 followed by the digit 7. Then the number X^{3} will have
90 digits  
91 digits  
92 digits  
93 digits 
X = 4777......... (29 times (7))
X = 4.777........ ×10^{29}
X = 5×10^{29} (4.777 rounded as 5)
X^{3} = 125×10^{87}
Total no. of digits = 3+87 [125=3 digit, 10^{87} = 87 digit]
= 90
Question 64 
The number of roots of e^{x} + 0.5x^{2} – 2 in the range [5, 5] is
0  
1  
2  
3 
e^{x} = 0.5x^{2} + 2
If we draw a graph for e^{x} and 0.5x^{2} + 2 in between [5, 5]
Question 65 
An air pressure contour line joins locations in a region having the same atmospheric pressure. The following is an air pressure contour plot of a geographical region. Contour lines are shown at 0.05 bar intervals in this plot.
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?
P  
Q  
R  
S 