# UGC NET Computer Science Previous Questions June 2013 Paper 2 - Part 3

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.
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
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 | λ
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
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.

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-α)
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)
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)
29.       The value of postfix expression:
8 3 4 + - 3 8 2 / + * 2 \$ 3+ is
(A) 17                 (B) 131
(C) 64                 (D) 52
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.