UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 29)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 29)

Q 29. A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left leaf nodes in such a tree with 8 internal nodes will be :
 

(1) 30

(2) 33

(3) 45

(4) 125

 Answer: (2) 33

In a complete n-ary tree, L=(n−1)∗I+1   where L = No. of leaves, I = No. of Internel nodes

Here n = 5, I = 8

Therefore,  L = (5-1) * 8 + 1 = 4 * 8 + 1 = 33


In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.

Read More

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 28)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 28)

Q 28. The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number) :

(1) 45

(2) 72

(3) 360

(4) 450

Answer: (3) 360

Solution : Here we have octal number i.e. 8

So, its of 5 digit, therefore 5 x 8

Now 5 x 8 x 9 = 360.

Read More

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 27)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 27)

27. Match the following with respect to algorithm paradigms :

List - I	List - II
(a) The 8-Queen's Problem (b) Single-Source shortest paths (c) STRASSEN's Matrix multiplication (d) Optimal binary search trees	(i)     Dynamic programming (ii)    Divide and conquer (iii)   Greedy approch (iv)   Backtracking

 

             (a)           (b)          (c)          (d)

(1)         (iv)          (i)           (iii)          (ii)

(2)         (iv)         (iii)           (i)           (ii)

(3)         (iii)          (iv)          (ii)          (i)

(4)         (iv)         (iii)          (ii)          (i) 


Answer :  4.    (iv)         (iii)          (ii)          (i)


 
 

Read More

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 26)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 26)

Q 26. A binary search tree in which every non-leaf node has non-empty left and right sub-trees is called a strictly binary tree. Such a tree with 19 leaves :

1. cannot have more than 37 nodes
2. has exactly 37 nodes
3. has exactly 35 nodes
4. cannot have more than 35 nodes

 Answer : 2). has exactly 37 nodes

Reason : 

If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one. A strictly binary tree with N leaves always contains 2N – 1 nodes. 

Now we have 19 leaves, Therefore  (2 x 19) - 1 =  38 - 1 = 37

Read More

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 25)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 25)

Q 25. A text is made up of the characters a, b, c, d, e each occurring with the probability 0.08, 0.40,     0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of:

1. 2.4
2. 1.87
3. 3.0
4. 2.15 

 Answer: 4). 2.15
Solution:
 

Given 0.08 + 0.40 + 0.25 + 0.15 + 0.12 = 1

B : 0
C : 1 0
D : 1 1 0
A : 1 1 1 0
E : 1 1 1 1 1

Now,  B consume single bit, C consume 2 bits, D consume 3 bits, A and E consume 4 bits

Avg length = 4∗(A)+1∗(B)+2∗(C)+3∗(D)+4∗(E)
 
Avg length = 4∗(0.08)+1∗(0.4)+2∗(0.25)+3∗(0.15)+4∗(0.12)= 2.15

Read More

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 24)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 24)

Q 24. Which of the following algorithms solves the single-source shortest paths?

1. Prim's algorithm
2. Floys-Warshall algorithm
3. Johnson's algorithm
4. Dijkstra's algorithm

Answer : 4. Dijkstra's algorithm

Solution:

1. Prim's algorithm => Min Cost spanning tree
2. Floys-Warshall algorithm => All pair shortest path
3. Johnson's algorithm =>  All pair shortest path
4. Dijkstra's algorithm => Single source shortest path

Read More