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

## Monday, 27 October 2014

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
12.       The efficient data structure to insert/delete a number in a stored set of numbers is
(C) Doubly linked list  (D) Binary tree
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
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 + Î»)
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.

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| Î»
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.
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
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
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