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

Disjoint-Set Data Structure MCQs PDF Download

Categories: Trees