Description: GATE Exam Previous Year Question Paper Solution Computer Science(CS) - 2008 | |

Number of Questions: 85 | |

Created by: Aliensbrain Bot | |

Tags: Computer Science GATE CS Previous Year Paper |

Attempted
0/85
Correct 0
Score 0

‹
›

$\lim_{x \to \infty}\frac{x-\sin x}{x+\cos x}$ equals

Given f_{1}, f_{3} and f in canonical sum of products form (in decimal) for the circuit.

$f_1 = \Sigma m(4, 5, 6, 7, 8)$

$f_3 = \Sigma m(1, 6, 15)$

$f = \Sigma m(1, 6, 8, 15)$

Then f_{2} is

In the IEEE floating point representation, the hexadecimal value 0x00000000 corresponds to

Some code optimizations are carried out on the intermediate code because

What is the maximum size of data that the application layer can pass on to the TCP layer below?

Which of the following system calls results in the sending of SYN packets?

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

Which of the following statements is true for every planar graph on n vertices?

If $P, Q, R$ are Boolean variables, then

$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$ simplifies to

^{4} − 16x^{3} + 24x^{2} + 37?

$\left[\begin{array}{cc}1 & 0 \\ 0 & 0 \end{array} \right]\left[\begin{array}{cc}0 & 1 \\ 0 & 0 \end{array} \right] \left[\begin{array}{cc}1 & -1 \\ 1 & 1 \end{array} \right]$ and $\left[\begin{array}{cc}-1 & 0 \\ 1 & -1 \end{array} \right]$

$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent?

I. $P ∨ \neg Q$

||. $\neg(\neg P ∧ Q)$

|||. $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$

IV. $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$

Which of the following first order logic statements represents the following: Each finite state automaton has an equivalent pushdown automaton

f(n) = 2^{n}

g(n) = n!

h(n) = n^{logn}

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

Which of the following tuple relational calculus expression(s) is/are equivalent to $\forall t \in r \left(P\left(t\right)\right)$?

I. $\neg \exists t \in r \left(P\left(t\right)\right)$

II. $\exists t \notin r \left(P\left(t\right)\right)$

III. $\neg \exists t \in r \left(\neg P\left(t\right)\right)$

IV. $\exists t \notin r \left(\neg P\left(t\right)\right)$

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

In the slow start phase of the TCP congestion control algorithm, the size of the congestion window

I. 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

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the

programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic storage allocation

IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot

be implemented with a stack-based allocation scheme for activation records

V. Programming languages which permit a function to return a function as its result cannot be

implemented with a stack-based storage allocation scheme for activation records

Which of the following statements about synchronous and asynchronous I/O is NOT true?

Which of the following is NOT true for deadlock prevention and deadlock avoidance schemes?

for (i = 0; i < n; i++) for ();

The total number of child processes created is

The P and V operations on counting semaphores, where s is a counting semaphore, are defined as

follows:

P(s) : s = s - 1;

ifs < 0 then wait;

V(s) : s = s + 1;

ifs <= 0 then wakeup a process waiting on s;

Assume that P_{b} and V_{b} the wait and signal operations on binary semaphores are provided. Two binary

semaphores x_{b} and y_{b} are used to implement the semaphore operations P(s) and V(s) as follows:

P(s) : Pb(Xb);

s = s - 1;

if (s < 0) {

Vb(Xb) ;

Pb(Yb) ;

}

else Vb(Xb);V(s) : Pb(Xb) ;

s = s + 1;

if (s <= 0) Vb(Yb) ;

Vb(Xb) ;

The initial values of x_{b} and y_{b} are respectively

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] = Y[i-1] + Z [i-2];

Y[i] = 2*X [i];

Z[i] = 3*X[i];

}

Return X[n];

}

f_{1} (8) and f_{2} (8) return the values

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows:

Bits 30-31 are used to index into the first level page table

Bits 21-29 are used to index into the second level page table

Bits 12-20 are used to index into the third level page table, and

Bits 0-11 are used as offset within the page

The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively

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?

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] = Y[i-1] + Z [i-2];

Y[i] = 2*X [i];

Z[i] = 3*X[i];

}

Return X[n];

}

The running time of f1 (n) and f2 (n) are

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a_{1}, a_{2}, a_{3}, …,

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 2-dimensional Boolean array, X, with n rows and W+1 columns.

X [i, j], 1$\le$i $\le$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a_{1}, a_{2}, …, a}

whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s.

The value of x_{5} is

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 < j);
- } while ((Y[k] ! = x) && (i < j));
- if (Y[k] == x) print f(“x is in the array”);
- else print f(“x is not in the array”);
- }

On which of the following contents of Y and x does the program fail?

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 < j);
- } while ((Y[k] ! = x) && (i < j));
- if (Y[k] == x) print f(“x is in the array”);
- else print f(“x is not in the array”);
- }

The correction needed in the program to make it work properly is

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a_{1}, a_{2}, a_{3}, …,

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 2-dimensional Boolean array, X, with n rows and W+1 columns.

X [i, j], 1$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a_{1}, a_{2}, …, a}

whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

I. Function locals and parameters

II. Register saves and restores

III. Instruction fetches

I. Bypassing can handle all RAW hazards

II. Register renaming can eliminate all register carried WAR hazards

III. Control hazard penalties can be eliminated by dynamic branch prediction

I. It must be a trap instruction

II. It must be a privileged instruction

III. An exception cannot be allowed to occur during execution of an RFE instruction

I. L1 must be a write-through cache

II. L2 must be a write-through cache

III. The associativity of L2 must be greater than that of L1

IV. The L2 cache must be at least as large as the L1 cache

I. It is useful in creating self-relocating code

II. If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation

III. The amount of increment depends on the size of the data item accessed

Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The

cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run on this

machine begins as follows:

double ARR[1024] [1024];

int i, j;

/* Initialize array ARR to 0.0 */

for (i = 0; i < 1024; i++)

for (j = 0; j < 1024; j++)

ARR[i] [j] = 0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page

0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

The total size of the tags in the cache directory is

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

Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The

cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run on this

machine begins as follows:

double ARR[1024] [1024];

int i, j;

/* Initialize array ARR to 0.0 */

for (i = 0; i < 1024; i++)

for (j = 0; j < 1024; j++)

ARR[i] [j] = 0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page

0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

The cache hit ratio for this initialization loop is

Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The

cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run on this

machine begins as follows:

double ARR[1024] [1024];

int i, j;

/* Initialize array ARR to 0.0 */

for (i = 0; i < 1024; i++)

for (j = 0; j < 1024; j++)

ARR[i] [j] = 0.0;

The size of double is 8Bytes. Array ARR is located in memory starting at the beginning of virtual page

0xFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR

Which of the following array elements has the same cache index as ARR [0] [0]?

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:

11 : ADD R2 ^{$\leftarrow$} R7 + R8

12 : SUB R4 ^{$\leftarrow$} R5 – R6

13 : ADD R1 ^{$\leftarrow$} R2 + R3

14 : STORE Memory [R4] ^{$\leftarrow$} R1

BRANCH to Label if R1 == 0

Which of the instructions 11, 12, 13 or 14 can legitimately occupy the delay slot without any other program modification?

a = (x > y) ? ((x > z) ? x : z) : ((y > z) ? y : z)

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"); ptintf("\n");
reverse(); printf("\n");
}
```

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 the function completes execution?

```
struct node {
int value;
struct node * next;
};
Void rearrange struct node * list {
struct node * p, * q;
int temp;
if (!list || !!list - > next) return;
p = list; | q = list - > next;
while q {
temp = p - > value;
p - > value = q - > value;
q - > value = temp;
p = q - > next;
q = p ? p - > next : 0;
}
}
```

What is printed by the following C program?

```
int f(int x, int py, int **ppz) void main() {
{
Int y, z;
int c, * b, * * a; * * ppz + = 1;
z = * ppz c = 4;
b = &c;
a = &b;
*py + = 2;
y = *py;
printf(“ % d”, f(c, b, a));
x + = 3;
}
return x + y + z;
}
```

A clustering index is defined on the fields which are of the type

Consider the following E-R diagram

The minimum number of tables needed to represent M, N, P, R1, R2 is

Let R and S be two relations with the following schema

R (__P__, __Q__, R1, R2, R3)

S(__P__, __Q__, S1, S2)

Where {P, Q} is the key for both schemas. Which of the following queries are equivalent?

I. $\Pi_P \left(R \bowtie S\right)$

II. $\Pi_P \left(R\right) \bowtie \Pi_P\left(S\right)$

III. $\Pi_P \left(\Pi_{P, Q} \left(R\right) \cap \Pi_{P,Q} \left(S\right) \right)$

IV. $\Pi_P \left(\Pi_{P, Q} \left(R\right) - \left(\Pi_{P,Q} \left(R\right) - \Pi_{P,Q} \left(S\right)\right)\right)$

Consider the following relational schemes for a library database:

Book Title, Author, Catalog_ no, Publisher, Year, Pr ice

Collection Title, Author, Catalog_ no

within the functional dependencies:

I. Title Author ^{$\rightarrow$} Catalog_no

II. Catalog_no ^{$\rightarrow$} Title Author Publisher Year

III. Publisher Title Year ^{$\rightarrow$} Pr ice

Assume {Author, Title} is the key for both schemes. Which of the following statements is true?

Consider the following E-R diagram

Which of the following is a correct attribute set for one of the tables for the correct answer to the above question?

Which of the following statements is false?

Which of the following is true for the language $\left\{ a^p \text{ | p is a prime} \right\} $?

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

If L and $\bar L$ are recursively enumerable then L is

Which of the following are regular sets?

I. $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$

II. $\left\{a^nb^m \mid n =2m \right\}$

III. $\left\{a^nb^m \mid n \neq m \right\}$

IV. $ \left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\} $

Which of the following statements are true?

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa

II. All $\epsilon$ productions can be removed from any context-free grammar by suitable transformations

III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular

IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

Match the following NFAs with the regular expressions they correspond to

- $\epsilon + 0\left(01^
*1+00\right)^*01^*$ - $\epsilon + 0\left(10^
*1+00\right)^*0$ - $\epsilon + 0\left(10^
*1+10\right)^*1$ - $\epsilon + 0\left(10^
*1+10\right)^*10^*$

Match the following:

E. | Checking that identifiers are declared before their use | P. | $L : = : \left\{a^nb^mc^nd^m \mid n: \geq1, m \geq 1\right\}$ | |

F. | Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function | Q. | $X: \rightarrow XbX \mid XcX \mid dXf \mid g$ | |

G. | Arithmetic expressions with matched pairs of parentheses | R. | $L: = \left\{wcw\mid w : \in \left(a\mid b\right)^* \right\}$ | |

H. | Palindromes | S. | $X : \rightarrow : bXb \mid :cXc : \mid \epsilon $ |

Given below are two finite state automata (→ indicates the start state and F indicates a final state)

Y:

| | a | b |

|-----------------|---|---|

| $\rightarrow$ 1 | 1 | 2 |

| 2(F) | 2 | 1 |

Z:

| | a | b |

|-----------------|---|---|

| $\rightarrow$ 1 | 2 | 2 |

| 2(F) | 1 | 1 |

Which of the following represents the product automaton Z × Y?

The data blocks of a very large file in the Unix file system are allocated using