# DS-GATE

## DS | GATE-2008 | PREVIOUS YEAR QUESTIONS| SET-13

DS | GATE-2008 | Data Structures The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.  [GATE – 2008] a. θ(m+n)b. θ(m)c. θ(n)d. θ(mn) Answer : a) The Breadth First Search algorithm has been implemented using the queue data structure. One …

## DS | GATE-2006 | PREVIOUS YEAR QUESTIONS| SET-15

DS | GATE-2006 | Data Structures A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, …

## DS | GATE-2007 | PREVIOUS YEAR QUESTIONS| SET-14

DS | GATE-2007 | Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering? [ GATE – 2007 ]

## DS | GATE-2009 | PREVIOUS YEAR QUESTIONS| SET-12

DS | GATE-2009 | 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

## DS | GATE-2010 | PREVIOUS YEAR QUESTIONS| SET-11

DS | GATE-2010 | Data Structures 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? [GATE – 2010] a. 0b. 1c. n-1d. (n-1)/2 Answer : a)DS …

## DS | GATE-2011 | PREVIOUS YEAR QUESTIONS| SET-10

DS | GATE-2011 | Data Structures 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?  [GATE – 2011] a. b. c. d. Answer : b)DS | GATE-2011 | We are given a set of n …

## DS | GATE-2012 | PREVIOUS YEAR QUESTIONS| SET-9

DS | GATE-2012 | Data Structures The worst case running time to search for an element in a balanced binary search tree with n2n elements is : [GATE – 2012] a. Θ (n log n)b. Θ (n2n)c. Θ (n)d. Θ (log n) Answer : c)DS | GATE-2012 | Data Structures The recurrence relation capturing the optimal …

## DS | GATE-2013 | PREVIOUS YEAR QUESTIONS| SET-8

DS | GATE-2013 | Data Structures 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? [GATE – 2013] a. For every subset of k vertices, the induced subgraph has at most …

## DS | GATE-2014 | PREVIOUS YEAR QUESTIONS| SET-7

DS | GATE-2014 | Data Structures Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix? [GATE – 2014] a. θ(n)b. θ(n+m)c. θ(n2 )d. θ(m2 ) Answer : c) Consider a rooted …

## DS | GATE-2015 | PREVIOUS YEAR QUESTIONS| SET-6

DS | GATE-2015 | Data Structures 1. The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are: [GATE – 2015] a. 63 and 6, respectivelyb. 64 and 5, respectivelyc. 32 and 6, respectivelyd. 31 and …