## UGC Net Computer Science December-12 Page 6 Solved

51. Suppose there are logn sorted lists of n logn elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)

52. Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping

int i;

program Main( )

{

i = 10;

call f ( );

}

procedure f( )

{

int i = 20;

call g ( );

}

procedure g( )

{

print i;

}

Let x be the value printed under static scoping and y be the value printed under dynamic scoping. Then x and y are

(A) x = 10, y = 20

(B) x = 20, y = 10

(C) x = 20, y = 20

(D) x = 10, y = 10

53. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i,then the word w is of length

(A) no greater than 2i+1

(B) no greater than 2i

(C) no greater than 2i–1

(D) no greater than i

54. The Object Modelling Technique (OMT) uses the following three kinds of model to describe a system

(A) Class Model, Object Model and Analysis Model.

(B) Object Model, Dynamic Model,and Functional Model.

(C) Class Model, Dynamic Model and Functional Model.

(D) Object Model, Analysis Model and Dynamic Model.

55. The factors that determine the quality of a software system are

(A) correctness, reliability

(B) efficiency, usability, maintainability

(C) testability, portability, accuracy,error tolerances, expandability,access control, audit.

(D) All of the above

56. If a relation with a Schema R is decomposed into two relations R1 and R2 such that (R1 Ụ R2) = R1 then which one of the following is to be satisfied for a lossless joint decomposition (→ indicates functional

dependency)

57. Given the following statements :

(i) Recursive enumerable sets are closed under complementation.

(ii) Recursive sets are closed under complementation.

Which is/are the correct statements ?

(A) only (i)

(B) only (ii)

(C) both (i) and (ii)

(D) neither (i) nor (ii)

58. Skolmization is the process of

(A) bringing all the quantifiers in the beginning of a formula in FDL.

(B) removing all the universal quantifiers.

(C) removing all the existential quantifiers.

(D) all of the above.

59. Which level of Abstraction describes how data are stored in the data base ?

(A) Physical level

(B) View level

(C) Abstraction level

(D) Logical level

60. The transform which possesses the “multi-resolution” property is

(A) Fourier transform

(B) Short-time-Fourier transform

(C) Wavelet transform

(D) Karhunen-Loere transform