Disjoint-Set Data Structure Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Disjoint-Set Data Structure”.

1. How many properties will an equivalent relationship satisfy?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation: An equivalent relationship will satisfy three properties – reflexive, symmetric and transitive.
advertisement

2. A relation R on a set S, defined as x R y if and only if y R x. This is an example of?
a) reflexive relation
b) symmetric relation
c) transitive relation
d) invalid relation
View Answer

Answer: b
Explanation: A symmetric property in an equivalence relation is defined as x R y if and only y R x.

3. Electrical connectivity is an example of equivalence relation.
a) true
b) false
View Answer

Answer: a
Explanation: Electrical connectivity is reflexive, symmetric and also transitive. Hence, electrical connectivity is an equivalence relation.
advertisement
advertisement

4. 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)
View Answer

Answer: d
Explanation: The worst case efficiency for a path compression algorithm is mathematically found to be O(M log N).

5. Path Compression algorithm performs in which of the following operations?
a) Create operation
b) Insert operation
c) Find operation
d) Delete operation
View Answer

Answer: c
Explanation: Path compression algorithm is performed during find operation and is independent of the strategy used to perform unions.
advertisement

6. 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
View Answer

Answer: a
Explanation: The Ackermann’s function is defined as A(1,i) = i+1 for i>=1. This form in text grows faster and the inverse is slower.

7. ___________ 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
View Answer

Answer: d
Explanation: Path compression is one of the earliest forms of self-adjustment used in extremely important strategies using theoretical explanations.
advertisement

8. 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)
View Answer

Answer: b
Explanation: If the Unions are performed by height, the depth of any tree is calculated to be O(log N).

9. When executing a sequence of Unions, a node of rank r must have at least 2r descendants.
a) true
b) false
View Answer

Answer: a
Explanation: By the induction hypothesis, each tree has at least 2r – 1 descendants, giving a total of 2r and establishing the lemma.
advertisement

10. What is the value for the number of nodes of rank r?
a) N
b) N/2
c) N/2r
d) Nr
View Answer

Answer: c
Explanation: Each node of a rank r is the root of a subtree of at least 2r. Therefore, there are at most N/2r disjoint subtrees.

11. 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)
View Answer

Answer: d
Explanation: The worst case running time of a union operation done by size and path compression is mathematically found to be O(M logN).

12. 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
View Answer

Answer: a
Explanation: One of the lemmas state that, in the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from leaf to root.

13. How many strategies are followed to solve a dynamic equivalence problem?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Explanation: There are two strategies involved to solve a dynamic equivalence problem- executing find instruction in worst-case time and executing union instruction in worst-case time.

14. 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)
View Answer

Answer: c
Explanation: The total time spent for N-1 merges in a dynamic equivalence problem is mathematically found to be O(N log N).

15. What is the condition for an equivalence relation if two cities are related within a country?
a) the two cities should have a one-way connection
b) the two cities should have a two-way connection
c) the two cities should be in different countries
d) no equivalence relation will exist between two cities
View Answer

Answer: b
Explanation: If the two towns are in the same country and have a two-way road connection between them, it satisfies equivalence property.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter