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 $$32$$ $$KB$$ with block size $$32$$ byte...
A $$5$$ stage pipelined $$CPU$$ has the following sequence of stages $$IF$$-Inst...
Consider a three word machine instruction $$ADD$$ $$A$$ $$\left[ {{R_0}} \right]...
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${...
A device with data transfer rate $$10$$ $$KB/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 $$3$$ $$X$$ $$3$$ 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...

EXAM MAP

Joint Entrance Examination

JEE Advanced JEE Main

Graduate Aptitude Test in Engineering

GATE CSE GATE EE GATE ECE GATE ME GATE CE GATE PI GATE IN