Computer Science and Information Technology - GATE 2010 Paper Solution

Question No. 1

Let G = (V, E) be a graph. Define $\xi\left(G\right)=\sum_di_d\times d,\;\mathrm{where}\;i_G$ is the number of vertices of degree d in G. If S and T are two different trees with ξ (S) = ξ (T), then

Question No. 2

Newton-Raphson method is used to compute a root of the equation x2 − 13 = 0 with 3.5 as the initial value. The approximation after one iteration is

Question No. 3

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

Question No. 4

Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If * denotes the multiplication operation, the structure {S, *} forms

Question No. 5

What is the value of limn1-1n2n?

Question No. 6

The minterm expansion of fP,Q,R=PQ+QR+PR is

Question No. 7

A main memory unit with a capacity of 4 megabytes is built using 1M×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

Question No. 8

P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)16. The 2’s complement representation of 8*P is

Question No. 9

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

Question No. 10

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

Question No. 11

What does the following program print?

#include <stdio.h>
void f (int *p, int *q) {
p = q;
*p = 2;
int i=0, j=1;
int main ( ){
f(&i, &j);
printf("%d %d\n", i, j ;
return 0;

Question No. 12

Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

Question No. 13

Which data structure in a compiler is used for managing information about variables and their attributes?

Question No. 14

Which languages necessarily need heap allocation in the runtime environment?

Question No. 15

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

Question No. 16

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

Question No. 17

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Question No. 18

Consider a B+-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?

Question No. 19

A relational schema for a train reservation database is given below

Passenger (pid, pname, age)
Reservation (pid, cass, tid)

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?

FROM Reservation
WHERE class = 'AC' AND
              FROM Passenger
              WHERE age 65 AND

Question No. 20

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?

I. 2-phase locking
II. Time-stamp ordering