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