CBSE UGC NET Computer Science Paper III August 2016 (Re-test) - Part 4

31.       Consider the problem of a chain <A1, A2, A3, A4> of four matrices. Suppose that the dimensions of the matrices A1, A2, A3 and A4 are 30 × 35, 35 × 15, 15 × 5 and 5 × 10 respectively. The minimum number of scalar multiplications needed to compute the product A1A2A3A4 is ................
(A) 14875          (B) 21000
(C) 9375            (D) 11875
32.       Consider a hash table of size m = 10000, and the hash function h(K)=floor(m(KAmod1)) for A = (√5 – 1)/2. The key 123456 is mapped to location ...............
(A) 46     (B) 41
(C) 43     (D) 48
33.       Consider a weighted complete graph G on the vertex set {v1, v2, …. vn} such that the weight of the edge (vi, vj) is 4 |i – j|. The weight of minimum cost spanning tree of G is:
(A) 4n2               (B) n
(C) 4n – 4          (D) 2n – 2
34.       A priority queue is implemented as a max-heap. Initially, it has five elements. The level-order traversal of the heap is as follows:
20, 18, 15, 13, 12
Two new elements ‘10’ and ‘17’ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:
(A) 20, 18, 17, 15, 13, 12, 10
(B) 20, 18, 17, 12, 13, 10, 15
(C) 20, 18, 17, 10, 12, 13, 15
(D) 20, 18, 17, 13, 12, 10, 15
35.       If there are n integers to sort, each integer has d digits, and each digit is in the set  {1, 2, …, k}, radix sort can sort the numbers in:
(A) O (k (n + d))            (B) O (d (n + k))
(C) O ((n + k) l g d)       (D) O ((n + d) l g k)

36.       Match the following:
a. Prim’s algorithm                  i. O(V2E)
b. Bellman-Ford algorithm     ii. O(VE lgV)
c. Floyd-Warshall algorithm   iii. O(E lgV)
d. Johnson’s algorithm           iv. O(V3)
Where V is the set of nodes and E is the set of edges in the graph.
Codes :
a    b   c   d
(A) i    iii   iv  ii
(B) i    iii   ii   iv
(C) iii  i    iv   ii
(D) iii  i    ii   iv
37.       Constructors have ............. return type.
(A) void              (B) char
(C) int                 (D) no
38.       Method over-riding can be prevented by using final as a modifier at ...............
(A) the start of the class.
(B) the start of method declaration.
(C) the start of derived class.
(D) the start of the method declaration in the derived class.
39.       Which of the following is a correct statement?
(A) Composition is a strong type of association between two classes with full ownership.
(B) Composition is a strong type of association between two classes with partial ownership.
(C) Composition is a weak type of association between two classes with partial ownership.
(D) Composition is a weak type of association between two classes with strong ownership.