GATE CSE 2015 SET-2
Q11.
The number of min-terms after minimizing the following Boolean Algebra is _________. {[{D}'+A{B}'+{A}'C+A{C}'D+{A}'{C}'{D}]}'Q12.
A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with \infty, and hence there cannot be any entry to the right of, or below a \infty. The following Young tableau consists of unique entries. When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a \infty). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _______.Q13.
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?Q14.
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n isQ15.
Consider the following C function. int fun(int n){ int x=1,k; if (n==1) return x; for (k=1; k \lt n; ++k) x = x + fun(k) * fun(n-k); return x; } The return value of fun(5) is ________.Q16.
Consider the following function written in the C programming language. void foo(char *a){ if ( *a && *a != ' '){ foo(a+1); putchar(*a); } } The output of the above function on input "ABCD \; \; EFGH" isQ17.
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?Q18.
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap isQ19.
A half Combinational Circuit is implemented with XOR and AND gates. A full Combinational Circuit is implemented with two half Combinational Circuits and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4-bit ripple-carry binary Combinational Circuit is implemented by using four full Combinational Circuits. The total propagation time of this 4-bit binary Combinational Circuit in microseconds is____________.Q20.
Consider the intermediate code given below. (1) i = 1 (2) j = 1 (3) t1 = 5 * i (4) t2 = t1 + j (5) t3 = 4 * t2 (6) t4 = t3 (7) a[t4] = -1 (8) j = j + 1 (9) if j\leq 5 goto (3) (10) i=i+1 (11) if i\lt 5 goto (2) The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are