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 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 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 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 uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay b

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 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 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 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 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 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 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 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 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 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