21. Given
the production rules of a grammar G1 as
S1→AB | aaB
A→a | Aa
B→b
and the production rules of a grammar G2 as
S2→aS2bS2 |
bS2aS2 | λ
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 : S1→Sc, S→SA|A, A→aSb|ab, there is a rightmost derivation
S1=>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(n2)
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