GATE CSE 2005
View Questions

## 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 seman­tic rules for expression calculation are stated next to each gramma
View Question
Consider the following expression grammar. The seman­tic 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$$10KB/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\, &lt; \,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 &amp; 1 &amp; 0 &amp; 2 \cr { - 1} &amp; 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 &amp; { - 1} \cr { - 4} &amp; 5 View Question Consider the set$$H$$of all$$3X3$$matrices of the type$$\$\left[ {\matrix{ a &amp; f &amp; 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, &amp;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 &gt; 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
EXAM MAP
Joint Entrance Examination