Q. If you have n elements and perform m union operations, what is the amortized time complexity of each operation in a Disjoint Set Union with path compression and union by rank?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(α(n))
Solution
The amortized time complexity of each operation in a Disjoint Set Union with path compression and union by rank is O(α(n)), where α is the inverse Ackermann function.
Q. In a Disjoint Set Union, what is the purpose of union by rank?
A.
To keep track of the number of elements in each set
B.
To minimize the height of the trees representing sets
C.
To ensure all elements are unique
D.
To sort the elements in each set
Solution
The purpose of union by rank in Disjoint Set Union is to minimize the height of the trees representing sets, which helps in optimizing the 'Find' operation.
Correct Answer:
B
— To minimize the height of the trees representing sets
Q. What is the main advantage of using path compression in the 'Find' operation?
A.
It increases the size of the data structure
B.
It reduces the time complexity of future operations
C.
It makes the data structure more complex
D.
It allows for multiple unions at once
Solution
The main advantage of using path compression in the 'Find' operation is that it reduces the time complexity of future operations by flattening the structure of the tree.
Correct Answer:
B
— It reduces the time complexity of future operations
Q. Which of the following techniques can be used to optimize the Union operation in Disjoint Set Union?
A.
Path compression
B.
Binary search
C.
Heapification
D.
Graph traversal
Solution
Path compression is a technique used to optimize the Union operation in Disjoint Set Union by flattening the structure of the tree whenever 'Find' is called.
