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
Answer : a)
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
Answer : b)
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
Answer : a)
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)
Answer : c)
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
Answer : b)
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
Answer : c)
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
Answer : c)
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
Answer : d)
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
Answer : b)
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
Answer : b)
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
Answer : c)
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
Answer : d)