GATE CS Applied Course

GATE Previous Year Wise Questions

GATE Previous Subject Wise Questions

Question 161
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 ____.
A
358
B
438
C
568
D
664
Algorithms GATE 2014 SET 2 Greedy-Algorithm
Question 162
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
A
4
B
6
C
8
D
10
GATE 2014 SET 2
Question 163
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
A queue cannot be implemented using this stack
B
A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
C
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
D
A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.
GATE 2014 SET 2
Question 164
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
A smaller block size implies better spatial locality
B
A smaller block size implies a smaller cache tag and hence lower cache tag overhead
C
A smaller block size implies a larger cache tag and hence lower cache hit time
D
A smaller block size incurs a lower cache miss penalty
computer organization GATE 2014 SET 2
Question 165
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?
A
Width of tag comparator
B
Width of set index decoder
C
Width of way selection multiplexor
D
Width of processor to main memory data bus
computer organization GATE 2014 SET 2
Question 166
The number of distinct positive integral factors of 2014 is _________________________
Submit
GATE 2014 SET 2
Question 167
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?
A
Both S1 and S2 are true
B
S1 is true and S2 is false
C
S2 is true and S1 is false
D
Neither S1 nor S2 is true
GATE 2014 SET 2
Question 168
A cycle on n vertices is isomorphic to its complement. The value of n is _____.
Submit
GATE 2014 SET 2
Question 169
The number of distinct minimum spanning trees for the weighted graph below is ____
Submit
Algorithms GATE 2014 SET 2 Minimum-Spanning-Tree
Question 170
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) 
A
select R.* from R, S where R.a=S.a (D)
B
select distinct R.* from R,S where R.a=S.a
C
select R.* from R,(select distinct a from S) as S1 where R.a=S1.a
D
select R.* from R,S where R.a=S.a and is unique R
GATE 2014 SET 2
Question 171
A binary operation \oplus on a set of integers is defined as x \oplus y = x2 + y2. Which one of the following statements is TRUE about \oplus?
A
Commutative but not associative
B
Both commutative and associative
C
Associative but not commutative
D
Neither commutative nor associative
GATE 2013
Question 172
Which one of the following is the tightest upper bound that represents the number of swaps
required to sort n numbers using selection sort?
A
O(log n)
B
O(n)
C
O(n log n)
D
O(n^2)
Algorithms GATE 2013 Sorting
Question 173
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?
A
O(1)
B
O(log n)
C
O(n)
D
O(n log n)
Algorithms GATE 2013 Sorting
Question 174
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete
graph of n vertices?
A
B
C
D
Algorithms GATE 2013 Sorting
Question 175
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.
A
P only
B
Q only
C
Both P and Q
D
Neither P nor Q
Algorithms GATE 2013 Graph Theory
Question 176
What is the logical translation of the following statement?
    “None of my friends are perfect.”
A
∃x (F (x)∧ ¬P(x))
B
∃ x (¬ F (x)∧ P(x))
C
∃x (¬F (x)∧¬P(x))
D
¬∃ x (F (x)∧ P(x))
GATE 2013
Question 177
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
A
No two vertices have the same degree.
B
At least two vertices have the same degree.
C
At least three vertices have the same degree.
D
All vertices have the same degree.
gate 2009 Graph Theory
Question 178
The number of elements that can be sorted in Θ(log n) time using heap sort is
A
Θ(1)
B
C
D
Algorithms GATE 2013 Sorting
Question 179
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
A
\Theta(n^2)
B
\Theta(n^2Logn)
C
\Theta(n^3)
D
\Theta(n^3Logn)
GATE 2013
Question 180
What is the number of swaps required to sort n elements using selection sort, in the worst case?
A
B
C
D
Algorithms gate 2009 Sorting
© 2020 - All rights are reserved- AAIC Technologies pvt ltd