UGC NET COMPUTER SCIENCE SOLVED PAPERS 2017-19 - UGC NET Computer Science November 2017 Paper 2

22. A list of n strings, each of length n, is sorted into lexicographic order using merge - sort algorithm. The worst case running time of this computation is :

  • Option : B
  • Explanation :
    When we are sorting an array of n integers, Recurrence relation for Total number of comparisons involved will be,
    T(n) = 2T(n/2) + (n) where (n) is the number of comparisons in order to merge 2 sorted subarrays of size n/2. = (nlog2n)
    Instead of integers whose comparison take O(1) time, we are given n strings. We can compare 2 strings in O(n) worst case.
    Therefore, the total number of comparisons now will be (n2log2n) where each comparison takes O(n) time now.
    In general, merge sort makes (nlog2n) comparisons, and runs in (nlog2n) time if each comparison can be done in O(1) time.
Cancel reply
Cancel reply

23. Postorder traversal of a given binary search tree T produces following sequence of keys:
3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

  • Option : D
  • Explanation :
    Since Inorder traversal of a BST always gives elements in increasing order. For this question sorted order of keys will always be the in-order tree traversal for post-order traversal. So, option (D) is correct.
Cancel reply
Cancel reply

24. Which of the following devices takes data sent from one network device and forwards it to the destination node based on MAC address?

  • Option : C
  • Explanation :
    Switch takes data from one network and forward it to other network based on MAC address. So option (C) is correct.
Cancel reply
Cancel reply

25. __________ do not take their decisions on measurements or estimates of the current traffic and topology.

  • Option : C
  • Explanation :
    Non-adoptive algorithms don't take their decisions on measurements or estimates of the current traffic and topology. So, option (C) is correct.
Cancel reply
Cancel reply