InterviewSolution
Saved Bookmarks
InterviewSolution
This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
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 |
| Answer» | |
| 2. |
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 |
| Answer» | |
| 3. |
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 |
| Answer» | |
| 4. |
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* |
| Answer» | |
| 5. |
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 |
| Answer» | |
| 6. |
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 |
| Answer» | |
| 7. |
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) |
| Answer» | |
| 8. |
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 |
| Answer» | |
| 9. |
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 |
| Answer» | |
| 10. |
What Boolean function does the circuit below realize ?(A) xz+x’z’(B) xz’+x’z(C) x’y’+yz(D) xy+y’z’ |
| Answer» None | |
| 11. |
Let R (A, B, C, D, E, P, G) be a relational schema in which the following functional dependencies are known to hold: AB → CD, DE → P, C → E, P → C and B → G. The relational schema R is(A) in BCNF(B) in 3NF, but not in BCNF(C) in 2NF, but not in 3NF(D) not in 2NF |
| Answer» | |
| 12. |
A non pipelined single cycle processor operating at 100 MHz is converted into a synchronous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respectively. The delay of the latches is 0.5 nsec. The speedup of the pipeline processor for a large number of instructions is(A) 4.5(B) 4.0(C) 3.33(D) 3.0 |
| Answer» | |
| 13. |
Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generated by the control unit. While designing the horizontal microprogrammed control unit, single address field format is used for branch control logic. What is the minimum size of the control word and control address register?(A) 125, 7(B) 125, 10(C) 135, 7(D) 135, 10 |
| Answer» | |
| 14. |
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.I. 81, 537, 102, 439, 285, 376, 305II. 52, 97, 121, 195, 242, 381, 472III. 142, 248, 520, 386, 345, 270, 307IV. 550, 149, 507, 395, 463, 402, 270 Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?(A) II and III only(B) I and III only(C) III and IV only(D) III only |
| Answer» | |
| 15. |
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be(A) regular(B) Complete(C) Hamiltonian(D) Euler |
| Answer» | |
| 16. |
Consider the following Boolean function of four variablesf(A, B, C, D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)The function is(A) independent of one variable(B) independent of two variables(C) independent of three variable(D) dependent on all the variables |
| Answer» | |
| 17. |
Arrange the following functions in increasing asymptotic order:A. n1/3B. en C. n7/4 D. n log9nE. 1.0000001n(A) A, D, C, E, B(B) D, A, C, E, B(C) A, C, D, E, B(D) A, C, D, B, E |
| Answer» | |
| 18. |
What Boolean function does the circuit below realize ?(A) xz+x’z’(B) xz’+x’z(C) x’y’+yz(D) xy+y’z’ |
| Answer» None | |
| 19. |
Let R (A, B, C, D) be a relational schema with the following functional dependencies:A → B, B → C,C → D and D → B. The decomposition of R into (A, B), (B, C), (B, D)(A) gives a lossless join, and is dependency preserving(B) gives a lossless join, but is not dependency preserving(C) does not give a lossless join, but is dependency preserving(D) does not give a lossless join and is not dependency preserving |
| Answer» None | |
| 20. |
Consider the code fragment written in C below :void f (int n){if (n <=1) {printf ("%d", n);}else {f (n/2);printf ("%d", n%2);}}What does f(173) print?(A) 010110101(B) 010101101(C) 10110101(D) 10101101 |
| Answer» | |
| 21. |
Consider the code fragment written in C below :void f (int n){if (n <= 1) {printf ("%d", n);}else {f (n/2);printf ("%d", n%2);}}Which of the following implementations will produce the same output for f(173) as the above code?P1void f (int n){if (n/2) {f(n/2);}printf ("%d", n%2);}P2void f (int n){if (n <=1) {printf ("%d", n);}else {printf ("%d", n%2);f (n/2);}}(A) Both P1 and P2(B) P2 only(C) P1 only(D) Neither P1 nor P2 |
| Answer» | |