GATE CS Applied Course

GATE Previous Year Wise Questions

gate 2018 GATE 2019 gate 2016 gate 2016 set 1 GATE 2017 SET 1 GATE 2017 SET2 GATE 2015 SET 1 GATE 2015 SET 2 GATE 2015 SET3 GATE 2014 SET 1 GATE 2014 SET 2 GATE 2013 gate 2009 GATE 2012 gate 2010 GATE 2019 GATE 2014 SET 3 gate 2011 GATE 2008 CS GATE 2008 IT GATE 2007 CS GATE 2007 IT GATE 2006 CS GATE 2006 IT GATE 2005 CS GATE 2005 IT GATE 2004 CS

GATE Previous Subject Wise Questions

Data Structures Algorithms operating systems computer organization Computer Networks DBMS Graph Theory

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

358

438

568

664

Algorithms GATE 2014 SET 2 Greedy-Algorithm

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.
GATECS2014Q38

GATE 2014 SET 2

Suppose implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

A queue cannot be implemented using this stack

A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

GATE 2014 SET 2

In designing a computer’s cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?

A smaller block size implies better spatial locality

A smaller block size implies a smaller cache tag and hence lower cache tag overhead

A smaller block size implies a larger cache tag and hence lower cache hit time

A smaller block size incurs a lower cache miss penalty

computer organization GATE 2014 SET 2

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

Width of tag comparator

Width of set index decoder

Width of way selection multiplexor

Width of processor to main memory data bus

computer organization GATE 2014 SET 2

The number of distinct positive integral factors of 2014 is _________________________

Submit

GATE 2014 SET 2

Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements:

S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.

Which one of the following is CORRECT?

Both S1 and S2 are true

S1 is true and S2 is false

S2 is true and S1 is false

Neither S1 nor S2 is true

GATE 2014 SET 2

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

Submit

GATE 2014 SET 2

The number of distinct minimum spanning trees for the weighted graph below is ____

Submit

Algorithms GATE 2014 SET 2 Minimum-Spanning-Tree

SQL allows tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below:

    select * from R where a in (select S.a from S)

select R.* from R, S where R.a=S.a (D)

select distinct R.* from R,S where R.a=S.a

select R.* from R,(select distinct a from S) as S1 where R.a=S1.a

select R.* from R,S where R.a=S.a and is unique R

GATE 2014 SET 2

A binary operation $\oplus$ on a set of integers is defined as x $\oplus$ y = x² + y². Which one of the following statements is TRUE about $\oplus$ ?

Commutative but not associative

Both commutative and associative

Associative but not commutative

Neither commutative nor associative

GATE 2013

Which one of the following is the tightest upper bound that represents the number of swaps
required to sort n numbers using selection sort?

O(log n)

O(n)

O(n log n)

O(n^2)

Algorithms GATE 2013 Sorting

Which one of the following is the tightest upper bound that represents the time complexity of
inserting an object into a binary search tree of n nodes?

O(1)

O(log n)

O(n)

O(n log n)

Algorithms GATE 2013 Sorting

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete
graph of n vertices?

Algorithms GATE 2013 Sorting

Which of the following statements is/are TRUE for undirected graphs?

P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

P only

Q only

Both P and Q

Neither P nor Q

Algorithms GATE 2013 Graph Theory

What is the logical translation of the following statement?
“None of my friends are perfect.”

∃x (F (x)∧ ¬P(x))

∃ x (¬ F (x)∧ P(x))

∃x (¬F (x)∧¬P(x))

¬∃ x (F (x)∧ P(x))

GATE 2013

Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?

No two vertices have the same degree.

At least two vertices have the same degree.

At least three vertices have the same degree.

All vertices have the same degree.

gate 2009 Graph Theory

The number of elements that can be sorted in Θ(log n) time using heap sort is

Θ(1)

Algorithms GATE 2013 Sorting

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}

The return value of the function is

$\Theta(n^2)$