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 &gt; 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{ &amp; S \to S*E \cr &amp; S \to E \cr &amp; 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{ &amp; S \to FR \cr &amp; R \to *S\,|\,\varepsilon \cr &amp; F \to
View Question
Consider the following translation scheme. \eqalign{ &amp; S \to ER \cr &amp; R \to *E\left\{ {pr{\mathop{\rm in View Question Consider the following C code segment. for (i = 0; i &lt; n; i++) { for (j=0; j &lt; 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$$32KB2$$-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$$32KB2$$-way set associate with$$32$$-byte block size. The View Question A CPU has five stages pipeline and runs at$$1GHz$$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&gt;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{ &amp; AB \to CD,\,AF \to D,\,\,DE \to F, \cr &amp; 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 &lt; p &lt; 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 &gt; 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$$nxn$$real matrix.$$b$$is an$$nx1$$real vector. Suppose there are two$$nx$$View Question What are the eigen values of the matrix$$P$$given below?$$\$P = \left( {\matrix{ a &amp; 1 &amp; 0 \cr 1 &amp;
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
NEETAIIMS