December 2014 - Paper 3

1. Home
2. UGC NET Computer Science Solved Papers
3. December 2014
4. Paper 3

31:  

Match the following .

     List- I                                                    List - II

a. Bucket sort                                      i. O(n3/gn)

b. Matrix chain multiplication           ii. O(n3) 

c. Huffman codes                             iii. O(nlgn)

d. All pairs shortest paths               iv. O(n)

A.	a   b   c   d  iv   ii   i   iii
B.	a   b   c   d  ii   iv   i   iii
C.	a   b   c   d  iv   ii   iii   i
D.	a   b   c   d  iii   ii   iv   i
	Answer Report Discuss
	Option: D Explanation : Click on Discuss to view users comments. Write your comments here: Updating your Comments.. Updating your Comments..

32:  

We can show that the clique problem is NP-hard by proving that

A.	CLIQUE ≤ P 3-CNF SAT
B.	CLIQUE ≤ PVERTEX_COVER
C.	CLIQUE ≤  P SUBSET_SUM
D.	None of the above
	Answer Report Discuss
	Option: D Explanation : Click on Discuss to view users comments. Write your comments here: Updating your Comments.. Updating your Comments..

33:  

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
	Answer Report Discuss
	Option: D Explanation : Click on Discuss to view users comments. Write your comments here: Updating your Comments.. Updating your Comments..

34:  

Consider the problem of a chain <A₁, A₂, A₃> of three matrices. Suppose that the dimensions of the matrices are 10 x 100, 100 x 5 and 5 x 50 respectively. There are two different ways of parenthesization : (i) ((A₁ A₂)A₃) and (ii) (A₁(A₂ A₃)) 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
	Answer Report Discuss
	Option: D Explanation : Click on Discuss to view users comments. Write your comments here: Updating your Comments.. Updating your Comments..

35:  

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 s~quence 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
	Answer Report Discuss
	Option: C Explanation : Click on Discuss to view users comments. Write your comments here: Updating your Comments.. Updating your Comments..

• «
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• »