11. The
minimum number of nodes in a binary tree of depth d (root is at level 0) is
(A) 2d – 1 (B) 2d+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 = { an | 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:
L1 = {an bl
ak | n + l +k>5 }
L2 = {an bl
ak |n>5, l >3, k≤ l }
Which of the following is true?
(A) L1 is regular language and L2
is not regular language.
(B) Both L1 and L2 are
regular languages.
(C) Both L1 and L2 are
not regular languages.
(D) L1 is not regular language and
L2 is regular language.
Answer: A
16. LL
grammar for the language L = {an bm cn+m |
m≥0, n≥0} is
(A) S → aSc | S1 ; S1 →
bS1c | λ
(B) S → aSc | S1| λ ; S1
→ bS1c
(C) S → aSc | S1| λ ; S1
→ bS1c| λ
(D) S → aSc | λ ; S1 → bS1c|
λ
Answer: C
17. Assume
the statements S1 and S2 given as:
S1: Given a context free grammar G,
there exists an algorithm for determining whether L(G) is infinite.
S2: There exists an algorithm to determine
whether two context free grammars generate the same language.
Which of the following is true?
(A) S1 is correct and S2
is not correct.
(B) Both S1 and S2 are
correct.
(C) Both S1 and S2 are
not correct.
(D) S1 is not correct and S2
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