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

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

40, 30, 20, 10, 15, 16, 17, 8, 4, 35

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

40, 30, 20, 10, 35, 16, 17, 8, 4, 15

40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Data Structures GATE 2015 SET 1 Heap-Tree

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The
lower bound for the number of operations to convert the tree to a heap is

Ω(log n)

Ω(n)

Ω(n log n)

Data Structures GATE 2015 SET 2 Heap-Tree

A binary tree T has 20 leaves. The number of nodes in T having two children is _______.

Submit

Data Structures GATE 2015 SET 2 Binary-Trees

Submit

Data Structures GATE 2015 SET 2

Data Structures GATE 2015 SET 2 Hashing

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly
two children are ________.

Submit

Data Structures GATE 2015 SET3 Binary-Trees

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is
____________.

Submit

Data Structures GATE 2015 SET3 Hashing

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.

θ(n)

θ(n+m)

θ(n² )

θ(m² )

Data Structures GATE 2014 SET 1 Graphs

Consider a rooted Binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having having exactly 4 nodes O(n^a Logn ^b). Then the value of a + 10b is ________

Data Structures GATE 2014 SET 1 Time-Complexity

Consider the directed graph given below.
GATECS2014Q22

Which one of the following is TRUE?

The graph does not have any topological ordering

Both PQRS and SRQP are topological orderings

Both PSRQ and SPRQ are topological orderings.

PSRQ is the only topological ordering.

Data Structures GATE 2014 SET 1 Graphs

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

t1 = 5

t1 < t2

t1 > t2

t1 = t2

Data Structures GATE 2014 SET 1 Quick-Sort

Consider a hash table with 9 slots. The hash function is ?(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

3, 0, and 1

3, 3, and 3

4, 0, and 1

3, 0, and 2

Data Structures GATE 2014 SET 1 Hashing

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

10, 8, 7, 3, 2, 1, 5

10, 8, 7, 2, 3, 1, 5

10, 8, 7, 1, 2, 3, 5

10, 8, 7, 5, 3, 2, 1

Data Structures GATE 2014 SET 2 Heap-Tree

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing.

the shortest path between every pair of vertices.

the shortest path from W to every vertex in the graph

the shortest paths from W to only those nodes that are leaves of T.

the longest path in the graph

Data Structures GATE 2014 SET 2 Graphs

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

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

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

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

GATE Previous Year Wise Questions

GATE Previous Subject Wise Questions

Question 21

Question 22

Question 23

Question 24

Question 25

Question 26

Question 27

Question 28

Question 29

Question 30

Question 31

Question 32

Question 33

Question 34

Question 35

Question 36

Question 37

Question 38

Question 39

Question 40