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

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

 Question 1
How many properties will an equivalent relationship satisfy?
 A 1 B 2 C 3 D 4
Question 1 Explanation:
An equivalent relationship will satisfy three properties - reflexive, symmetric and transitive.

 Question 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
Question 2 Explanation:
A symmetric property in an equivalence relation is defined as x R y if and only y R x.

 Question 3
Electrical connectivity is an example of equivalence relation.
 A true B false
Question 3 Explanation:
Electrical connectivity is reflexive, symmetric and also transitive. Hence, electrical connectivity is an equivalence relation.

 Question 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)