Related InterviewSolutions

• A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors.n3 can be expressed as(A) n1 + n2 – 1(B) n1 – 2(C) [((n1 + n2)/2)](D) n2 – 1
• Which of the following languages is (are) non-regular?L1 = {0m1n | 0 ≤ m ≤ n ≤ 10000}L2 = {w | w reads the same forward and backward}L3 = {w ∊ {0, 1} * | w contains an even number of 0’s and an even number of 1’s}(A) L2 and L3 only(B) L1 and L2 only(C) L3 only(D) L2 only
• Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?(A) m ≤ 2n(B) n ≤ m(C) M has one accept state(D) m = 2n
• If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?(A) Set of all strings that do not end with ab(B) Set of all strings that begin with either an a or a b(C) Set of all strings that do not contain the substring ab,(D) The set described by the regular expression b*aa*(ba)*b*
• Consider a CFG with the following productions.S → AA | BA → 0A | A0 | 1B → 0B00 | 1S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is(A) {0n 102n | n ≥ 1}(B) {0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l}(C) {0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l}(D) The set of all strings over {0, 1} containing at least two 0’s(E) None of the above
• Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.Which one of the following is TRUE?(A) L1 = L2(B) L1 ⊂ L2(C) L1 ∩ L2‘ = ∅(D) L1 ∪ L2 ≠ L1
• Which of the following is TRUE?(A) The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)(B) The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)(C) The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)(D) The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)
• Consider the following languages.L1 = {ai bj ck | i = j, k ≥ 1}L1 = {ai bj | j = 2i, i ≥ 0}Which of the following is true?(A) L1 is not a CFL but L2 is(B) L1 ∩ L2 = ∅ and L1 is non-regular(C) L1 ∪ L2 is not a CFL but L2 is(D) There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
• Consider the C program below. What does it print?# include <stdio.h># define swapl (a, b) tmp = a; a = b; b = tmpvoid swap2 ( int a, int b){int tmp;tmp = a; a = b; b = tmp;}void swap3 (int*a, int*b){int tmp;tmp = *a; *a = *b; *b = tmp;}int main (){int num1 = 5, num2 = 4, tmp;if (num1 < num2) {swap1 (num1, num2);}if (num1 < num2) {swap2 (num1 + 1, num2);}if (num1 >= num2) {swap3 (&num1, &num2);}printf ("%d, %d", num1, num2);}/* Add code here. Remove these lines if not writing code */(A) 5, 5(B) 5, 4(C) 4, 5(D) 4, 4
• What Boolean function does the circuit below realize ?(A) xz+x’z’(B) xz’+x’z(C) x’y’+yz(D) xy+y’z’