### CSE IT GATE 2015 Question Paper Solutions: Part-2

In this post, we have covered Question No-10 to Question No-20 of the 2015 set-3 gate question paper for CSE.  Please click here for Part-1 of CSE IT GATE 2015 Question Paper Solutions to see the Q-1 to Q10 with answers…

Q[10] Consider the equality $\sum_{i=0}^{n}i^{3} = X$ and the following choices for 𝑋
I. Ɵ(𝑛4)
II. Ɵ(𝑛5)
III. 𝑂(𝑛5)
IV. Ω(𝑛3)
The equality above remains correct if 𝑋 is replaced by
(A) Only I
(B) Only II
(C) I or III or IV but not II
(D) II or III or IV but not I

Explanation:
X= sum of the cubes of first n natural numbers
[n2 (n 1)2 ] / 4 =which equals the values of : θ(n4) , O(n5) and Ω(n3)

Q[11] Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________

Explanation:
Let a binary tree with ‘n’ vertices be ‘p’  has
(i) ‘p’ vertices of degree ‘1’
(ii) one vertex (i.e. root of T) of degree ‘2’.
(iii) ‘n − p −1’ vertices of degree ‘3’
(iv) ‘n −1’ edges

Then, as per Handshaking theorem we have:

p×1+1× 2 + (n − p −1)×3 = 2(n −1)
=>n= 2p- 1
=>399 as p= 200
Then the number of nodes having exactly two children is n − p = 199

Q[12]  Given a hash table 𝑇 with 25 slots that stores 2000 elements, the load factor 𝛼 for 𝑇 is ____________.

Explanation:
load factor = (no. of elements) / (no. of table slots) = 2000/25 = 80

Q[13] In the given matrix
1  1  2
0  1  0
1  2  1
one of the eigenvalues is 1. The eigenvectors corresponding to the eigenvalue 1 are

(A) {𝛼(4,2,1)|𝛼≠0,𝛼∈ℝ}
(B) {𝛼(−4,2,1)|𝛼≠0,𝛼∈ℝ}
(C) {𝛼(√2,0,1)|𝛼≠0,𝛼∈ℝ}
(D) {𝛼(−√2,0,1)|𝛼≠0,𝛼∈ℝ}

Explanation:
And let the given matrix be A (square matrix of order 3 x3)

The characteristic equation for this can be written as :

AX = zX  ; Here, X is the eigenvector that is needed
AX – zX = 0
[ A – z I ] [X] = 0  where I is an identity matrix of order 3

put z = 1 => given that of the eigenvalue is 1

[ A – 1 I ] [X] = 0

The resultant matrix is :

[ 0 -1 2 ] [x1] [0]
[ 0 0 0 ] [ x2] =[ 0 ]
[ 1 2 0 ] [ x3] [0]

Multiplying thr above matrices and getting the equations as:

-x2 + 2×3 = 0 —————-(1)
x1 + 2×2 = 0—————–(2)

now let x1 = k, then x2 and x3 will be -k/2 and -k/4
respectively.

hence eigenvector X = { (k , -k/2, -k/4) } where k != 0

put k = -4c ( c is also a constant, not equal to zero ),
we get X = { ( -4c, 2c, 1c ) }, i.e. { c ( -4, 2, 1 ) }

Hence option B.

Q[14] The value of lim𝑥→∞(1+𝑥2)𝑒−𝑥 is
(A) 0
(B) 1/2
(C) 1
(D) ∞

Explanation:
This can be solved using L’Hôpital’s rule that uses derivatives to help evaluate limits involving indeterminate forms.

Since lim_{x\to c}f{x}= lim_{x\to c}g{x}=infinity and lim_{x\to c}\frac{f{x}{g'(x)} exists.

We get  lim_{x\to c}\frac{f'{x}} {g(x)}=lim_{x\to c}\frac {f'(x)}{g'(x)}.

lim_{x\to infinity}frac{1+x^2}{e^x} = lim_{x\to infinity}frac{2x}{e^x} = lim_{x\to infinity}frac{2}{e^x}=0

Q[15] The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is____________

Explanation:
4-digit numbers with first digit ‘1’ are as follows:
1111, 1112, 1113, 1122, 1123, 1133, 1222, 1223, 1233, 1333 i.e., 10
4 digit numbers with first digit 2 : 2222, 2223, 2233, 2333 i.e, 4
4 digit numbers with first digit 3: 3333 i.e, 1

Finally, the total is 15.

Q[16] In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following “The result of the toss is head if and only if I am telling the truth.”
Which of the following options is correct?
(B) The result is tail
(C) If the person is of Type 2, then the result is tail
(D) If the person is of Type 1, then the result is tail

Q[17] While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
(A) 65
(B) 67
(C) 69
(D) 83

Explanation:

Q[18] The result of evaluating the postfix expression 10 5 + 60 6 / * 8 − is
(A) 284
(B) 213
(C) 142
(D) 71

Explanation:
10  10/5   15/+  60/15/15    6/60/15/6    10/15//  150/*    8/150/8   142/-

Q[19] Consider the following relation
Which of the following options will be needed at the end of the SQL query

FROM Cinema P1
such that it always finds the addresses of theaters with maximum capacity?
(A) WHERE P1.capacity >= All (select P2.capacity from Cinema P2)
(B) WHERE P1.capacity >= Any (select P2.capacity from Cinema P2)
(C) WHERE P1.capacity > All (select max(P2.capacity) from Cinema P2)
(D) WHERE P1.capacity > Any (select max(P2.capacity) from Cinema P2)

Explanation:
The inner query collects capacities of all the theaters. In the outer query,  we are filtering the tuples
with the condition “capacity>=All”. So the theaters which are having maximum capacity will satisfy the conductivity and Hence the answer is option A.

Q[20] Consider the following array of elements.
〈89,19,50,17,12,15,2,5,7,11,6,9,100〉
The minimum number of interchanges needed to convert it into a max-heap is

(A) 4
(B) 5
(C) 2
(D) 3