GATE Solved Paper 2017-19 - GATE 2017 Shift 2

46. Consider the recurrence function

  • Option : B
  • Explanation :
    T(n) = 2T(√n) + 1
    Put n = 2K
    T(2K) = 2T(2K/2) + 1
    T(2K) = δ(K)

    By master's theorem
    δ(K) = θ(K)
    T(2K) = θ(K)
    T(n) = θ(log n)   ∵ 2K = n
Cancel reply
Cancel reply

47. If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)2] equals _____

  • Option : A
  • Explanation :
    Using Linearity of Expectation, we can write,
    E[(X+2)2] = E[X2] + E[4X] + E[4]
    The Poisson distribution, mean and variance are same. Here Mean is given as 5. So variance should also be 5.
    Also,
    Variance = E[X2] – (E[X])2
    5 = E[X2] – 25.
    E[X2] = 30
    Thus E[(X+2)2] = 30 + 4*5 + 4 = 54.
Cancel reply
Cancel reply

48. Consider the following C function

  • Option : C
  • Explanation :
    for i = 1
    j will run from 1 to n by incrementing by '1' in each step 'j 'will run for n times
    For i=2
    j will run from 1 to n by incrementing by ‘2’ in each step j will run for n/2 times

    next time j will run for n/3 times
    and so on

    time complexity = n + n/2 + n/3 + n/4 + .....
    = n(1+1/2+1/3+.....)
    =nlogn
Cancel reply
Cancel reply

49. The pre-order transversal 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:

  • Option : B
  • Explanation :
    Given: Preorder ! 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20
    In order! 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
    Note: BST In order will give ascending order
    Corresponding BST is

    ∴ Post order is 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
Cancel reply
Cancel reply

50. Consider the C program fragment below which is meant to divide x by 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)?

  • Option : C
  • Explanation :
    Given, program is:
    (while (r y){
    }
    If we want to final value as Then initial value of r should be equal to x (Since y is subtracted from r each time in given code). q incremented by 1 (q is quotient here). To avoid undefined behavior, value of y should be greater than zero. Therefore, (q == 0)&&(r == x)&&(y > 0))
Cancel reply
Cancel reply