# 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, respectively
b. 64 and 5, respectively
c. 32 and 6, respectively
d. 31 and 5, respectively

2. Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. N

now consider that a value 35 is inserted into this heap. After insertion, the new heap is:  [Gate – 2015 ]

a. 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
b. 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
c. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
d. 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

3. A binary tree T has 20 leaves. The number of nodes in T having two children is _________. [Gate – 2015 ]

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

4. 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:   [Gate – 2015 ]

a. Ω(n)
b. Ω(nlog n)
c. Ω(logn)
d. Ω(n2)

5. Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020? [Gate – 2015 ]

a. h(i) = i2 mod 10
b. h(i) = i3 mod 10
c. h(i) = (11 *i2) mod 10
d. h(i) = (12 * i) mod 10

6. Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let  α be the value of RTT in milliseconds. (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size the window scale option. Then the values of α and β are: [Gate – 2015 ]

a. 63 milliseconds, 65535×214
b. 63 milliseconds, 65535×216
c. 500 milliseconds, 65535×214
d. 500 milliseconds, 65535×216

DS | GATE-2015 |

7. A younf tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked  with [Gate – 2015 ]

a. 4
b. 6
c. 5
d. 9

DS | GATE-2015 |

8. Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is  ___________. [Gate – 2015 ]

a. 50
b. 60
c. 70
d. 80

9. 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: [Gate – 2015 ]

a. 2
b. 3
c. 4
d. 5

DS | GATE-2015 |

10. 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: [Gate – 2015 ]

a. 65
b. 67
c. 69
d. 83

DS | GATE-2015 |

11. The result evaluating the postfix expression  10  5 +  60 6 /  * 8 –   is: [Gate – 2015 ]

a. 284
b. 213
c. 142
d. 71

12. Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____. [GATE – 2015]

a. 196
b. 197
c. 198
d. 199