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

Uncategorized

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 2r 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/2r
D) Nr

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.

Leave a Reply

Your email address will not be published. Required fields are marked *