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

Number of Questions: 65 | |

Created by: Aliensbrain Bot | |

Tags: Computer Science GATE CS Previous Year Paper |

Attempted
0/64
Correct 0
Score 0

‹
›

_{16}. The 2's complement representation of 8*P is

^{× }1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

^{k} records. Package A requires 0.0001n^{2} time units and package B requires 10nlog_{10}n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

Which languages necessarily need heap allocation in the runtime environment?

Which one of the following is not a client server application?

^{+} -tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

What does the following program print?

```
#include
void f (int *p, int * g)
{
p = q;
* p = 2;
}
int i = 0, j = 1;
int main ( )
{
f(&i, &j);
print f ("%d%d n", i, j) ;
return 0;
}
```

^{2} − 13 = 0 with 3.5 as the initial value. The approximation after one iteration is

I. 2-phase locking

II. Time-stamp ordering

What is the value of $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$ ?

A relational schema for a train reservation database is given below:

Passenger (pid, pname, age)

Table: passenger

pid | pname | Age |
---|---|---|

0 | Sachin | 65 |

1 | Rahul | 66 |

2 | Sourav | 67 |

3 | Anil | 69 |

Table: Reservation

pid | class | tid |
---|---|---|

0 | AC | 8200 |

1 | AC | 8201 |

2 | SC | 8201 |

5 | AC | 8203 |

1 | SC | 8204 |

3 | AC | 8202 |

What pids are returned by the following SQL query for the above instance of the tables?

```
SELECT pid
FROM Reservation
WHERE class 'AC' AND
EXISTS (SELECT *
FROM Passenger
WHERE age 65 > AND
Passenger. pid = Reservation. pid)
```

What is the probability that divisor of 1099 is a multiple of 1096?

Which of the following statements are true?

I. Shortest remaining time first scheduling may cause starvation

II. Preemptive scheduling may cause starvation

III. Round robin is better than FCFS in terms of response time

*p. *The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of *q. *What is the probability of a computer being declared faulty?

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared Boolean variables S1 and S2 are randomly assigned.

Method used by P1 | Method used by P2 |
---|---|

while (S1==S2); | while (S1!=S2); |

Critical Section | Critical Section |

S1=S2; | S2 = not(S1) |

Which one of the following statements describes the properties achieved?

I. 7, 6, 5, 4, 4, 3, 2, 1

II. 6, 6, 6, 6, 3, 3, 2, 2

III. 7, 6, 6, 4, 4, 3, 2, 2

IV. 8, 7, 7, 6, 4, 2, 1, 1

What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?

P. Requirements Capture | 1. Module Development and Integration |

Q. Design | 2. Domain Analysis |

R. Implementation | 3. Structural and Behavioral Modeling |

S. Maintenance | 4. Performance Tuning |

What is the possible number of reflexive relations on a set of 5 elements?

What is the value printed by the following C program?

```
#include
int f(int * a, int n) {
if (n <= 0) return 0;
else if ( * a % 2 = = 0) return *a + f(a + 1, n - 1);
else return *a - f(a + 1, n - 1);
}
int main() {
int a[] = {
12,
7,
13,
4,
11,
6
};
print f( % d, f(a, 6));
return 0;
}
```

_{1}Q_{0} is 00, what are the next four values of Q_{1}Q_{0}?

_{0}, a_{1},…, a_{n-1} of real numbers is defined as a + a_{1} / 2 + …. + a_{n-1 }/ 2^{n-1}. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a_{0}, a_{1}, …., a_{n-1}. Then X is equal to

The grammar S $\rightarrow$ aSa|bS|c is

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

```
typedef struct node {
int value;
struct node * next;
}Node;
Node * move_to_front(Node * head) {
Node * p, * q;
if ((head = = NULL: || (head - > next = = NULL)) return head; q = NULL; p = head;
while (p - > next != NULL) {
q = P;
p = p - > next;
}
return head;
}
```

Choose the correct alternative to replace the blank line.

A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL instruction, and 6 clock cycles for DIV instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?

Instruction Meaning of instruction

$t_0: MUL :R_2,R_0,R_1$ $R_2 \gets R_0*R_1$

$t_1: DIV: R_5,R_3,R_4$ $R_5 \gets R_3 / R_4$

$t_2: ADD: R_2,R_5,R_2$ $R_2 \gets R_5 + R_2$

$t_3: SUB :R_5,R_2,R_6$ $R_5 \gets R_2 - R_6$

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W =

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram

All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?

A system has $n$ resources $R_0, \dots,R_{n-1}$, and $k$ processes $P_0, \dots, P_{k-1}$. The implementation of the resource request logic of each process $P_i$ is as follows:

```
if (i%2==0) {
if (i
```

The program below uses six temporary variables a, b, c, d, e, f.

a = 1 |

b = 10 |

c = 20 |

d = a + b |

e = c + d |

f = c + e |

b = c + e |

e = b + f |

d = 5 + e |

return d + f |

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds, 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit, respectively.

When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below

0 | |
---|---|

1 | |

2 | 42 |

3 | 23 |

4 | 34 |

5 | 52 |

6 | 46 |

7 | 33 |

8 | |

9 |

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.

When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0 = 1, S1 = 0, S2 = 0.

Process P0 | Process P1 | Process P2 |

while (true) { | wait (S1); | wait (S2); |

wait (S0); | release (S0); | release (S0); |

print '0'; | ||

release (S1); | ||

release (S2); | ||

} |

How many times will process P0 print ‘0’?

** Directions:** Choose the most appropriate word from the options given below to the complete the following sentence.

His rather casual remarks on politics ___________ his lack of seriousness about the subject.

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram

Suppose the weights of all unused links in the previous question are changed to 2 and the distance vector algorithm is used again until all routing tables stabilize. How many links will now remain unused?

** Directions:** Choose the most appropriate word from the options given below to complete the following sentence.

If we manage to ____________ our natural resources, we would leave a better planet for our children.

**Unemployed : Worker**

Which of the following statements best sums up the meaning of the above passage?

If 137 + 276 = 435 how much is 731 + 672?

Which of the following options is closest in meaning to the word Circuitous.

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below

0 | |
---|---|

1 | |

2 | 42 |

3 | 23 |

4 | 34 |

5 | 52 |

6 | 46 |

7 | 33 |

8 | |

9 |

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

Consider the following schedule for transactions T1, T2 and T3:

$\underline {T1}$

$\underline{T2}$

$\underline{T1}$

Read(X)

Read(Y)

Read(Y)

Write(Y)

Write(X)

Write(X)

Read(X)

Write(X)

Which one of the schedules below is the correct serialization of the above?

^{i}1^{j} | i $\ne$ j}. L2 = {0^{i}1^{j} | i = j}. L3 = {0^{i}1^{j} | i = 2j +1}.

L4 = {0^{i}1^{j} | i $\ne$2j}. Which one of the following statements is true?

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W =

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

Hari (H), Gita (G), Irfan (I) and Saira (S) are siblings (i.e. brothers and sisters). All were born on 1^{st} january. The age difference between any two successive siblings (that is born one after another) is less than 3 years. Given the following facts:

i. Hari's age + Gita's age > Irfan's age + Saira's age

ii. The age difference between Gita and Saira is 1 year. However Gita is not the oldest and Saira is not the youngest.

iii. There are no twins.

In what order were they born (oldest first)?

The following program is to be tested for statement coverage:

begin

if (a = = b) {S1; exit;}

else if (c = = d) {S2;}

else {S3; exit;}

S4;

end

The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given.

T1 : a, b, c and d are all equal

T2 : a, b, c and d are all distinct

T3 : a=b and c !=d

T4 : a !=b and c=d

Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?

B $\rightarrow$A,

A $\rightarrow$C

The relation R contains 200tuples and the relation S contains 100tuples. What is the maximum number of tuples possible in the natural join $R \bowtie S$

The minterm expansion of f (P, Q, R) = PQ + Q^{$\bar R$} + P^{$\bar R$} is

The Boolean expression for the output f of the multiplexer shown below is