Question Paper GATE 2008 CSE Organizing Institute for GATE 2008 was IISc Bangalore

# Recent questions tagged gate2008 1
Consider the following ER diagram The minimum number of tables needed to represent $M$, $N$, $P$, $R1$, $R2$ is Which of the following is a correct attribute set for one of the tables for the minimum number of tables needed to represent $M$, $N$, $P$, $R1$, $R2$? ${M1, M2, M3, P1}$ ${M1, P1, N1, N2}$ ${M1, P1, N1}$ ${M1, P1}$
2
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if( ... $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
3
Consider a machine with a $2$-way set associative data cache of size $64$ $Kbytes$ and block size $16$ $bytes$. The cache is managed using $32$ $bit$ virtual addresses and the page size is $4$ $Kbytes$. A program to be run on this machine begins as follows: double ARR[1024 ... made by the program are those to array $ARR$. The cache hit ratio for this initialization loop is: $0$% $25$% $50$% $75$%
4
Consider a machine with a $2$-way set associative data cache of size $64$ Kbytes and block size $16$ bytes. The cache is managed using $32$ bit virtual addresses and the page size is $4$ Kbytes. A program to be run on this machine begins as follows: double ARR; int i, j; /*Initialize ... elements have the same cache index as $ARR$? $ARR$ $ARR$ $ARR$ $ARR$
5
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X = Y = Z = 0; X = 1; Y = 2; Z = 3; for(i = 2; i <= n; i++){ ... X[i]; Z[i] = 3 * X[i]; } return X[n]; } $f1(8)$ and $f2(8)$ return the values $1661$ and $1640$ $59$ and $59$ $1640$ and $1640$ $1640$ and $1661$
6
Delayed branching can help in the handling of control hazards The following code is to run on a pipelined processor with one branch delay slot: I1: ADD $R2 \leftarrow R7 + R8$ I2: Sub $R4 \leftarrow R5 &ndash; R6$ I3: ADD $R1 \leftarrow R2 + R3$ I4: STORE ... Which of the instructions I1, I2, I3 or I4 can legitimately occupy the delay slot without any program modification? I1 I2 I3 I4
7
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. The value of $x_5$ is $5$ $7$ $8$ $16$
8
The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$ ... , implies that there is a subset whose elements sum to $W$? $X[1, W]$ $X[n, 0]$ $X[n, W]$ $X[n-1, n]$
9
$G$ is a graph on $n$ vertices and $2n-2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ vertices, the induced subgraph has at most $2k-2$ edges ... are at least $2$ edge-disjoint paths between every pair of vertices. There are at least $2$ vertex-disjoint paths between every pair of vertices.
10
The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$, with $n$ rows ... $X[i, j] = X[i-1, j] \wedge X[i, j-a_i]$ $X[i, j] = X[i-1, j] \wedge X[i-1, j-a_i]$
11
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. Which of the following recurrences does $x_n$ satisfy? $x_n = 2x_{n-1}$ $x_n = x_{\lfloor n/2 \rfloor} + 1$ $x_n = x_{\lfloor n/2 \rfloor} + n$ $x_n = x_{n-1} + x_{n-2}$
12
Delayed branching can help in the handling of control hazards For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false, The instruction following the conditional branch instruction in memory is executed The first ... executed The first instruction in the taken path is executed The branch takes longer to execute than any other instruction
13
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X = Y = Z = 0; X = 1; Y = 2; Z = 3; for(i = 2; i <= n; i++){ X ... $f1(n)$ and $f2(n)$ are $\Theta(n)$ and $\Theta(n)$ $\Theta(2^n)$ and $\Theta(n)$ $\Theta(n)$ and $\Theta(2^n)$ $\Theta(2^n)$ and $\Theta(2^n)$
14
Consider a machine with a $2$-way set associative data cache of size $64$ $Kbytes$ and block size $16$ $bytes$. The cache is managed using $32$ $bi$t virtual addresses and the page size is $4$ $Kbytes$. A program to be run on this machine begins as follows: double ARR[ ... array $ARR$. The total size of the tags in the cache directory is: $32$ $Kbits$ $34$ $Kbits$ $64$ $Kbits$ $68$ $Kbits$
15
Consider the following relational schemes for a library database: Book (Title, Author, Catalog_no, Publisher, Year, Price) Collection(Title, Author, Catalog_no) with the following functional dependencies: $\text{Title Author }\rightarrow\text{ Catalog_no}$ ... are in $3NF$ only Book is in $2NF$ and Collection in $3NF$ Both Book and Collection are in $2NF$ only
16
Let R and S be two relations with the following schema $R(\underline{P,Q}, R1, R2, R3)$ $S(\underline{P,Q}, S1, S2)$ where $\left\{P, Q\right\}$ is the key for both schemas. Which of the following queries are equivalent? $\Pi_P \left(R \bowtie S\right)$ ... Only I and II Only I and III Only I, II and III Only I, III and IV
17
A processor uses $36$ bit physical address and $32$ bit virtual addresses, with a page frame size of $4$ Kbytes. Each page table entry is of size $4$ ... level page tables are respectively $\text{20,20,20}$ $\text{24,24,24}$ $\text{24,24,20}$ $\text{25,25,24}$
18
A process executes the following code for(i=0; i<n; i++) fork(); The total number of child processes created is $n$ $2^n-1$ $2^n$ $2^{n+1} - 1$
19
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes? In deadlock prevention, the request for resources is always granted if the resulting state is safe In deadlock avoidance, the request for resources is ... state is safe Deadlock avoidance is less restrictive than deadlock prevention Deadlock avoidance requires knowledge of resource requirements apriori..
20
Which of the following statements about synchronous and asynchronous I/O is NOT true? An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of ... /O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O
21
The $P$ and $V$ operations on counting semaphores, where s is a counting semaphore, are defined as follows: $P(s):$ $s=s-1;$ If $s < 0$ then wait; $V(s):$ $s=s+1;$ If $s \leq0$ then wake up process waiting on s; Assume that $P_b$ and $V_b$ the wait and signal operations on ... $x_b$ and $y_b$ are respectively $0$ and $0$ $0$ and $1$ $1$ and $0$ $1$ and $1$
22
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers $1, 2, 3, 4, 5, 6, 7$ in the given order. What will be the contents of the list after function completes execution? struct node { int value; struct ... $2, 1, 4 ,3, 6, 5, 7$ $1, 3, 2, 5, 4, 7, 6$ $2, 3, 4, 5, 6, 7, 1$
23
Choose the correct option to fill $?1$ and $?2$ so that the program below prints an input string in reverse order. Assume that the input string is terminated by a new line character. void reverse(void) { int c; if(?1) reverse(); ?2 } main() { printf("Enter text"); printf("\n"); reverse(); printf ... $?2$ is $putchar(c);$ $?1$ is $((c = getchar() ) != '\setminus n')$ $?2$ is $putchar(c);$
24
What is printed by the following C program? int f(int x, int *py, int **ppz) { int y, z; **ppz += 1; z = **ppz; // corrected z = *ppz; to z = **ppz; *py += 2; y = *py; x += 3; return x+y+z; } void main() { int c, *b, **a; c = 4; b = &c; a = &b; printf("%d", f(c, b, a)); } $18$ $19$ $21$ $22$
25
A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a $\text{socket()}$, a $\text{bind()}$ and a $\text{listen()}$ system call in that order, following which it is preempted. ... $\text{connect()}$ system call returns an error $\text{connect()}$ system call results in a core dump
26
A computer on a $10$ $Mbps$ network is regulated by a token bucket. The token bucket is filled at a rate of $2$ $Mbps$. It is initially filled to capacity with $16$ $Megabits$. What is the maximum duration for which the computer can transmit at the full $10$ $Mbps$? $1.6$ seconds $2$ seconds $5$ seconds $8$ seconds
27
If a class $B$ network on the Internet has a subnet mask of $255.255.248.0$, what is the maximum number of hosts per subnet? $1022$ $1023$ $2046$ $2047$