51. Suppose there
are log

_{n}sorted lists of n/log_{n}elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)
(A) O(n log log

_{n})
(B) Î¸(n log

_{n})
(C) â„¦(n log

_{n})
(D) â„¦(n

^{3/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 2

^{i+1}
(B) no greater than 2

^{i}
(C) no greater than 2

^{i–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 R

_{1}and R_{2}such that (R_{1}á´—R_{2})=R_{1}then which one of the following is to be satisfied for a lossless joint decomposition (→ indicates functional dependency)
(A) (R

_{1}∩R_{2})→R_{1}or R_{1}∩R_{2}→R_{2}
(B) R

_{1}∩R_{2}→R_{1}
(C) R

_{1}∩R_{2}→R_{2}
(D) R

_{1}∩R_{2}→R_{1}and R_{1}∩R_{2}→R_{2}
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. R

_{1}∩R_{2}→R_{1}
2. R

_{1}∩R_{2}→R_{2}
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