GATE CSE 2012

## GATE CSE

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

View Question Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input

View Question A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case

View Question Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which

View Question Given the language L= { ab, aa, baa }, which of the following strings are in L* ?
1) abaabaaabaa
2) aaaabaaaa
3) baaa

View Question The protocol data unit (PDU) for the application layer in the Internet stack is

View Question In the IPv4 addressing format, the number of networks allowed under Class C addresses is

View Question An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available with it: 245.248.128.0/2

View Question Consider a source computer (S) transmitting a file of size 106 bits to a destination computer (D) over a network of two

View Question Which of the following transport layer protocols is used to support electronic mail?

View Question Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the st

View Question The decimal value $$0.5$$ in $$IEEE$$ single precision floating point representation has

View Question The amount of $$ROM$$ needed to implement a $$4$$ bit multiplier is

View Question A computer has a $$256$$ $$K$$ Byte, $$4$$-way set associative, write back data cache with block size of $$32$$ Bytes. T

View Question A computer has a $$256$$ $$K$$ Byte, $$4$$-way set associative, write back data cache with block size of $$32$$ Bytes. T

View Question Register renaming is done in pipelined processors

View Question Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insert

View Question The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudo

View Question Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of

View Question Given the basic $$ER$$ and relational models, which of the following is INCORRECT?

View Question Which of the following is TRUE?

View Question Which of the following statements are TRUE about an SQL query?
P: An SQL query can contain a HAVING clause even if it do

View Question Consider the following relations A, B and C:
A
.tg {border-collapse:collapse;border-spacing:0;}
.tg td{font-family:Ari

View Question Consider the following relations A, B and C:
A
.tg {border-collapse:collapse;border-spacing:0;}
.tg td{font-family:Ari

View Question Suppose R1 (A, B) and R2 (C, D) are two relation schemas. Let r1 and r2 be the
corresponding relation instances. B is a

View Question Consider the following transactions with data items P and Q initialized to zero:
T1 : read (P) ;
read (Q) ;

View Question What is the minimal form of the Karnaugh map shown below? Assume that $$X$$ denotes a don’t care term.

View Question Consider the following logical inferences.
$${{\rm I}_1}:$$ If it rains then the cricket match will not be played. The

View Question What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"

View Question The truth table
Represents the Boolean function

View Question Consider a random variable X that takes values + 1 and-1 with probability 0.5 each.
The values of the cumulative distr

View Question Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2 or 3 the die is rolled a second time. What

View Question How many onto (or subjective) functions are there form an n-element $$(n\, \ge \,2)$$ set to a 2-element set ?

View Question The recurrence relation capturing the optional execution time of the Towers of Hanoi problem with $$n$$ discs is

View Question Let G be a simple undirected planner graph on 10 vertices with 15 edges. If G is a connected graph, then the number of b

View Question Consider the function $$f\left( x \right) = \sin \left( x \right)$$ in the interval $$x \in \left[ {\pi /4,\,\,7\pi /4}

View Question Which of the following graphs is isomorphic to

View Question Let $$G$$ be a complete undirected graph on $$6$$ vertices. If vertices of $$G$$ $$\,\,\,\,$$ are labeled, then the numb

View Question Let $$A$$ be the $$2 \times 2$$ matrix with elements $${a_{11}} = {a_{12}} = {a_{21}} = + 1$$ and $${a_{22}} = - 1$$.

View Question A process executes the code
fork $$\left( {\,\,\,} \right);$$
fork $$\left( {\,\,\,} \right);$$
fork $$\left( {\,\,\,}

View Question Consider the $$3$$ processes, $$P1,$$ $$P2$$ and $$P3$$ shown in the table.
.tg {border-collapse:collapse;border-spac

View Question Fetch_And_Add (X, i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it

View Question Consider the virtual page reference string
$$$1,2,3,2,4,1,3,2,4,1$$$
On a demand paged virtual memory system running on

View Question A file system with 300 G Byte disk uses a file descriptor with 8 direct block addresses, 1 indirect block address and 1

View Question What will be the output of the following C program segment?
Char inchar = 'A';
Switch ( inchar ) {
case 'A' : printf ("C

View Question Consider the program given below, in a block-structured pseudo-language with lexical
scoping and nesting of procedures p

View Question Consider the following C code segment.
int a, b, c = 0;
void prtFun(void);
main( )
{
static int a = 1; /* Line 1 */

View Question Consider the following C code segment.
int a, b, c = 0;
void prtFun(void);
main( )
{
static int a = 1; /* Line 1 */

View Question What is the complement of the language accepted by the $$NFA$$ shown below?
Assume $$\sum { = \left\{ a \right\}\,\,} $

View Question Consider the set of strings on $$\left\{ {0,1} \right\}$$ in which, every substring of $$3$$ symbols has at most two zer

View Question Which of the following problems are decidable?
$$1.$$ Does a given program ever produce an output?
$$2.$$ If L is a cont

View Question