# Computer Science and Information Technology - GATE 2009 Paper Solution

Which one of the following in NOT necessarily a property of a Group?

What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.

Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?

Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?

(1217)8 is equivalent to

What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?

How many 32K × 1 RAM chips are needed to provide a memory capacity of 256 K-bytes?

A CPU generally handles an interrupt by executing an interrupt service routine

In which one of the following page replacement policies, Belady’s anomaly may occur?

The essential content(s) in each entry of a page table is/are

What is the number of swaps required to sort n elements using selection sort, in the worst case?

S → aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of

Which of the following statement (s) is / are correct regarding Bellman-Ford shortest path algorithm?

P. Always finds a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.

Let ${\mathrm{\pi }}_{\mathrm{A}}$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

Which one of the following is FALSE?

Match all items in Group 1 with correct options from those given in Group 2.

 Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization

Consider the program below:

#include <stdio.h>
int fun(int n,int *f_p) {
int t, f;
if (n <= 1) {
*f_p =1;
return 1;
}
t = fun (n- 1, f_p);
f = t + *f_p;
*f_p = t;
return f;
}
int main() {
int x = 15;
printf ("%d\ n", fun(5,&x));
return 0;
}

The value printed is:

The coupling between different modules of a software is categorized as follows:

I. Content coupling
II. Common coupling
III. Control coupling
IV Stamp coupling
V. Data coupling

Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:

Consider the HTML table definition given below:

<table border=1>
<tr> <td rowspan=2> ab </td>
<td colspan=2> cd </td>
</tr>
<tr> <td> ef </td>
<td rowspan=2> gh </td>
</tr>
<tr> <td colspan=2> ik </td>
</tr>
</table>

The number of rows in each column and the number of columns in each row are: