# Quiz: Disjoint Sets

## Quiz: Disjoint Sets >> Data Structures

*Please Do Not Click On The Options.

*** If You Click Mistakenly Then Please Refresh The Page To Get The Right Answers.**

#### Quiz: Disjoint Sets

**1**. Consider the following program:

Assume that the disjoint sets data structure is implemented as an array $smallest[1…12]$: $smallest[i]$ is equal to the smallest element in the set containing $i$.

What is the output of the following program? As an answer, enter four integers separated by spaces.

**2**. Consider the program:

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic.

Compute the product of the heights of the resulting trees after executing the code. For example, for a forest consisting of four trees of height 1, 2, 3, 1 the answer would be 6. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

**3**. Consider the following program:

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic.

What is the number of trees in the forest and the maximum height of a tree in this forest after executing this code? (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

**4**. Consider the following program:

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic and with path compression heuristic.

Compute the maximum height of a tree in the resulting forest. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)