GATE CSE 2008
View Questions

GATE CSE

You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine t
View Question
Consider the following functions: F(n) = 2n G(n) = n! H(n) = nlogn Which of the following statements about the asymptoti
View Question
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n
View Question
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m e
View Question
Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 *
View Question
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting t
View Question
Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 *
View Question
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this hea
View Question
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into tw
View Question
Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shorte
View Question
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive in
View Question
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive in
View Question
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program i
View Question
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program i
View Question
The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine
View Question
Which of the following are true? I. A programming language which does not permit global variables of any kind and has n
View Question
Which of the following describes a handle (as applicable to LR-parsing) appropriately?
View Question
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
View Question
Some code optimizations are carried out on the intermediate code because
View Question
If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?
View Question
What is the maximum size of data that the application layer can pass on to the TCP layer below?
View Question
Which of the following system calls results in the sending of SYN packets?
View Question
In the slow start phase of the TCP congestion control algorithm, the size of the congestion window
View Question
A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server pr
View Question
A computer on a 10 Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2 Mbps. It is in
View Question
The total number of keys required for a set of n individuals to be able to communicate with each other using secret key
View Question
In the $$IEEE$$ floating point representation the hexadecimal value $$0\, \times \,00000000$$ corresponds to
View Question
For inclusion to hold between two cache levels $$L1$$ and $$L2$$ in a multilevel cache hierarchy, which of the following
View Question
The following code is to run on a pipelined processor with one branch delay slot $$\eqalign{ & {{\rm I}_1}:\,\,ADD
View Question
In an instruction execution pipeline, the earliest that the data $$TLB$$ (Translation Look aside Buffer) can be accessed
View Question
Which of the following are NOT true in a pipelined processor? $$1.$$ Bypassing can handle all RAW hazards $$2.$$ Registe
View Question
The use of multiple register windows with overlap causes a reduction in the number of memory accesses for $$1.\,\,\,\,$$
View Question
Which of the following must be true for the $$RFE$$ (Return From Exception) instruction on a general purpose processor?
View Question
Which of the following is/are true of the auto increment addressing mode? $$1.$$ It is useful in creating self relocatin
View Question
For all delayed conditional branch instructions, irrespective of whether the condition evaluate true or false,
View Question
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list.
View Question
Which of the following is TRUE?
View Question
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known
View Question
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537,
View Question
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 1
View Question
How many distinct BSTs can be constructed with 3 distinct keys?
View Question
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to det
View Question
Consider the following sequence of nodes for the undirected graph given below. 1.a b e f d g c 2.a b e f c g d 3.a d
View Question
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function
View Question
Consider the following $$ER$$ diagram The minimum number of table needed to represent $$M,$$ $$N,$$ $$P, R1, R2$$ is
View Question
Consider the following $$ER$$ diagram Which of the following is a correct attribute set for one of the tables for the
View Question
Consider the following relational schemes for a library database. Book ( Title, Author, Catalog_ no, Publisher, Year, Pr
View Question
Let $$R\left( {A,B,C,D} \right)$$ be a relational schema with the following functional dependencies: $$A \to B,\,\,B \t
View Question
Let $$R\left( {A,\,B,\,C,\,D,E,P,G} \right)$$ be a relational schema in which the following functional dependencies are
View Question
Consider The Following Relational Scheme Student (school-id, sch-roll-no, sname, saddress) School (school-id, sch-name,
View Question
Consider The Following Relational Scheme Student (school-id, sch-roll-no, sname, saddress) School (school-id, sch-name,
View Question
Which of the following tuple relational calculus expression(s) is/are equivalent to $$\forall t \in r \left(P\left(t\rig
View Question
Let R and S be two relations with the following schema R (P, Q, R1, R2, R3) S (P, Q, S1, S2) Where {P, Q} is the key for
View Question
Consider the following three schedules of transactions T1, T2 and T3. [ Notation: In the following NYO represents the ac
View Question
A clustering index is defined on the fields which are of type
View Question
Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered
View Question
Given $${f_1},$$ $${f_3},$$ and $$f$$ in canonical sum of products form (in decimal) for the circuit. $$${f_1} = \sum {m
View Question
If $$P, Q, R$$ are Boolean variables, then $$\left( {P + \overline Q } \right)$$ $$\left( {P.\overline Q + P.R} \right)
View Question
In the Karnaugh map shown below, $$X$$ denotes a don’t care term. What is the minimal form of the function represented b
View Question
A set of Boolean connectives is functionally complete if all Boolean function can be synthesized using those, Which of t
View Question
A sample space has two events A and B such that probabilities $$P\,(A\, \cap \,B)\, = \,1/2,\,\,P(\overline A )\, = \,1
View Question
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the pr
View Question
Let X be a random variable following normal distribution with mean + 1 and variance 4. Let Y be another normal variable
View Question
If $$P$$, $$Q$$, $$R$$ are Boolean variables, then $$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$
View Question
Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a finite state automation, and pda$$(y)$$ mean
View Question
Which of the following first order formulae is logically valid? Here $$\alpha \left( x \right)$$ is a first order formul
View Question
$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions are equivalent? $${\rm I}.$$ $${\rm P}\
View Question
Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \left( {\exists y,\beta \to \left( {\forall
View Question
What is the probability that in a randomly choosen group of r people at least three people have the same birthday?
View Question
If $$P, Q, R$$ are subsets of the universal set $$U$$, then $$\left( {P \cap Q \cap R} \right) \cup \left( {{P^c} \cap
View Question
The following system of equations $${x_1}\, + \,{x_2}\, + 2{x_3}\, = 1$$ $${x_1}\, + \,2 {x_2}\, + 3{x_3}\, = 2$$ $${
View Question
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
View Question
$$\mathop {\lim }\limits_{x \to \infty } {{x - \sin x} \over {x + \cos \,x}}\,\,Equals$$
View Question
If $$\,\,\,\,f\,\,\,\,\left( x \right)$$ is defined as follows, what is the minimum value of $$f\,\left( x \right)$$ for
View Question
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema
View Question
What is the chromatic number of the following graph?
View Question
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain no consecutive $$0s$$. The value of $${x_
View Question
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains no consecutive $$0s$$. Which of the foll
View Question
The exponent of $$11$$ in the prime factorization of $$300!$$ is
View Question
In how many ways can $$b$$ blue balls and $$r$$ red balls be distributed in $$n$$ distinct boxes?
View Question
When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right
View Question
Which of the following statements is true for every planar graph on $$n$$ vertices?
View Question
$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adja
View Question
$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint span
View Question
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respective
View Question
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respective
View Question
How many of the following matrices have an eigen value $$1$$? $$\left[ {\matrix{ 1 & 0 \cr 0 & 0 \cr
View Question
If $$M$$ is a square matrix with a zero determinant, which of the following assertion(s) is (are) correct? $$S1$$ : Eac
View Question
The value of $$\int\limits_0^3 {\int\limits_0^x {\left( {6 - x - y} \right)dxdy\,\,\,} } $$ is _____.
View Question
A process executes the following code for (i = 0; i < n; i + +) fork ( ); The total number of child processes create
View Question
Which of the following is/are true of the auto-increment addressing mode? $${\rm I}.\,\,\,$$ It is useful in creating se
View Question
The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows: P(s): s = s-1;
View Question
A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page t
View Question
The data blocks of a very large file in the Unix file system are allocated using
View Question
For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance
View Question
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
View Question
Which of the following are true? I. A programming language which does not permit global variables of any kind and has no
View Question
Choose the correct option to fill ? 1 and ? 2 so that the program below prints an input string in reverse order. Assume
View Question
What is printed by the following C program? #include < stdio.h > int f(int x, int *py, int **ppz) { int y, z;
View Question
Given below are two finite state automata ($$ \to $$ indicates the start state and $$F$$ indicates a final state) W
View Question
Match the following $$NFAs$$ with the regular expressions they correspond to
View Question
Which of the following are regular sets?
View Question
Which of the following statement is false?
View Question
Which of the following statements are true? $$1.$$ Every left-recursive grammar can be converted to a right-recursive g
View Question
Match the following List-$${\rm I}$$ with List - $${\rm II}$$ List-$${\rm I}$$ $$E)$$ Checking that identifiers are decl
View Question
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$
View Question
If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is
View Question
Which of the following are decidable? $$1.$$ Whether the intersection of two regular languages is infinite $$2.$$ Whethe
View Question
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12