GATE CSE 2004
Q21.
Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2-variable Boolean function f=T+R, without using any additional hardware?Q22.
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the same value iii) All elements hash to the same value iv) Each element hashes to a different valueQ23.
A hard disk with a transfer rate of 10 Mbytes/second is constantly transferring data to memory using DMA. The processor runs at 600 MHz, and takes 300 and 900 clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is 20 Kbytes, what is the percentage of processor time consumed for the transfer operation?Q24.
Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?Q25.
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?Q26.
Consider the following C program main() { int x, y, m, n; scanf ("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m = x; n = y; while (m! = n) { if (m > n) m = m - n; else n = n - m; } print f ("% d", n); } The program computesQ27.
The inclusion of which of the following sets into S = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?Q28.
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n=d_{1}d_{2}...d_{m}. int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; } The loop invariant condition at the end of the i^{th} iteration is:Q29.
What does the following algorithm approximate? (Assume m \gt 1, e \gt 0). x = m; y = 1; while (x - y > e) { x = (x + y)/2; y = m/x; } print(x);Q30.
The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies: name, courseNo, \rightarrow grade rollNo, courseNo \rightarrow grade name \rightarrow rollNo rollNo \rightarrow name The highest normal form of this relation scheme is