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

Number of Questions: 60 | |

Created by: Aliensbrain Bot | |

Tags: Computer Science GATE CS Previous Year Paper |

Attempted
0/60
Correct 0
Score 0

‹
›

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

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

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

Consider the HTML table definition given below:

```
ab
cd
ef
gh
ik
```

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

For the composition table of a cyclic group shown below

* | a | b | c | d |
---|---|---|---|---|

a | a | b | c | d |

b | b | a | d | c |

c | c | b | d | a |

d | d | c | a | b |

Which one of the following choices is correct?

Evaluate: $\int^{\pi/4}_0 (1-\tan x)/(1+\tan x)dx $

Consider the following well-formed formulae:

I. $\neg \forall x(P(x))$ II. $\neg \exists x(P(x))$ III. $\neg \exists x(\neg P(x))$ IV. $\exists x(\neg P(x))$

Which of the above are equivalent?

(1217)_{8} is equivalent to

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?

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

Consider a disk system with 100 cylinders. The requests to access the cylinders occur in the following sequence: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20

Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to the adjacent one and shortest seek time first policy is used?

In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:

Now consider the following statements:
I. If a process makes a transition D, it would result in another process making transition A immediately.
II. A process P_{2} in blocked state can make transition E while another process P_{1} is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses non-preemptive scheduling.
Which of the above statements are TRUE?

The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:

```
void enter_CS(X)
{
while(test-and-set(X));
}
void leave_CS(X)
{
X = 0;
}
```

In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements: I. The above solution to CS problem is deadlock-free. II. The solution is starvation free. III. The processes enter CS in FIFO order. IV More than one process can enter CS at the same time. Which of the above statements is/are TRUE?

The running time of an algorithm is represented by the following recurrence relation:

$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$

Which one of the following represents the time complexity of the algorithm?

Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE?

I. The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph. II. The cyclomatic complexity of a module is the number of decisions in the module plus one, where a decision is effectively any conditional statement in the module. III. The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.

Which of the following statements are TRUE?

I. The context diagram should depict the system as a single bubble. II. External entities should be identified clearly at all levels of DFDs. III. Control information should not be represented in a DFD. IV. A data store can be connected either to another data store or to an external entity.

The binary operation □ is defined as follows

P | Q | P □ Q |
---|---|---|

T | T | T |

T | F | T |

F | T | F |

F | F | T |

Which one of the following is equivalent to $P \vee Q$?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i, j] = l(i,j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(I, j)?

^{e} mod n

M = (M')^{d} mod n
II. Ed = 1 mod n
III. ed = 1 mod $\phi$(n)
IV. M' = M^{e} mod $\phi$(n)
M = (M')^{d} mod $\phi$(n)
Which of the above equations correctly represent RSA
cryptosystem?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m, n), where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of X[m] and Y[n] is given below: l (i, j) = 0, if either i=0 or j=0 = expr1, if i,j>0 and X [i-1] = Y [j 1] = expr2, if i,j>0 and X [i-1] = Y [j 1]

Which one of the following options is correct?

Frames of 1000 bits are sent over a 10^{6} bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames.

Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?

Frames of 1000 bits are sent over a 10^{6} bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

Suppose that the sliding window protocol is used with the sender window size of 2^{l}, where l is the number of bits identified in the earlier part and acknowledgements are always piggy backed. After sending 2^{l} frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)

^{3}).
II. A programming language which allows recursion can be
implemented with static storage allocation.
III. No L-attributed definition can be evaluated in the framework of bottom-up parsing.
IV. Code improving transformations can be performed at both source language and intermediate code level.

How many 32 K x 1 RAM chips are needed to provide a memory capacity of 256 Kbytes?

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

A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c,h,s) , where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0^{th} sector is addressed as (0,0,0), the 1^{st} sector as (0,0,1), and so on

The address <400, 16, 29> corre4sponds tp sector number:

Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:

S1 | S2 | S3 | S4 | |
---|---|---|---|---|

11 | 2 | 1 | 1 | 1 |

12 | 1 | 3 | 2 | 2 |

13 | 2 | 1 | 1 | 3 |

14 | 1 | 2 | 2 | 2 |

What is the number of cycles needed to execute the following loop? For (I = 1 to 2) {I1; I2; I3; I4;}

A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c, h, s), where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0^{th} sector is addressed as (0, 0, 0), the 1^{st} sector as (0, 0, 1), and so on

The address of the 1039^{th} sector is

Consider the program below:

```
#include
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

Consider a binary max-heap implemented using an array.

Which one of the following array represents a binary max-heap?

Consider a binary max-heap implemented using an array.

What is the content of the array after two delete operations on the correct answer to the previous question?

Consider two transactions T_{1} and T_{2} and four schedules S_{1}, S_{2}, S_{3 }and S_{4} of T_{1} and T_{2} as given below:
T_{1} : R_{1} [x] W_{1} [x] W_{1} [y]
T_{2 }: R_{2} [x] R_{2} [y] W_{2} [y]
S_{1} : R_{1} [x] R_{2} [x] R_{2} [y] W_{1} [x] W_{1} [y] W_{2} [y]
S_{2} : R_{1} [x] R_{2} [x] R_{2} [y] W_{1} [x] W_{2} [y] W_{1} [y]
S_{3} : R_{1} [x] W_{1} [x] R_{2} [x] W_{1} [y] R_{2} [y] W_{2} [y]
S_{4} : R_{2} [x] R_{2} [y] R_{1} [x] W_{1} [x] W_{1} [y] W_{2} [y]

Which of the above schedules is/are conflict-serializable?

Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database:

I. $\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$ II. $\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}$ III. $\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}$ IV.

```
Select R.a, R.b
From R,S
Where R.c=S.c
```

Which of the above queries are equivalent?

Consider the following relational schema:

Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Assume that in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependency is implied other than those implied by primary and candidate keys.

Which of the following statements is TRUE about the above schema?

Consider the following relational schema: Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Consider the following relational query on the above database: SELECT S.sname FROM Suppliers S WHERE S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT (SELECT P.pid FROM Parts P WHERE P.color<> 'blue'))

Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?

*0(0 + 1)*0(0 + 1)*?

Which one of the following is FALSE?

The above DFA accepts the set of all strings over {0, 1} that

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

_{1 $\cap$} L_{2}, where L_{1} and L_{2} are languages as defined below:
L_{1} = $(a^m b^m\ ca^n b^m | m,n \ge 0)$
L_{2} = $(a^i b^j\ c^k | i,j \ge 0)$
Then L is

Given the following state table of an FSM with two states A and B, one input and one output:

Present State A | Present State B | Input | Next State A | Next State B | Output |
---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 1 |

0 | 1 | 0 | 1 | 0 | 0 |

1 | 0 | 0 | 0 | 1 | 0 |

1 | 1 | 0 | 1 | 0 | 0 |

0 | 0 | 1 | 0 | 1 | 0 |

0 | 1 | 1 | 0 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 1 |

1 | 1 | 1 | 0 | 0 | 1 |

If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?

Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.

Process P1: | Process P2: | Process P3: |
---|---|---|

t=0: requests 2 units of R2 | t=0: requests 2 units of R3 | t=0: requests 1 unit of R4 |

t=1: requests 1 unit of R3 | t=2: requests 1 unit of R4 | t=2: requests 2 units of R1 |

t=3: requests 2 units of R1 | t=4: requests 1 unit of R1 | t=5: releases 2 units of R1 |

t=5: releases 1 unit of R2 and 1 unit of R1. | t=6: releases 1 unit of R3 | t=7: requests 1 unit of R2 |

t=7: releases 1 unit of R3 | t=8: Finishes | t=8: requests 1 unit of R3 |

t=8: requests 2 units of R4 | t=9: Finishes | |

t=10: Finishes |

Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?

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