## GATE CSE 2006

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

Consider the following C-program fragment in which i, j and n are integer variab...
In a binary max heap containing n numbers, the smallest element can be found in ...
Which one of the following in place sorting algorithms needs the minimum number ...
An element in an array X is called a leader if it is greater than all elements t...
<p>A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes ...
Given two arrays of numbers a<sub>1</sub>,......,a<sub>n</sub> and b<sub>1</sub>...
<p>A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes ...
Consider the following recurrence:<br/> $$T\left( n \right){\rm{ }} = {\rm{ 2T(}... The median of n elements can be found in O(n) time. Which one of the following i... Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that ... To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it ... Consider the following graph: <img class="question-image" src="https://gateclass... Let S be an NP-complete problem and Q and R be two other problems not known to b... Let SHAM<sub>3</sub> be the problem of finding a Hamiltonian cycle in a graph G ... ## Compiler Design <p>Consider the following grammar.</p>$$\eqalign{ & S \to S*E \cr & S \to...
<p>Which one of the following grammars generates the following language?</p> $$L... In the correct grammar of the previous question, what is the length of the deriv... <p>Consider the following grammar:</p>$$\eqalign{ & S \to FR \cr & R \to ...
<p>Consider the following translation scheme.</p> \eqalign{ & S \to ER \cr ... Consider the following C code segment. <pre><code>for (i = 0; i < n; i++) { ... ## Computer Networks Consider the diagram shown below where a number of LANs are connected by (transp... Consider the diagram shown below where a number of LANs are connected by (transp... Station A uses 32 byte packets to transmit messages to Station B using a sliding... Station A needs to send a message consisting of 9 packets to Station B using a s... For which one of the following reasons does Internet Protocol (IP) use the time-... Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.5... ## Computer Organization Given two three bit number{a_2}{a_1}{a_0}$$and$${b_2}{b_1}{b_0}$$and$$c,...
Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set as...
A $$CPU$$ has a cache with block size $$64$$ bytes. The main memory has $$k$$ ba...
Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set as...
A CPU has five stages pipeline and runs at $$1$$ $$GHz$$ frequency. Instruction ...
A $$CPU$$ has $$24$$-bit instructions. A program starts at address $$300$$ (in d...
Consider the following program segment. Here R1, R2 and R3 are the general purpo...
Consider the following program segment. Here R1, R2 and R3 are the general purpo...
Consider the following program segment. Here R1, R2 and R3 are the general purpo...

## Data Structures

An implementation of a queue Q, using two stacks S1 and S2, is given below: <pre...
The following function computes the value of <sup>m</sup>C<sub>n</sub> correctly...
A scheme for storing binary trees in an array X is as follows. Indexing of X sta...
In a binary tree, the number of internal nodes of degree 1 is 5, and the number ...
Which of the following sequences of array elements forms a heap?
Suppose that we have numbers between 1 and 100 in a binary search tree and want ...
An array X of n distinct integers is interpreted as a complete binary tree. The ...
An array X of n distinct integers is interpreted as a complete binary tree. The ...
An array X of n distinct integers is interpreted as a complete binary tree. The ...
Let T be a depth first search tree in an undirected graph G. Vertices u and v ar...
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and...
Let T be a depth-first search tree in an undirected graph G. Vertices u and v ar...

The following functional dependencies are given : <br>\eqalign{ & AB \to CD,... Consider the relation enrolled (student, course) in which (student, course ) is ... Consider the relation <b>account (customer, balance)</b> where customer is a pri... <p>Consider the relation <b>"enrolled (student, course)"</b> in which (student, ... <p>Consider a database with three relation instances shown below. The primary ke... <p>Consider a database with three relation instances shown below. The primary ke... Consider the relations r<sub>1</sub>(P, Q, R) and r<sub>2</sub>(R, S, T) with pr... Which of the following relational query languages have the same expressive power... ## Digital Logic Consider a Boolean functionf(w, x, y, z).$$Suppose that exactly one of its i... Consider the circuit above. Which one of the following options correctly represe... You are given a free running clock with a duty cycle of$$50$$% and a digital wa... Consider the circuit in the diagram. The$$ \oplus $$operator represents$$EX$$... ## Discrete Mathematics Which one of the first order predicate calculus statements given below correctly... Consider the following propositional statements: <p><br>$${\rm P}1:\,\,\left( {...
In a certain town, the probability that it will rain in the afternoon is known t...
A logical binary relation $$\odot$$, is defined as follows: <img class="questi...
When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N ...
Consider the following first order logic formula in which $$R$$ is a binary rela...
Let $$P, Q$$, and $$R$$ be sets. Let $$\Delta$$ denote the symmetric difference...
Let E, F and G be finite sets. <br> Let $$X = \,\left( {E\, \cap \,F\,} \right)\... The set$$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$under multi... Let$$X,. Y, Z$$be sets of sizes$$x, y$$and$$z$$respectively. Let$$W =...
A relation $$R$$ is defined on ordered pairs of integers as follows: $$\left( {... For the set$$N$$of natural numbers and a binary operation$$f:N \times N \to N...
Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \su... Let S = {1, 2, 3,....., m} , m > 3. Let$${X_1},\,....,\,{X_n}$$be subsets of S... Consider the set S = {a, b, c, d}. Consider the following 4 partitions$$\,{\pi ...
Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,... If all the edge weights of an undirected graph are positive, then any subject of... Consider the polynomial$$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3...