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

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm?

P. Always finds a negative weighted cycle, if one
Q. Finds whether any negative weighted cycle is reachable from the source.

P Only

Q Only

Both P and Q

Neither P nor Q

Algorithms gate 2009 Shortest-Path

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which
one of the following is the postorder traversal sequence of the same tree?

10, 20, 15, 23, 25, 35, 42, 39, 30

15, 10, 25, 23, 20, 42, 35, 39, 30

15, 20, 10, 23, 25, 42, 35, 39, 30

15, 10, 23, 25, 20, 35, 42, 39, 30

Algorithms GATE 2013

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?

Θ(n)

Θ(n + k)

Θ(nk)

Algorithms GATE 2013 Time-Complexity

The worst case running time to search for an element in a balanced binary search tree with n2ⁿ elements is

Θ (n log n)

Θ (n2ⁿ)

Θ (n)

Θ (log n)

Data Structures GATE 2012 Binary-Trees

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

T(n) = 2T(n - 2) + 2

T(n) = 2T(n - 1) + n

T(n) = 2T(n/2) + 1

T(n) = 2T(n - 1) + 1

Data Structures Recursion GATE 2012

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

A(n) = Ω (W(n))

A(n) = Θ (W(n))

A(n) = O (W(n))

A(n) = o (W(n))

Algorithms GATE 2012 Time-Complexity

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?

T' = T with total weight t' = t²

T' = T with total weight t'2

T' ≠ T but total weight t' = t²

None of the above

Algorithms GATE 2012 Minimum-Spanning-Tree

Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

full: (REAR+1)mod n == FRONT
empty: REAR == FRONT

full: (REAR+1)mod n == FRONT
empty: (FRONT+1) mod n == REAR

full: REAR == FRONT
empty: (REAR+1) mod n == FRONT

full: (FRONT+1)mod n == REAR
empty: REAR == FRONT

Data Structures GATE 2012 Queues

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

O (n log n)

O (n² log n)

O (n² + log n)

O (n²)

Algorithms GATE 2012 Merge-Sort

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

SDT

SBDT

SACDT

SACET

Algorithms Shortest-Path GATE 2012

Suppose R₁(A, B) and R₂(C, D) are two relation schemas. Let r₁ and r₂ be the corresponding relation instances. B is a foreign key that refers to C in R₂. If data in r₁ and r₂ satisfy referential integrity constraints, which of the following is ALWAYS TRUE?

∏_B (r₁) - ∏_C (r₂) = ∅

∏_C (r₂) - ∏_B (r₁) = ∅

∏_B (r₁) = ∏_C (r₂)

∏_B (r₁) - ∏_C (r₂) ≠ ∅

DBMS GATE 2012

The height of a tree is defined as the number of edges on the longest path in the tree. The function
shown in the pseudocode below is invoked as height(root) to compute the height of a binary
tree rooted at the tree pointer root

.

The appropriate expressions for the two boxes B1 and B2 are

B1: (1+height(n→right))
B2: (1+max(h1,h2))

B1: (height(n→right))
B2: (1+max(h1,h2))

B1: height(n→right)
B2: max(h1,h2)

B1: (1+ height(n→right))
B2: max(h1,h2)

Data Structures GATE 2012 Binary-Trees

Consider the above tables A, B and C. How many tuples does the result of the following SQL query contains?

SELECT A.id 
FROM   A 
WHERE  A.age > ALL (SELECT B.age 
                    FROM   B 
                    WHERE  B. name = "arun")

GATE 2012

Algorithms gate 2009 Time-Complexity

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

Data Structures gate 2009 Hashing

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Data Structures gate 2009 AVL-Trees

(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)

(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)

(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)

(b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

Algorithms gate 2009 Minimum-Spanning-Tree

Algorithms gate 2009 Sorting

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:

l(i,j) = 0, if either i=0 or j=0
       = expr1, if i,j > 0 and X[i-1] = Y[j-1]
       = expr2, if i,j > 0 and X[i-1] != Y[j-1]

expr1 ≡ l(i-1, j) + 1

expr1 ≡ l(i, j-1)

expr2 ≡ max(l(i-1, j), l(i, j-1))

expr2 ≡ max(l(i-1,j-1),l(i,j))

Algorithms gate 2009 Dynamic-Programming

Consider the data given in the previous question. The values of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m+1 and N =n+1, such that L[i, j] = l(i, j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?

All elements L should be initialized to 0 for the values of l(i,j) to be properly computed

The values of l(i,j) may be computed in a row major order or column major order of L(M,N)

The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N)

L[p,q] needs to be computed before L[r,s] if either p < r or q < s

Algorithms gate 2009 Dynamic-Programming

TESTIMONIAL'S

Team
Contact Us
Terms & Conditions
Privacy Policy

Youtube
Facebook
Linkedin

Buy Gate CS
Free Videos
Practice Tests
Forum

FAQ'S
Team
Contact Us
Terms & Conditions
Privacy Policy

Youtube
Facebook
Linkedin

GATE Previous Year Wise Questions

GATE Previous Subject Wise Questions

Question 181

Question 182

Question 183

Question 184

Question 185

Question 186

Question 187

Question 188

Question 189

Question 190

Question 191

Question 192

Question 193

Question 194

Question 195

Question 196

Question 197

Question 198

Question 199

Question 200