# DS |GATE-2020| PREVIOUS YEAR QUESTIONS| SET-1 DS |GATE-2020| Data Structure

1. The pre-order traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the post-order traversal of the tree? [GATE– 2020]

a. 20, 19, 18, 16, 15, 12, 11, 10
b. 10, 11, 12, 15, 16, 18, 19, 20
c. 11, 12, 10, 16, 19, 18, 20, 15
d. 19, 16, 18, 20, 11, 12, 10, 15

2. Consider a double hashing scheme in which the primary hash function is h1(k)=k mod 23, and the secondary hash function is h2(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– 2020]

a. 11
b. 13
c. 15
d. 17

3. What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order? [GATE – 2020]

a. O (n log n)
b. O (n^2)
c. O (1)
d. Both option A and B

DS |GATE-2020|

4. Consider the following C program. [GATE – 2020]

#include
int main () {
int a   = {{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}};
printf (“%d\n”, *(* (a+**a+2) +3));
return (0);
}
The output of the program is _______.

a. 19
b. 20
c. 21
d. 22

5. What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially? [GATE – 2020]

a. O(n^4)
b. O(n^3)
c. O(n^2)
d. O(n^2 log n)

DS |GATE-2020|

6. In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k. [GATE – 2020]

a. O(n log k)
b. O(k log n)
c. O(log n + k)
d. O(log n)

DS |GATE-2020|

7. Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______. [GATE – 2020]

a. 511
b. 519
c. 600
d. 611