UGC NET COMPUTER SCIENCE SOLVED PAPERS 2014-16 - UGC NET Computer Science Paper 3 July 2016

31. The number of different binary trees with 6 nodes is ______.

  • Option : C
  • Explanation :
    The number of different binary trees with 6 nodes is fact(2n) / fact(n+1) * fac(n) where n is no nodes:
    If n= 6, then fact(2 * n) / fact(n+1) * fac(n)
    = fact(2 * 6) / fact(6 + 1) * fact(6)
    = fact(12) / fact(7) * fact(6)
    = 12 * 11 * 10 * 9 * 8 * fact(7) / fact(7) * fact(6)
    = 12 * 11 * 10 * 9 * 8 / 6 * 5 * 4 * 3 * 2
    = 6 * 11 * 2
    = 132.
    So, option (C) is correct.
Cancel reply
Cancel reply

32. Let A[1...n] be an array of n distinct numbers. If i A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?

  • Option : B
  • Explanation :
    There are n(n-1)/2 pairs such that i < j. For a pair (ai, aj), probability of being inversion is 1/2. Therefore expected value of inversions = 1/2 * (n(n-1)/2) = n(n-1)/4.
Cancel reply
Cancel reply

33. Which one of the following array represents a binary max-heap?

  • Option : C
  • Explanation :
    For max heap we will compare parent node(i) with its left-child(2 * i) and right-child(2 * i + 1):
  • In first option node(2) < node(5) which is violating the max-heap property.
  • In second option node node(2) < node(5) which is violating the max-heap property.
  • In third option there is no violation.
  • In fourth option node(3) < node(7) which is violating the max-heap property.
  • So, option (C) is correct.
Cancel reply
Cancel reply

34. Match the following :

(a) Huffman codes   (i) O(n2)
(b) Optimal polygon triangulation(ii) θ(n3)
(c) Activity selection problem(iii) O(nlgn)
(d) Quicksort(iv) θ(n)
 (a)(b)(c)(d)
(1)(i)(ii)(iv)(iii)
(2)(i)(iv)(ii)(iii)
(3)(iii)(ii)(iv)(i)
(4)(iii)(iv)(ii)(i)

  • Option : C
  • Explanation :
    • Huffman codes takes O(nlgn) time.
    • Optimal polygon triangulation takes θ(n3) time
    • Activity selection problem takes θ(n) time 
    • Quicksort takes O(n2) time
    So, option (C) is correct.
Cancel reply
Cancel reply

35. Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined ?

  • Option : C
  • Explanation :
    We have to find 364 in BST:
  • In first option 925 is root node, our key is less then 925 so we go for left BST. Next node is 221 → 912 → 245 → 899 → 259 → 363 → 364 respectively.
  • In second option 3 is root node, we go for right BST i.e. 400 → 388 → 220 → 267 → 383 → 382 → 279 → 364 respectively.
  • In third option 926 is root node, we go for left BST i.e. 203 → 912 → 241 next key is 913 we cant go for 913 after 241 because we are already in left BST of 912 our key will be surely in left BST of 912. This option is incorrect.
  • In fourth option 3 is root node, we go for right BST i.e. 253 → 402 → 399 → 331 → 345 → 398 → 364.
  • So, option (C) is correct.
Cancel reply
Cancel reply