GATE CSE 2006
View Questions

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
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12