## 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 $${... Consider the disk drive with the following specifications$$16$$surfaces,$$512...
A device with data transfer rate $$10$$ $$KB/sec$$ is connected to a $$CPU.$$ Da...
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 complete k-ary tree, every internal node has exactly k children. The number...
In a binary tree, for every node the difference between the number of nodes in t...
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...
A table has fields, $$F1, F2, F3, F4, F5,$$ with the following functional depend...
Which one of the following statements about normal forms is <b>FALSE?</b>
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...
<p>A company maintains records of sales made by its salespersons and pays them c...
The relation book (title, price) contains the titles and prices of different boo...
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 R and S be any two equivalence relations on a non-emply set A. Which one of ... Let A be a set with n elements. Let C be a collection of distinct subsets of A s... Let f:$$\,B \to \,C$$and g:$$\,A \to \,B$$be two functions and let h = fog. ... Let$$A$$,$$B$$and$$C$$be non-empty sets and let$$X = (A - B) - C$$and$$Y...
Let $$f$$ be a function from a set $$A$$ to a set $$B$$, $$g$$ a function from $... The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is... 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...
Consider the set $$H$$ of all $$3$$ $$X$$ $$3$$ matrices of the type $$\left[ {... Consider the following system of equations in three real variables$$x1, x2$$an... What are the eigen values of the following$$2x2$$matrix?$$\$\left[ {\matrix{ ...
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...