UGC NET november 2017 paper 2 computer science & application solved Q21-Q30

21. Consider an array representation of an n element binary heap where the elements are stored
from index 1 to index n of the array. For the element stored at index i of the array (i<=n),
the index of the parent is :

(1) floor ((i+1)/2)
(2) ceiling ((i+1)/2)
(3) floor (i/2)
(4) ceiling (i/2)

Correct Answer is: (3) floor (i/2)
As shown below the root of the 13 and 10 are floor of the 4 and 5 respectively.

22. The following numbers are inserted into an empty binary search tree in the given order :
10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree ?

(1) 3
(2) 4
(3) 5
(4) 6

Correct Answer is: (1) 3
Here, height is longest path from root to the leaf node. As shown green number in below image indicates the count of the tree edges which has max height.

23. Let G be an undirected connected graph with distinct edge weight. Let Emax be the edge
with maximum weight and Emin the edge with minimum weight. Which of the following
statements is false ?

(1) Every minimum spanning tree of G must contain Emin.
(2) If Emax is in minimum spanning tree, then its removal must disconnect G.
(3) No minimum spanning tree contains Emax.
(4) G has a unique minimum spanning tree.

Correct Answer is: (3) No minimum spanning tree contains Emax.

24. 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 :

(1) O(n log n)
(2) O(n2 log n)
(3) O(n2 + log n)
(4) O(n3)

Correct Answer is: (2) O(n2 log n)

25. 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 ?

(1) 3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15
(2) 20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
(3) 20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3
(4) 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20

Correct answer is: (4) 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20
3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14
Here, the root of the binary tree is 14 (last element), as it's post-order traversal.
Right side of the tree contains bigger elements than 14
Left side of the tree contains bigger elements than 14
So, the first number >14 on left of root (14) (check from right to left).
=>root of right sub-tree is 15
So, the first number <14 on left of root (14) (check from right to left).
=>root of left sub-tree is 4
now we have two sequences: right tree and left tree
right tree:  17, 16, 20, 18, 15,
left tree: 3, 5, 7, 9, 4
Here, also similarly  find left and right sub-tree of both tree root-right(15) and the root-left(4).
So, final binary tree is

26. Which of the following devices takes data sent from one network device and forwards it to

the destination node based on MAC address ?
(1) Hub
(2) Modem
(3) Switch
(4) Gateway

Correct answer is: (3) Switch

27. __________ do not take their decisions on measurements or estimates of the current traffic

and topology.
(1) Static algorithms
(2) Adaptive algorithms
(3) Non - adaptive algorithms
(4) Recursive algorithms

Correct answer is: (3) Non - adaptive algorithms

28. The number of bits used for addressing in Gigabit Ethernet is __________.

(1) 32 bits
(2) 48 bits
(3) 64 bits
(4) 128 bits

Correct answer is: (2) 48 bits

29. Which of the following layer of OSI Reference model is also called end-to-end layer ?

(1) Network layer
(2) Datalink layer
(3) Session layer
(4) Transport layer

Correct answer is: (4) Transport layer

30. The IP address __________ is used by hosts when they are being booted.

(1) 0.0.0.0
(2) 1.0.0.0
(3) 1.1.1.1
(4) 255.255.255.255

Correct answer is:  (1) 0.0.0.0