# GATE 2015 Question Paper Solutions Free Download : Part-2

**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 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**

**Answer: C**

**Explanation:**

X= sum of the cubes of first n natural numbers

**[n ^{2} (n 1)^{2 }] / 4** =which equals the values of : θ(n

^{4}) , O(n

^{5}) and Ω(n

^{3})

**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 ________**

**Answer: 199**

**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 ____________.**

**Answer:** **80**

**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

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,𝛼∈ℝ}**

**Answer: B**

**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) ∞**

**Answer: A**

**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____________ **

**Answer:15**

**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?**

**(A) The result is head**

**(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**

**Answer: C**

**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**

**Answer: B**

**Explanation: **

**Q[18] The result of evaluating the postfix expression 10 5 + 60 6 / * 8 − is**

**(A) 284**

**(B) 213**

**(C) 142**

**(D) 71**

**Answer: C**

**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
Cinema( theater, address, capacity)
Which of the following options will be needed at the end of the SQL query
SELECT P1.address**

**FROM Cinema P1**

**such that it always finds the addresses of theaters with maximum capacity?**

**(A) WHERE P1.**

*capacity*>= All (select P2.*capacit*y 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)**Answer: A**

**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**

**Answer: D**

**Explanation:
**During first swap : 100 and 15 interchanges

During second swap : 100 and 50 interchanges

During third swap : 100 and 89 interchanges

Thanks for reading….