Disjoint-Set Data Structure Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Disjoint-Set Data Structure”.

1. How many properties will an equivalent relationship satisfy?
a) 1
b) 2
c) 3
d) 4
View Answer

2. A relation R on a set S, defined as x R y if and only if y R x. This is an example of?
a) reflexive relation
b) symmetric relation
c) transitive relation
d) invalid relation
View Answer

3. Electrical connectivity is an example of equivalence relation.
a) true
b) false
View Answer

4. 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)
View Answer

5. Path Compression algorithm performs in which of the following operations?
a) Create operation
b) Insert operation
c) Find operation
d) Delete operation
View Answer

6. 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
View Answer

7. ___________ 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
View Answer

8. 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)
View Answer

9. When executing a sequence of Unions, a node of rank r must have at least 2^r descendants.
a) true
b) false
View Answer

10. What is the value for the number of nodes of rank r?
a) N
b) N/2
c) N/2^r
d) N^r
View Answer

11. What is the worst-case running time of unions done by size and path compression?
a) O(N)
b) O(logN)
c) O(N logN)
d) O(M logN)
View Answer

12. 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
View Answer

13. How many strategies are followed to solve a dynamic equivalence problem?
a) 1
b) 2
c) 3
d) 4
View Answer

14. 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)
View Answer

15. 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
View Answer

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.