## 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...
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(}... <p>A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes ... 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 needs to send a message consisting of 9 packets to Station B using a s... Station A uses 32 byte packets to transmit messages to Station B using a sliding... 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 ...
Suppose that we have numbers between 1 and 100 in a binary search tree and want ...
Which of the following sequences of array elements forms a heap?
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 ...
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...
Let T be a depth-first search tree in an undirected graph G. Vertices u and v ar...

## Database Management System

Consider the relation enrolled (student, course) in which (student, course ) is ...
The following functional dependencies are given : <br>\eqalign{ & AB \to CD,... 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)\... Let$$X,. Y, Z$$be sets of sizes$$x, y$$and$$z$$respectively. Let$$W =...
The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multi...
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 ...
If all the edge weights of an undirected graph are positive, then any subject of...
Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,... Consider the polynomial$$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3...