GATE CSE 2014 Set 1

## GATE CSE

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the n

View Question The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________

View Question Consider the following pseudo code. What is the total number of multiplications to be performed?
D = 2
for i = 1 to n do

View Question Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a
given graph. In this s

View Question A canonical set of items is given below
$$\eqalign{
& S \to L. > R \cr
& Q \to R. \cr} $$
On input symb

View Question Which one of the following is FALSE?

View Question Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with

View Question Consider the following three statements about link state and distance vector routing protocols, for a large network with

View Question Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connect

View Question Which one of the following are used to generate a message digest by the network security protocols?
(P) RSA (Q) SHA-1 (

View Question An access sequence of cache block addresses is of length $$N$$ and contains $$n$$ unique block address. The number of un

View Question Consider a $$6$$-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time

View Question A machine has a $$32$$-bit architecture, with $$1$$-word long instructions. It has $$64$$ registers, each of which is $$

View Question Consider two processors ܲ$${P_1}$$ and $${P_2}$$ executing the same instruction set. Assume that under identical conditi

View Question Consider the following C functions in which size is the number of elements in the array E:
int MyX(int *E, unsigned int

View Question Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The fo

View Question Let G be a graph with n vertices and m edges. What is the tightest upper bound on the
running time of Depth First Search

View Question Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine

View Question Consider the relation schema $$R = \left( {E,\,F,\,G,\,H,\,I,\,J,\,K,L,\,M,\,N} \right)$$ and the set of functional depe

View Question Given the following two statements:
$$S1:$$ Every table with two single-valued attributes is in $$1NF, 2NF, 3NF$$ and $$

View Question Given the following statements:
S1: A foreign key declaration can always be replaced by an equivalent check assertion in

View Question Given the following schema:
employees(emp-id, first-name, last-name, hire-date, dept-id, salary)
departments(dept-id, d

View Question Consider the following four schedules due to three transactions (indicated by the subscript) using
read and write on a d

View Question The base (or radix) of the number system such that the following equation holds is __________
$${{312} \over {20}} = 13.

View Question Consider the following Boolean expression for $$F:$$
$$F\left( {P,\,Q,\,R,\,S} \right) = PQ + \overline P QR + \overlin

View Question Consider the $$4$$-to-$$1$$ multiplexer with two select lines $${S_1}$$ and $${S_0}$$ given below
The minimal sum-of-p

View Question Consider the statement
"Not all that glitters is gold"
Predicate glitters$$(x)$$ is true if $$x$$ glitters and
predic

View Question Suppose you break a stick of unit length at a point chosen uniformaly at random. Then the expected length of the shorter

View Question Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is X/1296. The value of X is__

View Question Which one of the following propositional logic formulas is TRUE when exactly two of $$p, q,$$ and $$r$$ are TRUE?

View Question Let S denote the set of all functions $$f:\,{\{ 0,\,1\} ^4}\, \to \,\{ 0,\,1\} $$. Denote by N the number of functions f

View Question The value of the dot product of the eigenvectors corresponding to any pair of different eigen values of a 4-by-4 symmetr

View Question Consider the following system of equations:
3x + 2y = 1
4x + 7z = 1
x + y + z =3
x - 2y + 7z = 0
The number of solu

View Question Let the function
$$f\left( \theta \right) = \left| {\matrix{
{\sin \,\theta } & {\cos \,\theta } & {\tan \,

View Question The function $$f(x) =$$ $$x$$ $$sinx$$ satisfies the following equation:
$$f$$"$$\left( x \right) + f\left( x \right) +

View Question A function $$f(x)$$ is continuous in the interval $$\left[ {0,2} \right]$$. It is known that $$f(0)$$ $$=$$ $$f(2)$$ $$=

View Question There are 5 bags labeled 1 to 5. All the coins in given bag have the same weight. Some bags have coins of weight 10 gm,

View Question A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n.

View Question Let $$G = \left( {V,E} \right)$$ be a directed graph where $$V$$ is the set of vertices and $$E$$ the set of edges. Then

View Question The maximum number of edges in a bipartite graph on $$12$$ vertices is _________.

View Question An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}

View Question Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,

View Question Which one of the following is FALSE?

View Question Consider the following set of processes that need to be scheduled on a single $$CPU.$$ All the times are given in millis

View Question Assume that there are $$3$$ page frames which are initially empty. If the page reference string is $$1, 2, 3, 4, 2, 1, 5

View Question Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a q

View Question An operating system uses the Banker’s algorithm for deadlock avoidance when managing the
allocation of three resource ty

View Question Consider the following program in C language:
#include < stdio.h >
main()
{
int i;
int *pi = &i;
scanf("%d", p

View Question Match the following:
$$1)$$ Waterfall model
$$2)$$ Evolutionary model
$$3)$$ Component-based software engineering
$$4)$

View Question Which one of the following is TRUE?

View Question Consider the finite automation in the following figure.
What is the set of reachable states for the input string $$001

View Question Which of the regular expression given below represent the following $$DFA?$$

View Question Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

View Question