Computer Science and Information Technology - GATE 2010 Paper Solution


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

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

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

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

What is the value of limn1-1n2n?

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

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

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

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

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?

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;

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?

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

Which languages necessarily need heap allocation in the runtime environment?

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?

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

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?

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?

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

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

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