# UGC NET Computer Science and Applications Paper III December 2012 - Part 6

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)
(A) O(n log logn)
(B) θ(n logn)
(C) Ω(n logn)
(D) Ω(n3/2)
Explanation:
We can merge m arrays of each size n in in O(MN*LogN) time using Min Heap.
M = n/Logn
N = Logn
The time complexity = O(n/Logn * Logn * Log Log n) = O(nLogLogn)
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)
(A) (R1∩R2)→R1 or R1∩R2→R2
(B) R1∩R2→R1
(C) R1∩R2→R2
(D) R1∩R2→R1 and R1∩R2→R2
Explanation:
Let R be a relation schema.
Let F be a set of functional dependencies on R.
Let R1 and R2 form a decomposition of R.
The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in F+
1.  R1∩R2→R1
2.  R1∩R2→R2
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.       Skolemization 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