# UGC NET Computer Science Solved Paper III December 2014 - Part 4

31.       Any decision tree that sorts n elements has height
(A) W (n) (B) W (lgn)
(C) W (nlgn) (D) W (n2)
32.       Match the following :
List – I                                       List – II
a. Bucket sort                           i. O(n3lgn)
b. Matrix chain multiplication ii. O(n3)
c. Huffman codes                    iii. O(nlgn)
d. All pairs shortest paths       iv. O(n)
Codes :
a    b   c   d
(A) iv    ii    i   iii
(B) ii    iv    i   iii
(C) iv   ii    iii   i
(D) iii   ii    iv   i
33.       We can show that the clique problem is NP-hard by proving that
(A) CLIQUE £ P 3-CNF_SAT
(B) CLIQUE £ P VERTEX_COVER
(C) CLIQUE £ P SUBSET_SUM
(D) None of the above
34.       Dijkstra algorithm, which solves the single-source shortest--paths problem, is a ................, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a ...............
(A) Greedy algorithm, Divide-conquer algorithm
(B) Divide-conquer algorithm, Greedy algorithm
(C) Greedy algorithm, Dynamic programming algorithm
(D) Dynamic programming algorithm, Greedy algorithm
35.       Consider the problem of a chain <A1, A2, A3> of three matrices. Suppose that the dimensions of the matrices are 10 × 100, 100 × 5 and 5 × 50 respectively. There are two different ways of parenthesization : (i) ((A1 A2)A3) and (ii) (A1(A2 A3)). Computing the product according to the first parenthesization is .................. times faster in comparison to the second parenthesization.
(A) 5       (B) 10
(C) 20     (D) 100
36.       Suppose that we have numbers between 1 and 1000 in a binary search tree and we want to search for the number 365. Which of the following sequences could not be the sequence of nodes examined ?
(A) 4, 254, 403, 400, 332, 346, 399, 365
(B) 926, 222, 913, 246, 900, 260, 364, 365
(C) 927, 204,913, 242, 914, 247, 365
(D) 4, 401, 389, 221, 268, 384, 383, 280, 365
(A) Asynchronized methods (B) Synchronized methods
(C) Serialized methods           (D) None of the above
38.       How to express that some person keeps animals as pets ?
39.       Converting a primitive type data into its corresponding wrapper class object instance is called
(A) Boxing                     (B) Wrapping
(C) Instantiation           (D) Autoboxing