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

**1. 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

Explanation: For i>=1, Ackermann’s function is defined as A(1,i) = i+1. In text, this type grows faster, while the inverse grows slower.

**2. ___________ 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**

Explanation: Path compression is one of the earliest ways of self-adjustment, and it’s still used in critical strategies that rely on theoretical explanations.

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

Explanation: The depth of any tree is determined to be O if the Unions are performed by height (log N).

**4. When executing a sequence of Unions, a node of rank r must have at least 2 ^{r} descendants.**

**A) true**

B) false

Explanation: Each tree has at least 2r – 1 descendants, giving a total of 2r and establishing the lemma, according to the induction hypothesis.

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

A) N

B) N/2**C) N/2 ^{r}**

D) N

^{r}

Explanation: Each node of rank r is the root of at least 2r subtrees. As a result, there are only N/2r disjoint subtrees.

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

Explanation: The worst case running time of a union operation done by size and path compression is mathematically found to be O(M logN).

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

Explanation: One of the lemmas states that the ranks of the nodes on a path will increase monotonically from leaf to root in the Union/Find algorithm.

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

A) 1**B) 2**

C) 3

D) 4

Explanation: In order to solve a complex equivalence problem, two methods are used: executing the find instruction in worst-case time and executing the union instruction in worst-case time.

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

Explanation: In a dynamic equivalence problem, the total time spent for N-1 merges is calculated to be O. (N log N).

**10. 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

Explanation: The equivalence property is satisfied if the two towns are in the same country and have a two-way road link between them.

**11. How many properties will an equivalent relationship satisfy?**

A) 1

B) 2**C) 3**

D) 4

Explanation: The properties of an analogous relationship are reflexive, symmetric, and transitive.

**12. 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

Explanation: In an equivalence relation, a symmetric property is known as x R y if and only if y R x.

**13. Electrical connectivity is an example of equivalence relation.****A) true**

B) false

Explanation: Electrical connectivity is symmetric, reflexive, and transitive. As a result, electrical connectivity is a relationship of equivalence.

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

Explanation: Mathematically, the worst-case efficiency of a path compression algorithm is determined to be O. (M log N).

**15. Path Compression algorithm performs in which of the following operations?**

A) Create operation

B) Insert operation**C) Find operation**

D) Delete operation

Explanation: The path compression algorithm is run during the find process and is unaffected by the union strategy.

A data structure that stores a list of disjoint (non-overlapping) sets is known as a disjoint-set data structure, also known as a union–find data structure or merge–find set. It stores a partition of a set into disjoint subsets in the same way. It includes functions for creating new sets, combining sets (replacing them by their union), and locating a set’s representative member. The final operation helps you to quickly determine if two elements belong to the same or different sets.