Engineering Questions with Answers - Multiple Choice Questions

# Disjoint-Set Data Structure Multiple Choice MCQ

1 - Question

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

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

2 - Question

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

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

3 - Question

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

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

4 - Question

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)

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

5 - Question

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

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

6 - Question

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

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 - Question

___________ 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

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

8 - Question

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)

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

9 - Question

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

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

10 - Question

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

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 - Question

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)

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 - Question

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

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 - Question

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

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 - Question

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)

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

15 - Question

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