Data Structures and Algorithms Design (SSZG519)- Quiz-2-MTech Software Systems- BITS Pilani-WILP

Data Structures and Algorithms Design (SSZG519)- Quiz- 2

MTech Software Systems- WILP(Work Integrated Learning Programmes) 

Birla Institute of Technology and Science, Pilani

1. Consider the following statements.

i) External nodes of heap does not store any keys or elements
ii) Insertion and deletion in heap can be done in O(logn) time
iii) Min can be found in constant time.

Select one:
a. None of the above
b. i, ii are true and iii is false
c. i is true  and ii, iii are false
d. All of them are true
e. All of them are false

Ans: d. All of them are true

2. Which of the sorting algorithm has same running time for every input of size n?

Select one:
a. Heap sort
b. Insertion Sort
c. Selection Sort
d. None of the above

Ans: c. Selection Sort

3. What is the best case running time for heap sort?

Select one:
a. O(n log n)
b. O(n)
c. None of the above
d. O(log n)
e. O(n²)

Ans: a. O(n log n)

4. Which of the following has more than O(n) space requirement where n is the number of items stored.

Select one:
a. Direct Address Table
b. Look-up Table
c. None of the above
d. Binary Search Tree
e. Log File

Ans: a. Direct Address Table

5. Which of the following statements are true?

i. In linear probing method, there are only m different probe sequences are possible.
ii. In quadratic probing method,  there are m^2 different probe sequences are possible
iii. In double hashing, there are only m different probe sequences are possible.

Select one:
a. None of the above
b. All of them are true
c. i is true  and ii, iii are false
d. All of them are false
e. i, ii are true and iii is false

Ans: e. i, ii are true and iii is false

6. A binary search tree has n internal nodes. The number of external nodes is at most

Select one:
a. n
b. n+1
c. None of these
d. 2n
e. log n

Ans: d. 2n

7. Let T be a binary search tree built by receiving keys 3, 5, 10, 4, 8, 12, 2, 9. The in-order traversal of T is

Select one:
a. Any random order of 3, 5, 10, 4, 8, 12, 2, 9
b. 2, 3, 4, 5, 8, 9, 10, 12
c. 12, 10, 9, 8, 5, 4, 3, 2
d. None of the above
e. 3, 5, 10, 4, 8, 12, 2, 9

Ans: b. 2, 3, 4, 5, 8, 9, 10, 12

8. The worst case running time to find a maximum element in Binary search tree with n items is

Select one:
a. O(1)
b. O(n2)
c. None of the above
d. O(n)
e. O(logn)

Ans: d. O(n)

9. Which of the following  have O(1) running time for insert operation.

Select one:
a. Binary Search Tree, Look-up Table
b. Look-up Table, Hash Table
c. Hash Table, Binary Search Tree
d. Log File, Hash Table
e. None of the above

Ans: d. Log File, Hash Table

10. Keys { 200,205,210,...,600} are stored in a chained hash table.

Let h(k) = k mod 101, alpha be the load factor, and v be the maximum number of keys stored in a single slot. Which of the following is true?

Select one:
a. alpha > 1
b. alpha >v
c. None of the above
d. alpha =v
e. alpha < v

Ans: e. alpha < v

11. Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812, 1918, 1945.
1945 is stored in the slot ________ if linear probing policy is used and h(k) =5*x mod 8 is the auxiliary hash function.

Select one:
a. 0
b. 6
c. None of the above
d. 7
e. 5

Ans: d. 7

12. Keys "63, 73, 43, 98, 110" are stored in a direct address table.

"43"  will be stored in the slot ____________

Select one:
a. 43
b. 44
c. None of the above
d. 3
e. 0

Ans: a. 43

13. Let m is the size of the hash table and n is the number of elements in the hash table. Simple uniform hashing is impossible if

Select one:
a. n>m
b. n=2m
c. n<m
d. n=m
e. None of the above

Ans:  c. n<m

14. When using linear probing policy, the probability of an empty slot gets filled if it is preceded by i full slots.


Select one:
a. 1/m
b. (i+1)/m
c. None of the above
d. (i+1)/n
e. 1/n

Ans: b. (i+1)/m

15. Keys "63, 73, 43, 98, 110" are stored in a direct address table
What is the minimum size of the table?

Select one:
a. None of the above
b. 111
c. 109
d. 4
e. 5

Ans: b. 111

16. Which of the following input sequence stores the items { 1,2,3,4,5,6,7} in a size-balanced binary search tree (that is for every node v the number of nodes in the left subtree of v is same as the number of nodes in right subtree of v)

Select one:
a. 1,2,3,4,5,6,7
b. None of the above
c. 4,2,1,3,6,5,7
d. 4,3,1,2,7,5,6
e. 7,6,5,4,3,2,1

Ans: c. 4,2,1,3,6,5,7

17. Keys { 200,205,210,...,600} are stored in a chained hash table.

Suppose h(k) = k mod 100 is used, which slot will have maximum number of keys?

Select one:
a. 200
b. None of the above
c. 100
d. 99
e. 0

Ans: e. 0

18. Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812, 1918, 1945.
Find the the total number of key comparisons if linear probing policy is used and h(k) = 5*x mod 8 is the auxiliary hash function.


Select one:
a. 6
b. 9
c. None of the above
d. 7
e. 4


Ans: b. 9

19. Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812, 1918, 1945.
1812 is stored in the slot ___________ if double hashing policy is used with h_1(k) = 5*x mod 8 and h_2(x) = 1+ (k mod 7).


Select one:
a. 7
b. 4
c. 3
d. 1
e. None of the above

Ans: c. 3

20. Suppose a simple uniform hashing function is used with chaining. The expected number of key comparisons in successful search is at most __________


Select one:
a. None of the above
b. alpha
c. 1+ alpha/2 - alpha/(2n)
d. 1
e. 1+alpha

Ans: c. 1+ alpha/2 - alpha/(2n)