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
Question 241
The subset-sum problem is defined as follows. Given a set of n positive integers,S = {a1 , a2 , a3 ,..., an },   and  positive  integer  W,  is  there  a  subset  of  S  whose elements sum to W? A dynamic program for solving this
    
A
X[i, j] = X[i - 1, j] ∨ X[i, j - ai]
B
X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai]
C
X[i, j] = X[i - 1, j] ∧ X[i, j - ai]
D
X[i, j] = X[i - 1, j] ∧ X[i -1, j - ai]
Algorithms Dynamic-Programming GATE 2008 CS
Question 242
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 , a2 , a3 ,..., an },   and  positive  integer  W,  is  there  a  subset  of  S  whose elements sum to W? A dynamic program for solving this
 Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
A
X[1, W]
B
X[n, 0]
C
X[n, W]
D
X[n-1, n]
Algorithms Dynamic-Programming GATE 2008 CS
Question 243
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?  
A
B
C
D
Data Structures gate 2011
Question 244
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below. Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array  
Which of the following statements is TRUE?
A
The algorithm uses dynamic programming paradigm
B
The algorithm has a linear complexity and uses branch and bound paradigm
C
The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
D
The algorithm uses divide and conquer paradigm.
Algorithms Dynamic-Programming gate 2011
Question 245
Which of the given options provides the increasing order of asymptotic complexity of functions 
A
f3, f2, f4, f1
B
f3, f2, f1, f4
C
f2, f3, f1, f4
D
f2, f3, f4, f1
Algorithms gate 2011
Question 246
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:  
A
248000
B
44000
C
19000
D
25000
Algorithms Dynamic-Programming gate 2011
Question 247
Database table by name Loan_Records is given below. 
Borrower    Bank_Manager   Loan_Amount
 Ramesh      Sunderajan     10000.00
 Suresh      Ramgopal       5000.00
 Mahesh      Sunderajan     7000.00

What is the output of the following SQL query?


SELECT Count(*) 
FROM  ( ( SELECT Borrower, Bank_Manager 
          FROM Loan_Records) AS S 
          NATURAL JOIN ( SELECT Bank_Manager, Loan_Amount 
                         FROM Loan_Records) AS T );
A
3
B
9
C
5
D
6
DBMS gate 2011
Question 248
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?    
A
1/12(11n2-5n)
B
n2 – n + 1
C
6n – 11
D
2n + 1
Algorithms Minimum-Spanning-Tree gate 2011
Question 249
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.

 The length of the path from v5 to v6 in the MST of previous question with n  =10 is
A
11
B
25
C
31
D
41
Algorithms Minimum-Spanning-Tree gate 2011
Question 250
Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering? 
A
1 2 3 4 5 6
B
1 3 2 4 5 6
C
1 3 2 4 6 5
D
3 2 4 1 6 5
Data Structures Graphs GATE 2007 CS
Question 251
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
A
2h−1
B
2h−1 – 1
C
2h+1– 1
D
2h+1
Data Structures Binary-Trees GATE 2007 CS
Question 252
The maximum number of binary trees that can be formed with three unlabeled nodes is:
A
1
B
5
C
4
D
3
Data Structures Binary-Trees GATE 2007 CS
Question 253
Which of the following sorting algorithms has the lowest worst-case complexity?
A
Merge sort
B
Bubble Sort
C
Quick Sort
D
Selection Sort
Algorithms Time-Complexity GATE 2007 CS
Question 254
Consider the following segment of C-code: 
  int j, n;
  j = 1;
  while (j <= n)
        j = j*2;
The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.
A
⌈log2n⌉ + 1
B
n
C
⌈log2n⌉
D
⌊log2n⌋+1
Algorithms Time-Complexity GATE 2007 CS
Question 255
The following postfix expression with single digit operands is evaluated using a stack: 
8 2 3 ^ / 2 3 * + 5 1 * -
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
A
6, 1
B
5, 7
C
3, 2
D
1, 5
Data Structures GATE 2007 CS Stacks
Question 256
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
A
d e b f g c a
B
e d b g f c a
C
e d b f g c a
D
d e f g b c a
Data Structures Binary-Trees GATE 2007 CS
Question 257
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
A
8, _, _, _, _, _, 10
B
1, 8, 10, _, _, _, 3
C
1, _, _, _, _, _,3
D
1, 10, 8, _, _, _, 3
Data Structures Hashing GATE 2007 CS
Question 258
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
A
Dijkstra’s algorithm starting from S
B
Warshall’s algorithm
C
Performing a DFS starting from S.
D
Performing a BFS starting from S
Algorithms Time-Complexity GATE 2007 CS
Question 259
A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?
A
3
B
4
C
5
D
6
Data Structures GATE 2007 CS
Question 260
In the following C function, let n >= m.
int gcd(n,m)
{
  if (n%m ==0) return m; 
  n = n%m;
  return gcd(m,n);
}
How many recursive calls are made by this function?
A
θ (log2 n)
B
Ω (n)
C
θ (log2log2 n)
D
θ(√n)
Algorithms Time-Complexity GATE 2007 CS
TESTIMONIAL'S
Team
Contact Us
Terms & Conditions
Privacy Policy
Youtube
Facebook
Linkedin
Powered by
Buy Gate CS
Free Videos
Practice Tests
Forum
FAQ'S
Team
Contact Us
Terms & Conditions
Privacy Policy
Youtube
Facebook
Linkedin
Powered by
© 2024 - All rights are reserved- AAIC Technologies pvt ltd