search
Log In
Question Paper GATE 2008 CSE Organizing Institute for GATE 2008 was IISc Bangalore

Recent questions tagged gate2008

23 votes
1 answer
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}$
asked Nov 27, 2016 in Databases Arjun 3.1k views
18 votes
3 answers
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[10] , 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))$ ;
asked Apr 23, 2016 in Algorithms jothee 2.7k views
23 votes
4 answers
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$%
asked Apr 23, 2016 in CO and Architecture jothee 3.1k views
42 votes
5 answers
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[1024][1024]; int i, j; /*Initialize ... elements have the same cache index as $ARR[0][0]$? $ARR[0][4]$ $ARR[4][0]$ $ARR[0][5]$ $ARR[5][0]$
asked Apr 23, 2016 in CO and Architecture jothee 5.8k views
24 votes
6 answers
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[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 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$
asked Apr 23, 2016 in Algorithms jothee 2.8k views
36 votes
4 answers
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
asked Apr 23, 2016 in CO and Architecture jothee 5.9k views
19 votes
5 answers
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$
asked Apr 23, 2016 in Algorithms jothee 1.6k views
27 votes
2 answers
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]$
asked Apr 23, 2016 in Algorithms jothee 4.2k views
52 votes
6 answers
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.
asked Sep 27, 2014 in DS Akshay Jindal 11k views
36 votes
3 answers
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]$
asked Sep 12, 2014 in Algorithms Kathleen 4.2k views
31 votes
6 answers
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}$
asked Sep 12, 2014 in Algorithms Kathleen 3.2k views
45 votes
3 answers
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
asked Sep 12, 2014 in CO and Architecture Kathleen 8.8k views
28 votes
3 answers
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[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 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)$
asked Sep 12, 2014 in Algorithms Kathleen 7.4k views
47 votes
4 answers
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[1024][ ... array $ARR$. The total size of the tags in the cache directory is: $32$ $Kbits$ $34$ $Kbits$ $64$ $Kbits$ $68$ $Kbits$
asked Sep 12, 2014 in CO and Architecture Kathleen 9.1k views
46 votes
4 answers
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
asked Sep 12, 2014 in Databases Kathleen 10.6k views
42 votes
3 answers
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
asked Sep 12, 2014 in Databases Kathleen 7.6k views
162 votes
11 answers
17
19 votes
2 answers
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$
asked Sep 12, 2014 in Operating System Kathleen 6.4k views
35 votes
4 answers
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..
asked Sep 12, 2014 in Operating System Kathleen 9.7k views
31 votes
6 answers
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
asked Sep 12, 2014 in CO and Architecture Kathleen 8.7k views
53 votes
6 answers
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$
asked Sep 12, 2014 in Operating System Kathleen 10.8k views
29 votes
5 answers
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$
asked Sep 12, 2014 in DS Kathleen 6.3k views
18 votes
6 answers
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);$
asked Sep 12, 2014 in Programming Kathleen 3k views
28 votes
6 answers
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$
asked Sep 12, 2014 in Programming Kathleen 6.1k views
38 votes
3 answers
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
asked Sep 12, 2014 in Computer Networks Kathleen 7.4k views
23 votes
6 answers
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
asked Sep 12, 2014 in Computer Networks Kathleen 7.7k views
19 votes
2 answers
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$
asked Sep 12, 2014 in Computer Networks Kathleen 4.8k views
22 votes
4 answers
28
In the slow start phase of the TCP congestion algorithm, the size of the congestion window: does not increase increase linearly increases quadratically increases exponentially
asked Sep 12, 2014 in Computer Networks Kathleen 4.4k views
28 votes
3 answers
29
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if The SLR(1) parser for G has S-R conflicts The LR(1) parser for G has S-R conflicts The LR(0) parser for G has S-R conflicts The LALR(1) parser for G has reduce-reduce conflicts
asked Sep 12, 2014 in Compiler Design Kathleen 6.5k views
29 votes
7 answers
30
Which of the following are true? A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation Multi-level access link (or display) arrangement is needed to arrange ... scheme for activation records II and V only I, III and IV only I, II and V only II, III and V only
asked Sep 12, 2014 in Compiler Design Kathleen 6.6k views
...