Sample Questions, Previous Year Solved Papers, Study Materials For Competitive Examinations Like UGC NET, SET And GATE Computer Science.

## Saturday, 8 October 2016

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.