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