GATE 2017(set-02)

Question 1
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
136251
B
736251
C
571247
D
136252
       igital Logic Design       Number System
Question 1 Explanation: 
X=(BCA9)16
Each hexadecimal digit is equal to a 4-bit 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 3-bit 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=(1 3 6 2 5 1)8
Question 2
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)
       Programming       Match the following
Question 2 Explanation: 
Static char var; ⇾ A variable located in Data Section of memory

P→(ii),Q→(iv),R→(i),S→(iii)
Question 3
 
A
P→(iii),Q→(iv),R→(i),S→(ii)
B
P→(iv),Q→(iii),R→(i),S→(ii)
C
P→(iii),Q→(iv),R→(ii),S→(i)
D
P→(iv),Q→(iii),R→(ii),S→(i)
       Algorithms       Match the following
Question 3 Explanation: 
In this problem, we have to find Average case of different algorithms
→ Tower of Hanoi with n disks takes θ(2n) 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 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)
Question 4
   
A
I, II and IV only
B
I and III only
C
II and IV only
D
I only
       Theory Of computation       Context Free Language
Question 4 Explanation: 
Since CFL is closed under UNION so L1∪L2 is CFL, is a true statement.
CFL is not closed under complementation; So L1 compliment may or may not be CFL. Hence is Context free, is a false statement.
L1 – R means and Regular language is closed under compliment, so is also a regular language, so we have now L1∩R . Regular language is closed with intersection with any language, i.e. L∩R is same type as L. So L1∩R is context free.
CFL is not closed under INTERSECTION, so L1∩ L2 may or may not be CFL and hence IVth is false.
Question 5
A
P→(ii),Q→(iii),R→(iv),S→(i)
B
P→(ii),Q→(i),R→(iii),S→(iv)
C
P→(iii),Q→(iv),R→(i),S→(ii)
D
P→(i),Q→(iv),R→(ii),S→(iii)
       Compiler design       Compilers
Question 5 Explanation: 
Character stream is input to lexical analyzer which produces tokens as output. So Q → (iv).
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
   
A
I only
B
II only
C
III only
D
II and III only
       Compiler design        Parsers
Question 6 Explanation: 
Canonical LR is more powerful than SLR as every grammar which can be parsed by SLR parser, can also be parsed by CLR parser. The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
Question 7
   
A
I and II only
B
III only
C
IV only
D
III and IV only
       Operating Systems       Threads
Question 7 Explanation: 
First of all, you need to know about process and threads. 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
A
I and III only
B
II only
C
III only
D
II and III only
       Operating Systems       File Allocation Methods
Question 8 Explanation: 
→ Contiguous Allocation:
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
 
A
I and IV only
B
I, II and III only
C
I, II and IV only
D
II, III and IV only
       Computer Networks       Routing
Question 9 Explanation: 
I: RIP uses distance vector routing. “TRUE”
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 10
A
2/π and 16/π
B
2/π and 0
C
4/π and 0
D
4/π and 16/π
       Engineering Mathematics       Calculus
Question 10 Explanation: 

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
A
(¬p∧r)∧(¬r→(p∧q))
B
(¬p∧r)∧((p∧q)→¬r)
C
(¬p∧r)∨((p∧q)→¬r)
D
(¬p∧r)∨(r→(p∧q))
       Engineeing Mathematics       Prepositional Logic
Question 11 Explanation: 
p: It is raining
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) ⇾②
From ① & ②, the given statement can be represented as
Question 12
 
A
1.45×101
B
1.45×10-1
C
2.27×10-1
D
2.27×101
       Digital Logic System       Number systems
Question 12 Explanation: 

For single-precision floating-point representation decimal value is equal to (-1)5×1.M×2(E-127)
S=0
E=(01111100)2=(124). So E – 127 = - 3
1.M=1.11011010…0
=20+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(E-127)=(-1)0×1.847×2(-3)
≈0.231
≈2.3×10(-1)
Question 13
   
A
I only
B
II only
C
Both I and II
D
Neither I nor II
       Data Structures       Circular queue and Linked list
Question 13 Explanation: 
1. Next pointer of front node points to the rear node. 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
 
A
0, 0
B
0, 1
C
1, 0
D
1, 1
       Programming       Programming
Question 14 Explanation: 
printxy (int x, int y)
{
int *ptr;
x = 0;
ptr = &x;
y = *ptr;
*ptr = 1;

}
printxy (1, 1)
Question 15
 
A
MNOPQR
B
NQMPOR
C
QMNROP
D
POQNMR
       Data Structures        BFS
Question 15 Explanation: 
The possible order of visiting the nodes in Breadth First Search Algorithm, implementing using Queue Data Structure is

(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
   
A
{am bn│m≥n,n>0}
B
{am bn│m≥n,n≥0}
C
{am bn│m>n,n≥0}
D
{am bn│m>n,n>0}
       Theory Of Computation       Finite Automata
Question 16 Explanation: 
The production X→ aX | a can generate any number of a’s ≥ 1 and the production Y→ aYb | ϵ will generate equal number of a’s and b’s.
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 {am bn│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?  
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 one-to-many and the participation of A in R is partial.
       Database Management System       ER Model
Question 17 Explanation: 

The relational table for R be merged that of A, if the relationship R is Many-to-one and the participation of A in R is total.
Question 18
 
A
I only
B
II only
C
Both I and II
D
Neither I nor II
       Computer Networks       UDP
Question 18 Explanation: 
A connected UDP socket, the result of calling connection a UDP socket, Connect () specifying the remote address.
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
 
A
0
B
1
C
2
D
3
       Database Management Systems       Referential Integrity Constraint
Question 19 Explanation: 

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 _________.
A
9
B
10
C
11
D
12
       Computer Networks       IPV4
Question 20 Explanation: 
A record route option is used to record the internet router that handles the datagram. It can be used for debugging and management purpose.
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
 
A
0
B
1
C
2
D
3
       Engineering Mathematics       Set theory an algebra
Question 21 Explanation: 
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)}
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
A
2
B
3
C
4
D
5
       Engineering Mathematics        Matrices
Question 22 Explanation: 


R2→R2+R1

The number of non-zero rows of P + Q = 2,
So Rank = 2
Note: “Rank” is the number of independent vectors.
Method-1:
Each vector is a row in matrix.
Echelon form of a matrix has no. of zeroes increasing each rows.
The total non-zero rows left give the rank.
Method-2:
Find determinant of matrix, for 3×5, if determinant is ‘0’, the max rank can be 2. If determinant of any n×n is non-zero, then rows proceed with (n-1)×(n-1).
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 ___________.
A
16
B
17
C
18
D
19
       Engineering Mathematics       Graph Theory
Question 23 Explanation: 
An undirected graph ‘G’ has ‘n’ vertices & 25 edges.
Degree of each vertex ≥3

|v|=2|E|
The relation between max and min degree of graph are
m≤2|E|/|v| ≤M
Given minimum degree = 3
So 3≤2 |E|/|v|
3|v|≤2|E|
3(n)≤2(25)
n≤50/3
n≤16.6
(n=16)
Question 24
Consider a quadratic equation x-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 = _____.
A
8
B
9
C
10
D
11
       Digital Logic design       Number system
Question 24 Explanation: 
x2-13x+36=0 ⇾①
Generally if a, b are roots.
(x-a)(x-b)=0
x2-(a+b)x+ab=0
Given that x=5,x=6 are roots of ①
So a+b=13
ab=36 (with same base ‘b’)
i.e., (5)b+(6)b=(13)b
Convert them into decimal value
5b=510
610=610
13b=b+3
11=b+3
b=8
Now check with ab=36
5b×6b=36b
Convert them into decimals
5b×6b=(b×3)+610
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={w1aw2|w1, w2∈{a,b}*,|w1|=2,|w2|≥3} is _____.
A
8
B
9
C
10
D
11
       Theory Of computation       DFA
Question 25 Explanation: 
|w1 |=2 means the length of w1 is two. So we have four possibilities of w1={aa,ab,ba,bb}.
|w2 |≥3 means the w2 will have at least three length string from {a,b}.
w2 will have {aaa,aab,aba,abb,baa,bab,bba,bbb,……….}
So the required DFA is
Question 26
A
4/5
B
5/6
C
7/8
D
11/12
       Engineering Mathematics       Probability
Question 26 Explanation: 
Probability that ‘P’ applies for a job =1/4=P(p) ⇾①
Probability that ‘P’ applies for the job given that Q applies for the job =P(p/q)=1/2 ⇾ ②
Probability that ‘Q’ applies for the job, given that ‘P’ applies for the job =P(p/q)=1/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) ⇾ ④
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') ⇾⑤
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) ⇾⑥
Substitute in ⑤,
P(p'⁄q')=(2⁄3)/(1-P(q))=(2⁄3)/(1-1/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?
A
wx+w(x+y)+x(x+y)=x+wy
B
C
D
(w+y)(wxy+wyz)=wxy+wyz
       digital Logic Design       Boolean expressions
Question 27 Explanation: 
Option-A:
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
Option-B:

Option-C:

Option-D:
(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’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
B
C
D
       Digital Logic Design       K-Map
Question 28 Explanation: 
f(w,x,y,z)=Σm(0,1,2,3,7,8,10)+Σd(5,6,11,15)
K-Map for the function f is

Consider maxterms in K-map to represent function in product-of-sums (POS) form
f(w,x,y,z)=(w'+z')(x'+z)
Question 29
In a two-level cache system, the access times of L1 and L2 caches are 1 and 8 clock cycles, respectively. The miss penalty from the 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. The 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
       Computer Organization       Cache Mapping
Question 29 Explanation: 
The Average memory access time is,
AMAT = (L1 hit rate)*(L1 access time) + (L1 miss rate)*(L1 access time + L1 miss penalty)
= L1 hit rate * L1 access time + L1 miss rate * L1 access time + L1 miss rate * L1 miss penalty
We can write, L1 miss rate = 1 - L1 hit rate
AMAT = L1 hit rate * L1 access time + (1 - L1 hit rate) * L1 access time + L1 miss rate * L1 miss penalty
By taking L1 access time common,
= (L1 hit rate + 1 - L1 hit rate)* L1 access time + L1 miss rate * L1 miss penalty
AMAT = L1 access time + L1 miss rate * L1 miss penalty
We access L2 only when there is a miss in L1. So, L1 miss penalty is nothing but the effective time taken to access L2.
L1_miss_penalty = Hit_rate_of_L2* Access time of L2 + MissRate of L2 *(Access time of L2+ miss penalty L2)
= Hit_rate_of_L2* Access time of L2 + MissRate of L2 *Access time of L2 + MissRate of L2 * miss penalty L2
By taking Access time of L2 common we get,
= Access time of L2 * (Hit_rate_of_L2 + MissRate of L2 ) + MissRate of L2 * miss penalty L2
We know, MissRate of L2 = 1 - Hit_rate_of_L2 → Hit_rate_of_L2 + MissRate of L2 = 1
So, the above formula becomes,
L1_miss_penalty = Access time of L2 + (MissRate of L2 * miss penalty L2)
It is given,
access time of L1 = 1,
access time of L2 = 8,
miss penalty of L2 = 18,
AMAT = 2.
Let, miss rate of L2 = x. Since it is given that L1 miss rate is twice that of 12 miss rate, L1 miss rate = 2 * x.
Substituting the above values,
L1_miss_penalty = Access time of L2 + (MissRate of L2 * miss penalty L2)
L1_miss_penalty = 8 + (x*18)
AMAT = L1 access time + L1 miss rate * L1 miss penalty
2 = 1 + (2*x) (8+18*x)
36*x2+ 16*x -1 = 0
By solving the above quadratic equation we get,
x = Miss rate of L2 = 0.056
Miss rate of L1 = 2*x = 0.111
Question 30
A
Θ(log⁡log⁡n)
B
Θ(log⁡n)
C
Θ(√n)
D
Θ(n)
       Algorithms       Time Complexity
Question 30 Explanation: 
T(n)=2T(√n)+1
(or)
T(n)=2T(n(1⁄2) )+1
Here Assume n=2k
T(2k )=2T(2k )(1⁄2)+1
T(2k )=2T(2(k/2) )+1
Assume T(2k )=S(k)
S(k)=2S(k/2)+1
Apply Master’s theorem Case-1
a=2,b=2
S(k)=k(log22 )
S(k)=θ(k')
but S(k)=T(2k)
T(2k)=θ(k')
but n=2k
k=log⁡n
T(n)=θ(logn)
Question 31
A
Nβ(1-β)
B
C
N(1-β)
D
Not expressible in terms of N and β alone
       Engineering Mathematics       Probability
Question 31 Explanation: 
For a discrete random variable X,
Given gy (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(xj,n,p)=
The probability Mass function,

Given:
Question 32
A
B
C
D
       Compiler esign       Left Recursive Grammar
Question 32 Explanation: 
Consider the production (given below) which has left recursion.
S→Sα | β
The equivalent production (after removing left recursion) is
S→βS1
S1→αS1 | ϵ
Hence after removing left recursion from: E→ E-T | T, here α = -T and β = T
E→TE1
E1→ -TE1 | ϵ
After removing left recursion from: T→T+F | F, here α=+F and β=F
T→FT1
T1→ +FT1 | ϵ
Replace E1= X and T1= Y
We have,
E→TX
X→-TX | ϵ
T→FY
Y→+FY | ϵ
F→(E)| id
Question 33
 
A
Safe, Deadlocked
B
Safe, Not Deadlocked
C
Not Safe, Deadlocked
D
Not Safe, Not Deadlocked
       Operating Systems       deadlock
Question 33 Explanation: 

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
A
p=3 and q=1
B
p=3 and q=2
C
p=4 and q=1
D
p=4 and q=2
       Digital Logic design       Number Systems
Question 34 Explanation: 
Hamming distance of a code is minimum distance between any two code words.
Minimum Distance =p=3

Error bits that can be corrected =(p-1)/2=(3-1)/2=1
∴ p=3 and q=1
Question 35
Consider two hosts X and Y, connected by a single direct link of rate 10bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 × 108m/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
       Computer Networks       Network Communication
Question 35 Explanation: 
Given Data:
B=106 bits/sec
L=50000 Bytes
d=10000 Km = 107 m
v=8×108 m/sec
Transmission time,
P = L/B = 50000×8bits/ 106 bits/sec = 0.4sec = 400msec
Propagation time,
q = d/v = 107m / 2×108 m/s = 0.05sec = 50 msec
Question 36
The pre-order traversal 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
       ata Structures       Binary tree
Question 36 Explanation: 

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 post-order traversal.
Question 37
 
A
(q==r) && (r==0)
B
(x>0) && (r== x) && (y>0)
C
(q==0) && (r==x) && (y>0)
D
(q==0) && (y>0)
       Programming       Programming
Question 37 Explanation: 
Divide x by y.
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
A
Θ(n√n)
B
Θ(n2 )
C
Θ(n log⁡n)
D
Θ(n2 logn)
       Algorithms       Time Complexity
Question 38 Explanation: 
We can solve iterative programs time complexity with the help of rollback method.
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 log⁡n) times.
Question 39
A
B
{q0,q1,q3}
C
{q0,q1,q2 }
D
{q0,q2,q3 }
       Theory Of Computation       NFA
Question 39 Explanation: 
Extended transition function describes, what happens when we start in any state and follow any sequence of inputs. 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 q2, from q2, transition with input “a” is dead so we have to use epsilon transition to go to other state.
With epsilon transition we reach to q0, at q0 we have a transition with input symbol “a” so we reach to state q1.
From q1, we can take transition with symbol “b” and reach state q2 but from q2, again we have no further transition with symbol “a” as input, so we have to take another transition from state q1, that is, the epsilon transition which goes to state q2.
From q2 we reach to state q0 and read input “b” and then read input “a” and reach state q1. So q1 is one of the state of extended transition function.
From q1 we can reach q2 by using epsilon transition and from q2 we can reach q0 with epsilon move so state q2 and q0 are also part of extended transition function.
So state q0,q1,q2.
Question 40
 
A
I, II and IV only
B
II and III only
C
I and IV only
D
III and IV only
       Theory Of Computation       Context Free Languages
Question 40 Explanation: 
L1={ap│p is a prime number} is a context sensitive language. So I is false.
L2={an bm c2m│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 L2 is Context free and II is true.
L3={an bn c2n│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.
L4={an bn│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
A
I and IV only
B
II and III only
C
II, III and IV only
D
III and IV only
       Theory Of Computation       Deciability and Unecidability
Question 41 Explanation: 
Since membership problem for regular language is decidable, so I is decidable.
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
A
B
C
D
       Digital Logic Design       Sequential Circuit
Question 42 Explanation: 

By using above excitation table,
Question 43
   
A
3
B
4
C
5
D
6
       Programming       Programming
Question 43 Explanation: 
Swap (&x, &y) exchanges the contents of x & y.

①⇒ 1st for i = 0 <= 4 a[0] < a[1] ≃ 3<5 so perform swapping
done=

①⇒ no swap (3, 1)
②⇾ perform swap (1, 4)

①⇒ perform swap (1, 6)

①⇒ perform swap (1, 2)

①⇒ (done is still 0)
for i = 5 >= 1 a[5] > a[4] ≃ 1>2 – false. So, no swapping to be done
②⇾ no swap (6, 2)
③⇾ swap (4, 6)

①⇒ Swap (3, 6)

①⇒ Swap (5, 6)

⇒ Done is still 0. So while loop executes again.
①⇾ no swap (6, 5)
done = 1
②⇾ No swap (5, 3)
③⇾Swap (3, 4)

So, array [3] = 3
Question 44
A
54
B
55
C
56
D
57
       Database Management Systems       Transactions
Question 44 Explanation: 
From the given transactions T1 and T2, total number of schedules possible =(4+4)!/4!4!
=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
 
A
4.72
B
4.73
C
4.74
D
4.75
       Computer Organisation       Cache Memory
Question 45 Explanation: 
Since nothing is given whether it is hierarchical memory or simultaneous memory, by default we consider it as hierarchical memory.
Hierarchical memory (Default case):
For 2-level memory: The formula for average memory access time = h1 t1 + (1-h1)(t1+t2), this can be simplified as t1+(1-h1)t2
For 3-level memory: h1 t1+(1-h1)(t1+h2 t2+(1-h2)(t2+t3)) this can be simplified as
t1 + (1-h1)t2 + (1-h1)(1-h2)t3
Instruction fetch happens from I-cache whereas operand fetch happens from D-cache. Using that we need to calculate the instruction fetch time (Using I-cache and L2--cache) and operand fetch time (Using D-cache and L2-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 = t1 + (1-h1 ) t2 + (1-h1 )(1-h2 ) t3
=2+0.2*8+0.2*0.1*90 = 5.4ns
Operand fetch time = t1+(1-h1)t2 + (1-h1)(1-h2)t3 = 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
A
7
B
8
C
9
D
10
       Database Management Systems       SQL
Question 46 Explanation: 

In the given database table top_scorer no players are there from ‘Spain’. So, the query ① results 0 and ALL (empty) is always TRUE.
The query ② 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 47
A
15
B
16
C
17
D
18
       Engineering Mathematics       Combinatories
Question 47 Explanation: 
Question 48
If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X+2)2] equals _________.
A
54
B
55
C
56
D
57
       Engineering Mathematics       Probability
Question 48 Explanation: 
In Poisson distribution:
Mean = Variance
E(X)=E(X2) - (E(X))2 = 5
E(X2) = 5+(E(X))2 = 5+25 = 30
So, E[(X+2)2] = E[X2 + 4 +4X]
= E(X2)+4+4E(X) = 30+4+4×5
= 54
Question 49
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 the maximum order of the B+ tree is _________.
A
52
B
53
C
54
D
55
       Database Management systmes       B+trees
Question 49 Explanation: 
Given,
Block size = 512 bytes
Block pointer = 2 bytes
Search key = 8 bytes
Let Maximum order of B+ tree = n
n(Pb )+(n-1)(k)≤512
n(2)+(n-1)(8)≤512
2n+8n-8≤512
10n≤520
n≤520/10
(n=52)
Question 50
A
225
B
226
C
227
D
228
       Algorithms       Huffmann Coding
Question 50 Explanation: 

General procedure to solve Huffman coding problem
Step-1: Arrange into either descending/ ascending order according to that profits.
Step-2: Apply optimal merge pattern procedure.
Step-3: Make left sub-tree value either 0 or 1, for right sub-tree, vice-versa.




=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
A
29
B
30
C
31
D
32
       Operating systems       Process Scheduling
Question 51 Explanation: 

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∈R, and one eigenvalue of M is 2, then the largest among the absolute values of the eigenvalues of M is ________.
A
5
B
6
C
7
D
8
       Engineering Mathematics       Linear Algebra
Question 52 Explanation: 
For a 3×3 matrix ‘M’, the characteristic equation |A – λI| is
λ3-4λ2+aλ+30=0 ⇾①
One eigen value is ‘2’, so substitute it
23-4(2)2+a(2)+30=0
8-16+2a+30=0
2a=-22
a=-11
Substitute in ①,
λ3-4λ2-11+30=0

So ① 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 232 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 _____________.
A
18
B
19
C
20
D
21
       Computer Organisation       Cache Memapping
Question 53 Explanation: 
Given that it is a byte addressable memory and the main memory is of size 232 Bytes.
So the physical address is 32 bits long.
Each block is of size 32(=25) Bytes. So block offset 5.
Also given that there are 512(=29) 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
A
0
B
1
C
2
D
3
       Programming       Programming
Question 54 Explanation: 

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
A
1
B
2
C
4
D
6
       Programming       Programming
Question 55 Explanation: 
char * C = “GATECSIT2017”;
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.
A
aversion, dislike
B
luminous, radiant
C
plunder, loot
D
yielding, resistant
       Aptitude       Verbal
Question 56 Explanation: 
Yeilding means produce (or) provide (a natural, agricultural or industrial product)
Resistant means offering a resistance to something or someone.
Question 57
Saturn is __________ to be seen on a clear night with the naked eye.
A
enough bright
B
bright enough
C
as enough bright
D
bright as enough
       Aptitude       Verbal
Question 57 Explanation: 
In this question enough is used with bright, where bright is an adjective.
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?
A
V
B
W
C
X
D
Y
       Aptitude       Numerical
Question 58 Explanation: 
V is to west of W = VW .........(i)
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?
A
12
B
15
C
18
D
19
       Aptitude       Numerical
Question 59 Explanation: 
No. of 3 marks questions = X say
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
A
1⁄5
B
7⁄30
C
1⁄4
D
4⁄15
       Aptitude       Numerical
Question 60 Explanation: 
Totally there are 3 red socks, 4 green socks, 3 blue socks. In those we need to select 2 socks
The probability of selecting same colour is
3C2 / 10C2 * 4C2 / 10C2 * 3C2 / 10C2
⇒ 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:
A
‘culture’
B
‘seemingly’
C
‘urgent’
D
‘political’
       Aptitude       Verbal
Question 61 Explanation: 
Seemingly means that "according to the facts as one knows them" as far as one knows.
(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?
A
The box labeled ‘Apples’
B
The box labeled ‘Apples and Oranges’
C
The box labeled ‘Oranges’
D
Cannot be determined
       Aptitude       Numerical
Question 62 Explanation: 
Correct Answer is option B i.e., the box labeled Apples an Oranges.
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 X3 will have
A
90 digits
B
91 digits
C
92 digits
D
93 digits
       Aptitude       Numerical
Question 63 Explanation: 
X is a 30 digit number starting with digit 4 and followed by the digit 7
X = 4777......... (29 times (7))
X = 4.777........ ×1029
X = 5×1029 (4.777 rounded as 5)
X3 = 125×1087
Total no. of digits = 3+87 [125=3 digit, 1087 = 87 digit]
= 90
Question 64
The number of roots of ex + 0.5x2 – 2 in the range [-5, 5] is
A
0
B
1
C
2
D
3
       Aptitude       Numerical
Question 64 Explanation: 
ex+0.5x2-2=0
ex=-0.5x2+2
If we draw a graph for ex and -0.5x2+2 in between [-5, 5]
Question 65
A
P
B
Q
C
R
D
S
       Aptitude       Numerical
Question 65 Explanation: 
Region R can have more air pressure as compared to other regions because it has maximum number of lines crossing the area.
There are 65 questions to complete.