GATE IT 2006
Q11.
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i \neq 0, isQ12.
Let L be a context-free language and M a regular language. Then the language L \cap M isQ13.
In the context-free grammar below, S is the start symbol, a and b are terminals, and \epsilon denotes the empty string. S \to aSAb \mid \epsilon A \to bA \mid \epsilon The grammar generates the languageQ14.
In the context-free grammar below, S is the start symbol, a and b are terminals, and\epsilon denotes the empty string S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon Which of the following strings is NOT generated by the grammar?Q15.
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that \begin{array}{l|l}\hline \text{$d(P) = 5$ units } & \text{ $f(P) = 12$ units } \\\hline \text{$d(Q) = 6$ units} & \text{ $f(Q) = 10$ units} \\\hline \text{$d(R) = 14$ unit} & \text{$f(R) = 18$ units} \\\hline \end{array} Which one of the following statements is TRUE about the graph?Q16.
Let P, Q and R be sets, let \triangle denote the symmetric difference operator defined as P\triangle Q=(P \cup Q) - (P \cap Q). Using Venn diagrams, determine which of the following is/are TRUE? I. P \Delta(Q \cap R)=(P \Delta Q) \cap(P \Delta R) II. P \cap(Q \cap R)=(P \cap Q) \Delta(P \Delta R)Q18.
The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21 A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? 110111100111010Q19.
The boolean function for a combinational circuit with four inputs is represented by the following Karnaugh map.Which of the product terms given below is an essential prime implicant of the function?Q20.
Which of the following DMA transfer modes and interrupt handling mechanisms will enable the highest I/O band-width?