11. The
minimum number of nodes in a binary tree of depth d (root is at level 0) is

(A) 2

^{d}– 1 (B) 2^{d+1}– 1
(C) d + 1 (D)
d

Answer: C

12. The
efficient data structure to insert/delete a number in a stored set of numbers
is

(A) Queue (B)
Linked list

(C) Doubly linked list (D) Binary tree

Answer: C

13. The
number of states in a minimal deterministic finite automaton corresponding to
the language L = { a

^{n}| n≥4 } is
(A) 3 (B)
4

(C) 5 (D)
6

Answer: C

14. Regular
expression for the language L = { w ∈
{0, 1}* | w has no pair of consecutive zeros} is

(A) (1 + 010)*

(B) (01 + 10)*

(C) (1 + 010)* (0 + Î»)

(D) (1 + 01)* (0 + Î»)

Answer: D

15. Consider
the following two languages:

L

_{1}= {a^{n}b*a*^{l}^{k}| n +*l*+k>5 }
L

_{2}= {a^{n}b*a*^{l}^{k}|n>5,*l*>3, k≤*l*}
Which of the following is true?

(A) L

_{1}is regular language and L_{2}is not regular language.
(B) Both L

_{1}and L_{2}are regular languages.
(C) Both L

_{1}and L_{2}are not regular languages.
(D) L

_{1}is not regular language and L_{2}is regular language.
Answer: A

16. LL
grammar for the language L = {a

^{n}b^{m}c^{n+m}| m≥0, n≥0} is
(A) S → aSc | S

_{1}; S_{1}→ bS_{1}c | Î»
(B) S → aSc | S

_{1}| Î» ; S_{1}→ bS_{1}c
(C) S → aSc | S

_{1}| Î» ; S_{1}→ bS_{1}c| Î»
(D) S → aSc | Î» ; S

_{1}→ bS_{1}c| Î»
Answer: C

17. Assume
the statements S

_{1}and S_{2}given as:
S

_{1}: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.
S

_{2}: There exists an algorithm to determine whether two context free grammars generate the same language.
Which of the following is true?

(A) S

_{1}is correct and S_{2}is not correct.
(B) Both S

_{1}and S_{2}are correct.
(C) Both S

_{1}and S_{2}are not correct.
(D) S

_{1}is not correct and S_{2}is correct.
Answer: A

18. The
number of eight-bit strings beginning with either 111 or 101 is ...............

(A) 64 (B) 128

(C) 265 (D) None of the above

Answer: A

19. Find
the number of ways to paint 12 offices so that 3 of them will be green, 2 of
them pink, 2 of them yellow and the rest ones white.

(A) 55,440 (B) 1,66,320

(C) 4.790E+08 (D) 39,91,680

Answer: B

20. Consider
the following statements:

(i) A graph in which there is a unique path
between every pair of vertices is a tree.

(ii) A connected graph with e = v – 1 is a
tree.

(iii) A graph with e = v – 1 that has no
circuit is a tree.

Which of the above statements is/are true?

(A) (i) & (iii) (B) (ii)
& (iii)

(C) (i) & (ii) (D) All of
the above

Answer: D

## 0 Comments