Data Structure GATE Questions

A highly popular method used to prepare for the GATE Exam is to practise all the previous years’ GATE Questions to attain perfection. Candidates can practise, analyse and understand concepts while solving them. It will also help you strengthen your time management skills. We have attempted to compile, here in this article, a collection of GATE Questions on Data Structure.

Candidates are urged to practise these Data Structure GATE previous years’ questions to get the best results. Data Structure is an important topic in the GATE CSE question paper, and solving these questions will help the candidates to prepare more proficiently for the GATE exams. Therefore, candidates can find the GATE Questions for Data Structure in this article to solve and practise before the exams. They can also refer to these GATE previous year question papers and start preparing for the exams.

GATE Questions on C Programming

1. A program P reads in 500 integers in the range [0, 100], representing the cores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

(GATE CSE 2005)

1. An array of 50 numbers
2. An array of 100 numbers
3. An array of 500 numbers
4. A dynamically allocated array of 550 numbers

Answer (a)

2. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is ___________.

(GATE CSE 2004)

1. (top 1 = MAXSIZE/2) AND (top 2 = MAXSIZE/2 + 1)
2. top 1 + top 2 = MAXSIZE
3. (top 1 = MAXSIZE/2) or (top 2 = MAXSIZE)
4. top 1 = top 2 – 1

Answer (d)

3. Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverses the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where 1 ≤ k < n: reverse (s, 1, k);

reverse (s, k+1, k);

reverse (s, 1, n);

(GATE CSE 2000)

1. Rotates s left by k positions
2. Leaves s unchanged
3. Reverse all elements of s
4. None of the above

Answer (a)

4. Consider a double hashing scheme in which the primary hash function is h₁(k)=k mod 23, and the secondary hash function is h₂(k)=1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key-value k=90 is ________.

(GATE CSE 2020)

1. 8
2. 13
3. 15
4. 20

Answer (b)

5. Consider the following two statements:

i. A hash function (these are often used for computing digital signatures) is an injective function.

ii. encryption technique such as DES performs a permutation on the elements of its input alphabet.

Which one of the following options is valid for the above two statements?

(GATE CSE 2007)

1. Both are false
2. Statement i is true and statement ii is false
3. Statement ii is true and statement i is false
4. Both are true

Answer (c)

6. A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers, and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

(GATE CSE 2005)

1. 2
2. 3
3. 4
4. 6

Answer (d)

7. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i) 9679, 1989, 4199 hash to the same value

ii) 1471, 6171 has to the same value

iii) All elements hash to the same value

iv) Each element hashes to a different value

(GATE CSE 2004)

1. i only
2. ii only
3. i and ii only
4. iii or iv

Answer (c)

8. N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(N), delete, O(log⁡N) insert, O (log⁡N) fund, and Θ(N) decrease key. What is the time complexity of all these operations put together?

(GATE CSE 2016 Set 2)

1. O(log²N)
2. O(N)
3. O(N²)
4. Θ(N²logN)

Answer (c)

9. Let P be a singly linked list; let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete node x from the list?

(GATE CSE 2004)

1. O(n)
2. O(log²n)
3. O(log n)
4. O(1)

Answer (d)

10. 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)?

(GATE CSE 2016 Set 1)

1. Both operations can be performed in O(1) time
2. At most, one operation can be performed in O(1) time, but the worst-case time for the other operation will be Ω(n)
3. The worst-case time complexity for both operations will ne Ω(n)
4. The worst-case time complexity for both operations will be Ω(log n)

Answer (a)

11. A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

(GATE CSE 2005)

1. 6
2. 4
3. 3
4. 2

Answer (c)

12. Consider the following statements:

(i) First-in-first out types of computations are efficiently supported by STACKS.

(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.

(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.

(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

(GATE CSE 1996)

1. ii and iii are true
2. i and ii are true
3. iii and iv are true
4. ii and iv are true

Answer (a)

13. The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. Then the height of the binary tree is ________.

(GATE CSE 2018)

1. 5
2. 4
3. 10
4. 1

Answer (b)

14. 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, in X[2i+1]. To be able to store any binary tree on n vertices, the minimum size of X should be ________.

(GATE CSE 2006)

1. Log n
2. n
3. 2n + 1
4. 2n – 1

Answer (b)

15. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

(GATE CSE 2004)

1. 2
2. 3
3. 4
4. 5

Answer (b)