Q. In a Disjoint Set Union, what does the 'Union by Rank' technique help to achieve?
A.
Faster sorting of elements
B.
Reduced height of trees
C.
Increased memory usage
D.
Faster searching in arrays
Show solution
Solution
The 'Union by Rank' technique helps to achieve reduced height of trees, which in turn optimizes the 'Find' operation.
Correct Answer:
B
— Reduced height of trees
Learn More →
Q. In a Disjoint Set Union, what is the effect of union by rank?
A.
It increases the size of the set
B.
It keeps the tree flat by attaching smaller trees under larger trees
C.
It merges sets randomly
D.
It has no effect on the structure
Show solution
Solution
Union by rank keeps the tree flat by attaching smaller trees under larger trees, optimizing the union operation.
Correct Answer:
B
— It keeps the tree flat by attaching smaller trees under larger trees
Learn More →
Q. In a Disjoint Set Union, what is the role of the 'rank' of a set?
A.
To determine the size of the set
B.
To optimize the union operation
C.
To track the number of elements
D.
To store the parent node
Show solution
Solution
The 'rank' of a set is used to optimize the union operation by ensuring that the smaller tree is always added under the root of the larger tree.
Correct Answer:
B
— To optimize the union operation
Learn More →
Q. What is the initial state of each element in a Disjoint Set Union when it is first created?
A.
Each element is its own set
B.
All elements are in a single set
C.
Elements are sorted
D.
Elements are in random sets
Show solution
Solution
When first created, each element in a Disjoint Set Union is its own set, meaning they are all disjoint.
Correct Answer:
A
— Each element is its own set
Learn More →
Q. What is the time complexity of the 'Find' operation with path compression and union by rank?
A.
O(n)
B.
O(log n)
C.
O(α(n))
D.
O(1)
Show solution
Solution
The time complexity of the 'Find' operation with path compression and union by rank is O(α(n)), where α is the inverse Ackermann function.
Correct Answer:
C
— O(α(n))
Learn More →
Q. What is the time complexity of the 'Find' operation with path compression in Disjoint Set Union?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(α(n))
Show solution
Solution
The time complexity of the 'Find' operation with path compression in Disjoint Set Union is O(α(n)), where α is the inverse Ackermann function.
Correct Answer:
D
— O(α(n))
Learn More →
Q. What is the worst-case time complexity for a sequence of m union and find operations in Disjoint Set Union with path compression and union by rank?
A.
O(m)
B.
O(m log n)
C.
O(m α(n))
D.
O(n)
Show solution
Solution
The worst-case time complexity for a sequence of m union and find operations in Disjoint Set Union with path compression and union by rank is O(m α(n)).
Correct Answer:
C
— O(m α(n))
Learn More →
Q. Which of the following is NOT a common application of Disjoint Set Union?
A.
Kruskal's algorithm for minimum spanning tree
B.
Network connectivity
C.
Dynamic connectivity queries
D.
Binary search tree operations
Show solution
Solution
Binary search tree operations are not a common application of Disjoint Set Union; it is primarily used for network connectivity and algorithms like Kruskal's.
Correct Answer:
D
— Binary search tree operations
Learn More →
Showing 1 to 8 of 8 (1 Pages)
