GATE CSE 2006

## GATE CSE

Consider the following C-program fragment in which i, j and n are integer variables.
for (i = n, j = 0; i > 0; i /= 2

View Question
In a binary max heap containing n numbers, the smallest element can be found
in time

View Question
Which one of the following in place sorting algorithms needs the minimum
number of swaps?

View Question
An element in an array X is called a leader if it is greater than all elements to the
right of it in X. The best algorit

View Question
Given two arrays of numbers a1,......,an and b1,......, bn where each number is 0 or 1,
the fastest algorithm to find th

View Question
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3
children. A 3-ary heap can be repres

View Question
Consider the following recurrence:
$$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) +

View Question
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3
children. A 3-ary heap can be repres

View Question
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick

View Question
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i

View Question
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure

View Question
Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a min

View Question
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible

View Question
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM3 be th

View Question
Consider the following grammar.
$$\eqalign{
& S \to S*E \cr
& S \to E \cr
& E \to F + E \cr
&a

View Question
Which one of the following grammars generates the following language?
$$L = \left( {{a^i}{b^j}|i \ne j} \right)$$

View Question
In the correct grammar of the previous question, what is the length of the derivation (number of steps starring from S)

View Question
Consider the following grammar:
$$\eqalign{
& S \to FR \cr
& R \to *S\,|\,\varepsilon \cr
& F \to

View Question
Consider the following translation scheme.
$$\eqalign{
& S \to ER \cr
& R \to *E\left\{ {pr{\mathop{\rm in

View Question
Consider the following C code segment.
for (i = 0; i < n; i++)
{
for (j=0; j < n; j++)
{

View Question
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packet

View Question
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packet

View Question
Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and go-bac

View Question
Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay b

View Question
For which one of the following reasons does Internet Protocol (IP) use the time-to-live (TTL) field in the IP datagram h

View Question
Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP a

View Question
Given two three bit number $${a_2}{a_1}{a_0}$$ and $${b_2}{b_1}{b_0}$$ and $$c,$$ the carry in the function that repres

View Question
Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set associate with $$32$$-byte block size. The

View Question
A $$CPU$$ has a cache with block size $$64$$ bytes. The main memory has $$k$$ banks, each bank being $$c$$ bytes wide. C

View Question
Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set associate with $$32$$-byte block size. The

View Question
A CPU has five stages pipeline and runs at $$1$$ $$GHz$$ frequency. Instruction fetch happens in the first stage of the

View Question
A $$CPU$$ has $$24$$-bit instructions. A program starts at address $$300$$ (in decimal). Which one of the following is a

View Question
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
Assume that the content

View Question
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
Assume that the content

View Question
Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.
Assume that the content

View Question
An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, X){
push(S1, X);
}
void de

View Question
The following function computes the value of mCn correctly for all legal values m and n (m≥1,n≥0 and m>n)
int func(

View Question
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is store

View Question
In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The

View Question
Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of th

View Question
Which of the following sequences of array elements forms a heap?

View Question
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array

View Question
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array

View Question
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array

View Question
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent th

View Question
Let T be a depth first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of

View Question
Let T be a depth-first search tree in an undirected graph G. Vertices u and v are
leaves of this tree T. The degrees of

View Question
Consider the relation enrolled (student, course) in which (student, course ) is the primary key, and the relation Paid (

View Question
The following functional dependencies are given :
$$\eqalign{
& AB \to CD,\,AF \to D,\,\,DE \to F, \cr
& C

View Question
Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would

View Question
Consider the relation "enrolled (student, course)" in which (student, course) is the primary key, and the relation "paid

View Question
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are Di

View Question
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are Di

View Question
Consider the relations r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The relation r1 contains 2000

View Question
Which of the following relational query languages have the same expressive power?
I) Relational algebra
II) Tuple relati

View Question
Consider a Boolean function $$f(w, x, y, z).$$ Suppose that exactly one of its inputs is allowed to change at a time. If

View Question
Consider the circuit above. Which one of the following options correctly represents $$f(x,y,z)?$$

View Question
You are given a free running clock with a duty cycle of $$50$$% and a digital waveform $$f$$ which changes only at the n

View Question
Consider the circuit in the diagram. The $$ \oplus $$ operator represents $$EX$$-$$OR.$$ The $$D$$ flip-flops are initia

View Question
Which one of the first order predicate calculus statements given below correctly expresses the following English stateme

View Question
Consider the following propositional statements:
$${\rm P}1:\,\,\left( {\left( {A \wedge B} \right) \to C} \right) \equ

View Question
In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data

View Question
A logical binary relation $$ \odot $$, is defined as follows:
Let ~ be the unary negation (NOT) operator, with higher

View Question
When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting th

View Question
Consider the following first order logic formula in which $$R$$ is a binary relation symbol.
$$\forall x\forall y\left(

View Question
Let $$P, Q$$, and $$R$$ be sets. Let $$\Delta $$ denote the symmetric difference operator defined as $$P\Delta Q = \left

View Question
Let E, F and G be finite sets.
Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$
and

View Question
Let $$X,. Y, Z$$ be sets of sizes $$x, y$$ and $$z$$ respectively. Let $$W = X x Y$$ and $$E$$ be the set of all

View Question
The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multiplication modulo 10 is not a group. Give

View Question
A relation $$R$$ is defined on ordered pairs of integers as follows:
$$\left( {x,y} \right)R\left( {u,v} \right)\,if\,x

View Question
For the set $$N$$ of natural numbers and a binary operation $$f:N \times N \to N$$, an element $$z \in N$$ is called an

View Question
Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,

View Question
Let S = {1, 2, 3,....., m} , m > 3. Let $${X_1},\,....,\,{X_n}$$ be subsets of S each of size 3. Define a function f

View Question
Consider the set S = {a, b, c, d}. Consider the following 4 partitions $$\,{\pi _1},\,{\pi _2},\,{\pi _3},\,{\pi _4}$$ o

View Question
If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices an

View Question
Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ suc

View Question
Consider the polynomial $$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3}{x^3},$$ where $${a_i} \ne 0,\forall i

View Question
For each elements in a set of size $$2n$$, an unbiased coin in tossed. The $$2n$$ coin tosses are independent. An elemen

View Question
What is the cardinality of the set of integers $$X$$ defined below?
$$X = $$ {$$n\left| {1 \le n \le 123,\,\,\,\,\,n} \r

View Question
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices

View Question
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices

View Question
Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have a

View Question
$$F$$ is an $$n$$ $$x$$ $$n$$ real matrix. $$b$$ is an $$n$$ $$x$$ $$1$$ real vector. Suppose there are two $$n$$ $$x$$

View Question
What are the eigen values of the matrix $$P$$ given below?
$$$P = \left( {\matrix{
a & 1 & 0 \cr
1 &

View Question
Consider three $$CPU$$-intensive process, which require $$10,20$$ and $$30$$ time units and arrive at times $$0,2$$ and

View Question
Consider three processes (process id $$0,1,2,$$ respectively) with compute time bursts $$2, 4,$$ and $$8$$ time units. A

View Question
Consider three processes, all arriving at time zero, with total execution time of $$10,20,$$ and $$30$$ units, respectiv

View Question
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arriv

View Question
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arriv

View Question
The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x

View Question
A Computer system supports $$32$$-bit virtual addresses as well as $$32$$-bit physical addresses. Since the virtual addr

View Question
Consider the following snapshot of a system running n processes. Process i is
holding xi instances of a resource R, for

View Question
Consider this C code to swap two integers and these five statements:
void swap(int *px, int *py)
{
*px = *px - *py

View Question
If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$

View Question
Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ ac

View Question
Let $${L_1} = \left\{ {{0^{n + m}}{1^n}{0^m}\left| {n,m \ge 0} \right.} \right\},$$
$$\,\,\,{L_2} = \left\{ {{0^{n + m}

View Question
Consider the following statements about the context-free grammar
$$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \

View Question
For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$
Let $$L = \lef

View Question
Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enum

View Question