Disjoint Set and Bin Data Structure MCQs

Q1. What is the worst case efficiency for a path compression algorithm?.

A. O(N).

B. O(log N).

C. O(N log N).

D. O(M log N).

Q2. Does path compression algorithm work during?.

A. Create operation.

B. Insert operation.

C. Find operation.

D. Delete operation.

Q3. What is the definition for Ackermann's function?.

A. A(1,i) = i+1 for i>=1.

B. A(i,j) = i+j for i>=j.

C. A(i,j) = i+j for i = j.

D. A(1,i) = i+1 for i<1.

Answer= A(1,i) = i+1 for i>=1

Q4. ___________ is one of the earliest forms of a self-adjustment strategy used in splay trees, skew heaps..

A. Union by rank.

B. Equivalence function.

C. Dynamic function.

D. Path compression.

Q5. What is the depth of any tree if the union operation is performed by height?.

A. O(N).

B. O(log N).

C. O(N log N).

D. O(M log N).

Q6. When executing a sequence of Unions, a node of rank r must have at least 2r descendants..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q7. What is the value for the number of nodes of rank r?.

A. N.

B. N/2.

C. N/2r.

D. Nr.

Q8. What is the worst-case running time of unions done by size and path compression?.

A. O(N).

B. O(log * N).

C. O(N log N).

D. O(M log* N).

Q9. In the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from?.

A. leaf to root.

B. root to node.

C. root to leaf.

D. left subtree to right subtree.

Q10. How many strategies are followed to solve a dynamic equivalence problem?.

A. 1.

B. 2.

C. 3.

D. 4.

Q11. What is the total time spent for N-1 merges in a dynamic equivalence problem?.

A. O(N).

B. O(log N).

C. O(N log N).

D. O(M log N).

Q12. What is the condition for an equivalence relation if two cities are related within a country?.

A. the two cities should have a one-way connection.

B. the two cities should have a two-way connection.

C. the two cities should be in different countries.

D. no equivalence relation will exist between two cities.

Answer= the two cities should have a two-way connection

Q13. What is the use of the bin data structure?.

A. to have efficient insertion.

B. to have efficient deletion.

C. to have efficient region query.

D. to have efficient traversal.

Answer= to have efficient region query

Q14. Bin is an example of a range query data structure..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q15. What is the worst case time complexity of query operation(n is the no. of candidates)?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q16. What is the worst case time complexity of delete operation(n is the no. of candidates)?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q17. What is the worst case time complexity of insertion operation(n =no. of candidates)?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q18. What is computational geometry?.

A. study of geometry using a computer.

B. study of geometry.

C. study of algorithms.

D. study of algorithms related to geometry.

Answer= study of algorithms related to geometry

Q19. What will be the time complexity of query operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (k = number of bins query rectangle intersects).

A. O(1).

B. O(k).

C. O(k2).

D. O(log k).

Q20. What will be the time complexity of delete operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects).

A. O(1).

B. O(m).

C. O(m2).

D. O(log m).

Q21. What will be the time complexity of insertion operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects).

A. O(1).

B. O(m).

C. O(m2).

D. O(log m).

Q22. Efficiency of bin depends upon ___________.

A. size of query and candidates.

B. location of query and candidates.

C. location and size of query and candidates.

D. depends on the input.

Answer= location and size of query and candidates

Q23. Bigger the query rectangle the better is the query efficiency..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q24. In what time can a 2-d tree be constructed?.

A. O(N).

B. O(N log N).

C. O(N2).

D. O(M log N).

Q25. Insertion into a 2-d tree is a trivial extension of insertion into a binary search tree..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.