## GATE CSE 2005

Exam Held on Thu Jan 01 1970 00:00:00 GMT+0000 (Coordinated Universal Time)
Click View All Questions to see questions one by one or you can choose a single question from below.

## Algorithms

The time complexity of computing the transitive closure of a binary relation on ...
Consider the following C - function: <pre><code class="c">double foo(int n){ in...
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The...
Consider the following C - function: <pre><code class="c">double foo(int n){ in...
Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \o... Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-so... Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 <br/> Which one of the following is... Consider three decision problems P<sub>1</sub>, P<sub>2</sub> and P<sub>3</sub>.... ## Compiler Design The grammar$$A \to AA\,|\,\left( A \right)\,|\,\varepsilon $$<br/>is not suit... <p>Consider the grammar</p>$$S \to \left( S \right)\,|\,a$$<p>Let the number o... <p>Consider the grammar</p>$$E \to E + n\,|\,E \times n\,|\,n$$<p>For a senten... <p>Consider the following expression grammar. The seman­tic rules for expression... <p>Consider the following expression grammar. The seman­tic rules for expression... Consider line number 3 of the following C - program. <pre><code class="c">int ma... ## Computer Networks In a network of LANs connected by bridges, packets are sent from one LAN to anot... Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit ja... The maximum window size for data transmission using the selective reject protoco... In a packet switching network, packets are routed from source to destination alo... The address resolution protocol (ARP) is used for An organization has a class B network and wishes to form subnets for 64 departme... Packets of the same session may be routed through different paths in Suppose that two parties A and B wish to setup a common secret key (D - H key) b... ## Computer Organization The data given below. Solve the problems and choose the correct answer. <img cl... The data given below. Solve the problems and choose the correct answer. <img cl... Increasing the$$RAM$$of a computer typically improves performance because Consider a direct mapped cache of size$$32KB$$with block size$$32$$byte... A$$5$$stage pipelined$$CPU$$has the following sequence of stages$$IF$$-Inst... Consider a three word machine instruction$$ADDA\left[ {{R_0}} \right]...
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${... A device with data transfer rate$$10KB/sec$$is connected to a$$CPU.$$Da... Consider the disk drive with the following specifications$$16$$surfaces,$$512...
Consider the following data path of a $$CPU$$ <img class="question-image" src="...
Consider the following data path of a $$CPU$$ <img class="question-image" src="...

## Data Structures

A program P reads in 500 integers in the range [0, 100] representing the cores o...
A function f defined on stacks of integers satisfies the following properties. ...
The following C function takes a single-linked list of integers as a parameter a...
The numbers 1, 2, ........, n are inserted in a binary search tree in some order...
Postorder traversal of a given binary search tree T produces the following seque...
How many distinct binary search trees can be created out of 4 distinct keys?
In a binary tree, for every node the difference between the number of nodes in t...
In a complete k-ary tree, every internal node has exactly k children. The number...
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree ...
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The...
A hash table contains 10 buckets and uses linear probing to resolve collisions. ...

## Database Management System

Let $${E_1}$$ and $${E_2}$$ be two entities in an <b>E-R</b> diagram with simple...
The following table has two attributes $$A$$ and $$C$$ where $$A$$ is the primar...
Consider the entities 'hotel room', and 'person' with a many to many relationshi...
Which one of the following statements about normal forms is <b>FALSE?</b>
A table has fields, $$F1, F2, F3, F4, F5,$$ with the following functional depend...
In a schema with attributes $$A, B, C, D,$$ and $$E,$$ following set of function...
Consider a relation scheme $$R = \left( {A,\,B,\,C,\,D,\,E,\,H} \right)$$ on whi...
The relation book (title, price) contains the titles and prices of different boo...
<p>A company maintains records of sales made by its salespersons and pays them c...
In an inventory management system implemented at a trading corporation, there ar...
<p>Let r be a relation instance with schema R = (A, B, C, D).</p> We define $${r... A table <b>‘student’</b> with schema (roll, name, hostel, marks), and another ta... Amongst the ACID properties of a transaction, the 'Durability' property requires... A B-Tree used as an index for a large database table has four levels including t... ## Discrete Mathematics Let$$P, Q$$and$$R$$be three atomic prepositional assertions. Let$$X$$denot... Let$$P(x)$$and$$Q(x)$$be arbitrary predicates. Which of the following statem... What is the first order predicate calculus statement equivalent to the following... A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is... Let$$f(x)$$be the continuous probability density function of a random variable... Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball... An unbiased coin is tossed repeatedly until the outcome of two successive tosses... A random bit string of length n is constructed by tossing a fair coin n times an... Let A be a set with n elements. Let C be a collection of distinct subsets of A s... Let R and S be any two equivalence relations on a non-emply set A. Which one of ... Let f:$$\,B \to \,C$$and g:$$\,A \to \,B$$be two functions and let h = fog. ... The set$$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$is... Let$$f$$be a function from a set$$A$$to a set$$B$$,$$g$$a function from ... Let$$A$$,$$B$$and$$C$$be non-empty sets and let$$X = (A - B) - C$$and$$Y...
The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \r... The determination of the matrix given below is$$$\left[ {\matrix{ 0 & 1 & 0 ... Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then... Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the mi... What is the value of $$\int\limits_0^{2\pi } {{{\left( {x - \pi } \right)}^3}\le... What is the minimum number of ordered pairs of non-negative numbers that should ... Let$$G\left( x \right) = 1/\left( {1 - x} \right)2 = \sum\limits_{i = 0}^\infty... Let $$n = {p^2}q,$$ where $$p$$ and $$q$$ are distinct prime numbers. How many n... What are the eigen values of the following $$2x2$$ matrix? $$\left[ {\matrix{ ... Consider the set$$H$$of all$$3X3$$matrices of the type$$$\left[ {...
Consider the following system of equations in three real variables $$x1, x2$$ an...
Which one of the following graphs is NOT planar? <img class="question-image" src...

## Operating Systems

Consider the following code fragment: <pre><code class='c'>if (fork() == 0) {...
What is the swap space in the disk used for?
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${... Consider a disk drive with the following specifications: <br>$$16$$surfaces,$$...
Suppose n processes, P<sub>1</sub>,......., P<sub>n</sub> share m identical reso...

## Programming Languages

A common property of logic programming languages and functional languages is:
An Abstract Data Type (ADT) is
Which one of the following are essential features of an object-oriented programm...
Consider the following C program: <pre><code class="c">void foo (int n, int sum)...
Consider the following C program: <pre><code class="c">double foo(double); /* Li...
What does the following C statement declare? <pre><code>int (*f)(int *);</code><...

## Theory of Computation

Consider the machine $$M:$$ The language recognized by $$M$$ is: <img class="que...
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-dete...
Consider the language : <br>$${L_1} = \left\{ {{a^n}{b^n}{c^m}\left| {n,m > 0} ... Consider the language : <br>$${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\...
Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumer...
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known...