21. Given
the production rules of a grammar G1 as

S

_{1}→AB | aaB
A→a | Aa

B→b

and the production rules of a grammar G2 as

S

_{2}→aS_{2}bS_{2}| bS_{2}aS_{2}| Î»
Which of the following is correct statement?

(A) G1 is ambiguous and G2 is not ambiguous.

(B) G1 is ambiguous and G2 is ambiguous.

(C) G1 is not ambiguous and G2 is ambiguous.

(D) G1 is not ambiguous and G2 is not
ambiguous.

Answer: B

22. Given
a grammar : S

_{1}→Sc, S→SA|A, A→aSb|ab, there is a rightmost derivation S_{1}=>Sc =>SAC=>SaSbc. Thus, SaSbc is a right sentential form, and its handle is
(A) SaS (B)
be

(C) Sbe (D)
aSb

Answer: D

23. The
equivalent production rules corresponding to the production rules

S→SÎ±1|SÎ±2|Î²1|Î²2 is

(A) S→Î²1 | Î²2, A→Î±1A | Î±2A | Î»

(B) S→Î²1 | Î²2 | Î²1A | Î²2A,

A→Î±1A
| Î±2A

(C) S→Î²1 | Î²2, A→Î±1A | Î±2A

(D) S→Î²1 | Î²2 | Î²1A | Î²2A,

A→Î±1A | Î±2A | Î»

Answer: D

24. Given
a Non-deterministic Finite Automation (NFA) with states p and r as initial and
final states respectively transition table as given below

The minimum number of states required in
Deterministic Finite Automation (DFA) equivalent to NFA is

(A) 5 (B)
4

(C) 3 (D)
2

Answer: C

25. Which
is the correct statement(s) for Non Recursive predictive parser?

S1: First(Î±) = {t | Î± => * t Î² for some
string Î² } => *tÎ²

S2: Follow(X) = { a | S => * Î±Xa Î² for
some strings Î± and Î² }

(A) Both statements S1 and S2 are incorrect.

(B) S1 is incorrect and S2 is correct.

(C) S1 is correct and S2 is incorrect.

(D) Both statements S1 and S2 are correct.

Answer: D

26. Given
an open address hash table with load factor a < 1, the expected number of
probes in a successful search is

(A) Atmost
1/Î± ln (1-Î±/Î±)

(B) Atmost
1/Î± ln (1/1-Î±)

(C) Atleast
1/Î± ln (1/1-Î±)

(D) Atleast
1/Î± ln (Î±/1-Î±)

Answer: B

27. For
a B-tree of height h and degree t, the total CPU time used to insert a node is

(A) O(h log t) (B) O(t log h)

(C) O(t2h) (D)
O(th)

Answer: D

28. The
time complexity to build a heap with a list of n numbers is

(A) O(log n) (B)
O(n)

(C) O(n log n) (D) O(n

^{2})
Answer: B

29. The
value of postfix expression:

8 3 4 + - 3 8 2 / + * 2 $ 3+ is

(A) 17 (B) 131

(C) 64 (D) 52

Answer: D

30. Consider
the following statements for priority queue:

S1: It is a data structure in which the
intrinsic ordering of the elements does determine the result of its basic
operations.

S2: The elements of a priority queue may be
complex structures that are ordered on one or several fields.

Which of the following is correct?

(A) Both S1 and S2 are incorrect.

(B) S1 is correct and S2 is incorrect.

(C) SI is incorrect and S2 is correct.

(D) Both S1 and S2 are correct.

Answer: D

## 0 Comments