# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

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

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

How many properties will an equivalent relationship satisfy?

1 | |

2 | |

3 | |

4 |

Question 1 Explanation:

An equivalent relationship will satisfy three properties - reflexive, symmetric and transitive.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

A relation R on a set S, defined as x R y if and only if y R x. This is an example of?

reflexive relation | |

symmetric relation | |

transitive relation | |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Electrical connectivity is an example of equivalence relation.

true | |

false |

Question 3 Explanation:

Electrical connectivity is reflexive, symmetric and also transitive. Hence, electrical connectivity is an equivalence relation.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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

O(N) | |

O(log N) | |

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

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Does path compression algorithm work during?

Create operation | |

Insert operation | |

Find operation | |

Delete operation |

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.