We have the best collection of Disjoint-Set Data Structure MCQs and answer with FREE PDF. These Disjoint-Set Data Structure MCQs will help you to prepare for any competitive exams like: BCA, MCA, GATE, GRE, IES, PSC, UGC NET, DOEACC Exams at all levels – you just have to practice regularly.

## Disjoint-Set Data Structure MCQs

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

**Answer: **O(N log N)

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

**Answer: **O(M log N)

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

a) Create operation

b) Insert operation

c) Find operation

d) Delete operation

**Answer: **Find operation

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

**Answer: **A(1,i) = i+1 for i>=1

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

**Answer: **Path compression

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

**Answer: **O(log N)

**7. When executing a sequence of Unions, a node of rank r must have at least 2r descendants.**

a) true

b) false

**Answer: **true

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

a) N

b) N/2

c) N/2r

d) Nr

**Answer: **N/2r

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

**Answer: **O(M logN)

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

**Answer: **leaf to root