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)
Answer: A
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
Answer: D
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
Answer: C
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.
Answer: B
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
Answer: D
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
Answer: A
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)
Answer: B
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.
Answer: C
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
Answer: A
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
Answer: C
0 Comments