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

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

25,12,16,13,10,8,14

25,14,13,16,10,8,12

25,14,16,13,10,8,12

25,14,12,13,10,8,16

Data Structures gate 2009 Heap-Tree

Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?

14,13,12,10,8

14,12,13,8,10

14,13,8,12,10

14,13,12,8,10

Data Structures gate 2009 Heap-Tree

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

(n-1)/2

n-1

Data Structures gate 2010 Binary-Trees

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

Data Structures gate 2010 Graphs

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

46, 42, 34, 52, 23, 33

34, 42, 23, 52, 33, 46

46, 34, 42, 23, 52, 33

42, 46, 33, 23, 34, 52

Data Structures Hashing gate 2010

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

θ(n)

θ(m)

θ(m+n)

θ(mn)

Data Structures Graphs GATE 2008 CS

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

MNOPQR

NQMPOR

QMNPRO

QMNPOR

Data Structures GATE 2017 SET2 Graphs GATE 2008 CS

G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

For every subset of k vertices, the induced subgraph has at most 2k–2 edges

The minimum cut in G has at least two edges

There are two edge-disjoint paths between every pair to vertices

There are two vertex-disjoint paths between every pair of vertices

Data Structures Graphs GATE 2008 CS

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

θ(log n)

θ(n)

θ(nlog n)

None of the above, as the tree cannot be uniquely determined

Data Structures Binary-Trees GATE 2008 CS

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

θ(log n)

θ(n)

θ(nlog n)

θ(n²)

Data Structures Heap-Tree GATE 2008 CS

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?

Data Structures gate 2011

Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

1 2 3 4 5 6

1 3 2 4 5 6

1 3 2 4 6 5

3 2 4 1 6 5

Data Structures Graphs GATE 2007 CS

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:

2^h−1

2^h−1 – 1

2^h+1– 1

2^h+1

Data Structures Binary-Trees GATE 2007 CS

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Data Structures Binary-Trees GATE 2007 CS

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:

6, 1

5, 7

3, 2

1, 5

Data Structures GATE 2007 CS Stacks

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:

d e b f g c a

e d b g f c a

e d b f g c a

d e f g b c a

Data Structures Binary-Trees GATE 2007 CS

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.

8, _, _, _, _, _, 10

1, 8, 10, _, _, _, 3

1, _, _, _, _, _,3

1, 10, 8, _, _, _, 3

Data Structures Hashing GATE 2007 CS

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?

Data Structures GATE 2007 CS

Consider the following C program segment where CellNode represents a node in a binary tree:

struct CellNode
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr)
{
  int value = 0;
  if (ptr != NULL)
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Data Structures Binary-Trees GATE 2007 CS

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

θ(log₂n)

θ(log₂log₂n)

θ(n)

θ(nlog₂n)

Data Structures Heap-Tree GATE 2007 CS

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 41

Question 42

Question 43

Question 44

Question 45

Question 46

Question 47

Question 48

Question 49

Question 50

Question 51

Question 52

Question 53

Question 54

Question 55

Question 56

Question 57

Question 58

Question 59

Question 60