Q.1 What is the primary purpose of the Disjoint Set (Union-Find) data structure?
To store elements in sorted order
To efficiently manage disjoint sets and perform union and find operations
To implement hash tables
To perform matrix multiplication efficiently
Explanation - Disjoint Set, or Union-Find, is used to track a set of elements partitioned into non-overlapping subsets. It supports two main operations efficiently: union (merging sets) and find (determining the set of an element).
Correct answer is: To efficiently manage disjoint sets and perform union and find operations
Q.2 Which technique is commonly used to optimize the 'find' operation in Union-Find?
Path Compression
Binary Search
Dynamic Programming
Breadth-First Search
Explanation - Path compression flattens the structure of the tree whenever find is called, making future find operations faster.
Correct answer is: Path Compression
Q.3 In Union-Find, which of the following optimizations improves the 'union' operation?
Union by Rank
Quick Sort
DFS Traversal
Memoization
Explanation - Union by rank attaches the smaller tree under the root of the larger tree to keep the tree shallow, optimizing find operations.
Correct answer is: Union by Rank
Q.4 After applying path compression in Union-Find, the trees representing sets become:
Binary Search Trees
Shallow trees with reduced height
Linked lists
Graphs with cycles
Explanation - Path compression flattens the tree structure, making subsequent find operations faster by reducing the path length from nodes to their root.
Correct answer is: Shallow trees with reduced height
Q.5 What is the worst-case time complexity of a naive Union-Find without optimizations?
O(1)
O(log n)
O(n)
O(n^2)
Explanation - Without optimizations like path compression or union by rank, the find operation may take linear time if the sets form a long chain.
Correct answer is: O(n)
Q.6 What is the amortized time complexity of find and union operations using both path compression and union by rank?
O(1)
O(log n)
O(α(n))
O(n)
Explanation - Using both optimizations, the operations have nearly constant time, bounded by the inverse Ackermann function α(n), which grows extremely slowly.
Correct answer is: O(α(n))
Q.7 Which of the following problems is efficiently solved using Disjoint Set data structures?
Minimum Spanning Tree (Kruskal's Algorithm)
Matrix Multiplication
Binary Search
Topological Sorting
Explanation - Disjoint Set is used in Kruskal's Algorithm to detect cycles efficiently while constructing a Minimum Spanning Tree.
Correct answer is: Minimum Spanning Tree (Kruskal's Algorithm)
Q.8 In a Union-Find structure, if two nodes belong to the same set, what will the find operation return for both?
Different roots
The same root
Null
The node itself
Explanation - The find operation returns the representative (root) of the set, which will be the same for all elements in the same set.
Correct answer is: The same root
Q.9 Which data structure is typically used to implement Union-Find?
Arrays
Linked List
Binary Tree
Stack
Explanation - Union-Find is often implemented using arrays where each element stores a reference to its parent, enabling efficient find and union operations.
Correct answer is: Arrays
Q.10 What is the main disadvantage of a naive Union-Find implementation without any optimization?
High memory usage
Slow find operations due to tall trees
Cannot perform union operations
Does not support multiple sets
Explanation - Without path compression or union by rank, trees can become very tall, making find operations inefficient.
Correct answer is: Slow find operations due to tall trees
Q.11 Which scenario will most likely benefit from Union-Find?
Tracking connected components in a dynamic graph
Sorting an array
Searching in a sorted array
Calculating Fibonacci numbers
Explanation - Union-Find efficiently tracks connected components when edges are added incrementally.
Correct answer is: Tracking connected components in a dynamic graph
Q.12 If each set is initially a singleton, what is the first step in union operation?
Merge the sets
Find the roots of each set
Delete one element
Sort the elements
Explanation - To union two sets, first determine their roots using find, then merge based on rank or size.
Correct answer is: Find the roots of each set
Q.13 What does the term 'disjoint' in Disjoint Set indicate?
Sets are overlapping
Sets do not intersect
Sets are sorted
Sets are cyclic
Explanation - Disjoint sets are non-overlapping sets where no element is shared between two sets.
Correct answer is: Sets do not intersect
Q.14 Which function is responsible for merging two sets in Union-Find?
find()
union()
insert()
mergeSort()
Explanation - The union() operation merges two disjoint sets into a single set, updating the root structure accordingly.
Correct answer is: union()
Q.15 Union by size attaches the smaller tree under the larger tree. This is an alternative to:
Path Compression
Union by Rank
DFS
Breadth-First Search
Explanation - Union by size is a variant of union by rank where trees are merged based on the number of nodes rather than height.
Correct answer is: Union by Rank
Q.16 Which of the following is true when using both union by rank and path compression?
The tree height is always 1
Find and union operations are very efficient
Union operation becomes O(n)
Memory usage increases exponentially
Explanation - Combining these optimizations ensures nearly constant time operations for large datasets.
Correct answer is: Find and union operations are very efficient
Q.17 What will be the result of repeatedly calling find() on all elements in a Union-Find with path compression?
Trees become taller
All elements point directly to the root
Elements become disconnected
Union operations fail
Explanation - Path compression updates parent pointers during find so all nodes point to the root, flattening the tree.
Correct answer is: All elements point directly to the root
Q.18 If a Union-Find structure has n elements, what is the maximum number of disjoint sets it can have?
n
n/2
log n
1
Explanation - Initially, each element can be in its own singleton set, so there can be n disjoint sets.
Correct answer is: n
Q.19 Which of the following is NOT a typical operation of Disjoint Set?
Find
Union
Delete
MakeSet
Explanation - Disjoint Set typically supports makeSet, union, and find. Deletion is not standard.
Correct answer is: Delete
Q.20 When using union by rank, what rank represents?
The number of children of a node
An upper bound on the height of the tree
The number of elements in a set
The index of the node
Explanation - Rank is used to keep the tree shallow by representing the approximate height, helping efficient union operations.
Correct answer is: An upper bound on the height of the tree
Q.21 Disjoint Set data structures are particularly useful in algorithms that deal with:
Graphs and connectivity
Sorting arrays
String matching
Dynamic programming
Explanation - Disjoint Set efficiently handles connectivity queries in graphs, such as connected components or cycle detection.
Correct answer is: Graphs and connectivity
Q.22 Which algorithm relies heavily on Disjoint Set to detect cycles in a graph?
Kruskal's Algorithm
Prim's Algorithm
Dijkstra's Algorithm
Bellman-Ford Algorithm
Explanation - Kruskal's Algorithm uses Disjoint Set to efficiently detect cycles while adding edges to the Minimum Spanning Tree.
Correct answer is: Kruskal's Algorithm
Q.23 In Union-Find, what does makeSet(x) do?
Creates a new singleton set containing x
Merges two sets containing x
Deletes element x
Finds the set containing x
Explanation - makeSet initializes a set containing only element x, which can later be merged with others using union.
Correct answer is: Creates a new singleton set containing x
Q.24 Which property of Disjoint Set makes it suitable for dynamic connectivity problems?
Efficient union and find operations
Sorting capability
Random access
Fast deletion
Explanation - The efficiency of union and find allows Disjoint Set to quickly answer connectivity queries as sets are merged.
Correct answer is: Efficient union and find operations
Q.25 Union-Find with path compression and union by rank is almost equivalent to which time complexity for practical purposes?
O(n)
O(log n)
O(1)
O(n log n)
Explanation - Although the theoretical bound is O(α(n)), the inverse Ackermann function α(n) is extremely slow-growing, making it effectively constant for all practical input sizes.
Correct answer is: O(1)