GATE CSE 2005

## GATE CSE

The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

View Question
Consider the following C - function:
double foo(int n){
int i;
double sum;
if(n == 0) return 1.0;
sum = 0.0;
for (i

View Question
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is gi

View Question
Consider the following C - function:
double foo(int n){
int i;
double sum;
if(n == 0) return 1.0;
sum = 0.0;
for (i

View Question
Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements

View Question
Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be impl

View Question
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?

View Question
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the

View Question
The grammar $$A \to AA\,|\,\left( A \right)\,|\,\varepsilon $$ is not suitable for predictive-parsing because the gramm

View Question
Consider the grammar
$$S \to \left( S \right)\,|\,a$$
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for

View Question
Consider the grammar
$$E \to E + n\,|\,E \times n\,|\,n$$
For a sentence n + n × n, the handles in the right-sentential

View Question
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each gramma

View Question
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each gramma

View Question
Consider line number 3 of the following C - program.
int main ( ) { /* Line 1 */
int I, N;

View Question
In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since

View Question
Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum fra

View Question
The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:

View Question
In a packet switching network, packets are routed from source to destination along a single path having two intermediate

View Question
The address resolution protocol (ARP) is used for

View Question
An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be

View Question
Packets of the same session may be routed through different paths in

View Question
Suppose that two parties A and B wish to setup a common secret key (D - H key) between themselves using the Diffie-Hellm

View Question
The data given below. Solve the problems and choose the correct answer.
Mantissa is a pure fraction in sign - magnitu

View Question
The data given below. Solve the problems and choose the correct answer.
The normalized representation for the above f

View Question
Increasing the $$RAM$$ of a computer typically improves performance because

View Question
Consider a direct mapped cache of size $$32$$ $$KB$$ with block size $$32$$ bytes. The $$CPU$$ generates $$32$$ bit addr

View Question
A $$5$$ stage pipelined $$CPU$$ has the following sequence of stages $$IF$$-Instruction fetch from instruction memory, $

View Question
Consider a three word machine instruction $$ADD$$ $$A$$ $$\left[ {{R_0}} \right],\,@\,B$$
The first operand (destination

View Question
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${\rm I}/O$$ instructions in them. For $$C

View Question
A device with data transfer rate $$10$$ $$KB/sec$$ is connected to a $$CPU.$$ Data is transferred byte-wise. Let the int

View Question
Consider the disk drive with the following specifications $$16$$ surfaces, $$512$$ tracks/surface, $$512$$ sectors/track

View Question
Consider the following data path of a $$CPU$$
The, $$ALU$$, the bus and all the registers in the data path are of ide

View Question
Consider the following data path of a $$CPU$$
The, $$ALU$$, the bus and all the registers in the data path are of ide

View Question
A program P reads in 500 integers in the range [0, 100] representing the cores of 500 students. It then print the freque

View Question
A function f defined on stacks of integers satisfies the following properties.
f(∅) = 0 and f (push (S, i)) = max (f(S)

View Question
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list.

View Question
The numbers 1, 2, ........, n are inserted in a binary search tree in some order. In the resulting tree, the right subtr

View Question
Postorder traversal of a given binary search tree T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15,

View Question
How many distinct binary search trees can be created out of 4 distinct keys?

View Question
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2.

View Question
In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n interna

View Question
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values

View Question
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is gi

View Question
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash

View Question
Let $${E_1}$$ and $${E_2}$$ be two entities in an E-R diagram with simple single-valued attributes, $${E_1}$$ and $${E_2

View Question
The following table has two attributes $$A$$ and $$C$$ where $$A$$ is the primary key and $$C$$ is the foreign key refer

View Question
Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below
If we wish

View Question
Which one of the following statements about normal forms is FALSE?

View Question
A table has fields, $$F1, F2, F3, F4, F5,$$ with the following functional dependencies:
$$F1 \to F3.\,F2 \to F4.\,\,\,\

View Question
In a schema with attributes $$A, B, C, D,$$ and $$E,$$ following set of functional dependencies are given
$$\eqalign{

View Question
Consider a relation scheme $$R = \left( {A,\,B,\,C,\,D,\,E,\,H} \right)$$ on which the following functional dependencies

View Question
The relation book (title, price) contains the titles and prices of different books. Assuming that no two books have the

View Question
A company maintains records of sales made by its salespersons and pays them commission based on each individual’s total

View Question
In an inventory management system implemented at a trading corporation, there are several tables designed to hold all th

View Question
Let r be a relation instance with schema R = (A, B, C, D).
We define $${r_1} = {\pi _{A,B,C}}\left( r \right)$$ and $${r

View Question
A table ‘student’ with schema (roll, name, hostel, marks), and another table ‘hobby’ with schema (roll, hobbyname) conta

View Question
Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database b

View Question
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted i

View Question
Let $$P, Q$$ and $$R$$ be three atomic prepositional assertions. Let $$X$$ denotes $$\left( {P \vee Q} \right) \to R$$ a

View Question
Let $$P(x)$$ and $$Q(x)$$ be arbitrary predicates. Which of the following statement is always TRUE?

View Question
What is the first order predicate calculus statement equivalent to the following?
Every teacher is liked by some studen

View Question
A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded

View Question
Let $$f(x)$$ be the continuous probability density function of a random variable X. The probability that $$a\, < \,X\

View Question
Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows: (i) sel

View Question
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the tails ar

View Question
A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on o

View Question
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets $${S_1}$$ a

View Question
Let R and S be any two equivalence relations on a non-emply set A. Which one of the following statements is TRUE?

View Question
Let f: $$\,B \to \,C$$ and g: $$\,A \to \,B$$ be two functions and let h = fog. Given that h is an onto function which o

View Question
The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$1

View Question
Let $$f$$ be a function from a set $$A$$ to a set $$B$$, $$g$$ a function from $$B$$ to $$C$$, and $$h$$ a function from

View Question
Let $$A$$, $$B$$ and $$C$$ be non-empty sets and let $$X = (A - B) - C$$ and $$Y = (A - C) - (B - C)$$
Which one of the

View Question
The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$
The poset is:

View Question
The determination of the matrix given below is $$$\left[ {\matrix{
0 & 1 & 0 & 2 \cr
{ - 1} & 1

View Question
Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embe

View Question
Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $$G$$ is 8. Then,

View Question
What is the value of $$\int\limits_0^{2\pi } {{{\left( {x - \pi } \right)}^3}\left( {\sin x} \right)dx} $$

View Question
What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two p

View Question
Let $$G\left( x \right) = 1/\left( {1 - x} \right)2 = \sum\limits_{i = 0}^\infty {g\left( i \right)\,{x^1}} \,\,\,,$$

View Question
Let $$n = {p^2}q,$$ where $$p$$ and $$q$$ are distinct prime numbers. How many numbers $$m$$ satisfy $$1 \le m \le n$$ a

View Question
What are the eigen values of the following $$2x2$$ matrix?
$$$\left[ {\matrix{
2 & { - 1} \cr
{ - 4} & 5

View Question
Consider the set $$H$$ of all $$3$$ $$X$$ $$3$$ matrices of the type
$$$\left[ {\matrix{
a & f & e \cr
0

View Question
Consider the following system of equations in three real variables $$x1, x2$$ and $$x3$$ :
$$2x1 - x2 + 3x3 = 1$$
$$3x1

View Question
Which one of the following graphs is NOT planar?

View Question
Consider the following code fragment:
if (fork() == 0)
{
a = a + 5;
printf("%d, %d \n", a, &a);
}
else
{
a

View Question
What is the swap space in the disk used for?

View Question
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${\rm I}/O$$ instructions in the for $$CPU

View Question
Consider a disk drive with the following specifications:
$$16$$ surfaces, $$512$$ tracks/surface, $$512$$ sectors/track,

View Question
Suppose n processes, P1,......., Pn share m identical resource units, which can be reserved and released one at a time.

View Question
A common property of logic programming languages and functional languages is:

View Question
An Abstract Data Type (ADT) is

View Question
Which one of the following are essential features of an object-oriented programming language?
i) Abstraction and encapsu

View Question
Consider the following C program:
void foo (int n, int sum) {
int k = 0, j = 0;
if(n==0) return;
k=n%10; j = n /10

View Question
Consider the following C program:
double foo(double); /* Line 1 */
int main () {
double da, db;
//input da
db = fo

View Question
What does the following C statement declare?
int (*f)(int *);

View Question
Consider the machine $$M:$$ The language recognized by $$M$$ is:

View Question
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-determ

View Question
Consider the language :
$${L_1} = \left\{ {{a^n}{b^n}{c^m}\left| {n,m > 0} \right.} \right\}$$ and $${L_2} = \left\{

View Question
Consider the language :
$${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$

View Question
Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which

View Question
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}

View Question