Disjoint-Set Data Structure Multiple choice Questions and Answers (MCQs)
How many properties will an equivalent relationship satisfy?
Question 1 Explanation:
An equivalent relationship will satisfy three properties - reflexive, symmetric and transitive.
A relation R on a set S, defined as x R y if and only if y R x. This is an example of?
Question 2 Explanation:
A symmetric property in an equivalence relation is defined as x R y if and only y R x.
Electrical connectivity is an example of equivalence relation.
Question 3 Explanation:
Electrical connectivity is reflexive, symmetric and also transitive. Hence, electrical connectivity is an equivalence relation.
What is the worst case efficiency for a path compression algorithm?
O(N log N)
O(M log N)
Question 4 Explanation:
The worst case efficiency for a path compression algorithm is mathematically found to be O(M log N).
Does path compression algorithm work during?
Question 5 Explanation:
Path compression algorithm is performed during find operation and is independent of the strategy used to perform unions.
There are 5 questions to complete.