CS/IT Gate Subject



Data Structure GATE CS and IT previous year questions with Answer


Ques 41 Gate 2016 Set-1

What will be the output of the following C program?

void count(int n)
{
    static int d = 1;
    printf("%d ", n);
    printf("%d ", d);
    d++;
    if(n > 1) count(n-1);
    printf("%d ", d);
}
int main()
{
    count(3);
}


A

3 1 2 2 1 3 4 4 4

B

3 1 2 1 1 1 2 2 2

C

3 1 2 2 1 3 4

D

3 1 2 1 1 1 2



Ques 42 Gate 2016 Set-1

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

A

P only

B

Q only

C

Both P and Q

D

Neither P nor Q



Ques 43 Gate 2016 Set-1

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

A

Both operations can be performed in O(1) time

B

At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)

C

The worst case time complexity for both operations will be Ω(n)

D

Worst case time complexity for both operations will be Ω(logn)



Ques 44 Gate 2015 Set-3

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


a is the correct answer.


Ques 45 Gate 2015 Set-3

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

A

256

B

512

C

1024

D

2048



Ques 46 Gate 2015 Set-3

Consider the following array of elements.

〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉.

The minimum number of interchanges needed to convert it into a max-heap is

A

4

B

5

C

3

D

2



Ques 47 Gate 2015 Set-3

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

A

65

B

67

C

69

D

83



Ques 48 Gate 2015 Set-3

The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is

A

284

B

213

C

142

D

71



Ques 49 Gate 2015 Set-2

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


a is the correct answer.


Ques 50 Gate 2015 Set-2

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

A

Ω(logn)

B

Ω(n)

C

Ω(nlogn)

D

Ω(n2)