Disjoint-Set Data Structure Quiz Online Practice Test

1. An equivalence relation satisfies how many properties?

2. In a relation R on set S, where x R y if and only if y R x, what type of relation is this?

Reflexive

Symmetric

Transitive

Invalid

3. Electrical connectivity is an example of an equivalence relation.

True

False

Partially true

Depends on context

4. The worst-case efficiency of a path compression algorithm is:

O(N)

O(log N)

O(N log N)

O(M log N)

5. In which of these operations does the Path Compression algorithm operate?

Create

Insert

Find

Delete

6. How is Ackermann’s function defined?

A(1,i) = i+1 for i ≥ 1

A(i,j) = i+j for i ≥ j

A(i,j) = i+j for i = j

A(1,i) = i+1 for i < 1

7. Which of the following is an early self-adjustment technique utilized in splay trees and skew heaps?

Union by rank

Equivalence function

Dynamic function

Path compression

8. If a tree performs union operations based on height, what is its depth?

O(N)

O(log N)

O(N log N)

O(M log N)

9. How many nodes are there with a rank of r in a tree?

N/2

N/2r

10. What is the worst-case time complexity for performing unions with both size and path compression optimizations?

O(N)

O(log N)

O(N log N)

O(M log N)

11. In the Union/Find algorithm, how do the ranks of nodes change along a path?

From leaf to root

From root to node

From root to leaf

From left subtree to right subtree

12. How many approaches are used to address the dynamic equivalence problem?

13. What is the overall time complexity for performing N-1 merge operations in a dynamic equivalence problem?

O(N)

O(log N)

O(N log N)

O(M log N)

14. Under what condition do two cities within the same country form an equivalence relation?

The cities must have a one-way connection

The cities must have a two-way connection

The cities must be located in different countries

No equivalence relation exists between the cities

Test Name:	Disjoint-Set Data Structure Quiz
Subject Category:	Computer Science
Test Type:	Multiple Choice Questions
Total Score / Questions:	14 / 14
Time Allowed:	10 Min
Who Should Practice this Test:	Students, job seekers, or professionals preparing for competitive exams and interviews.

Disjoint-Set Data Structure MCQ Quiz Online Practice Test