【PTA】【数据结构与算法】并查集_the array representation of a disjoint set contain

选择题

1.The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are:

2.The array representation of a disjoint set is given by { 4, 6, 5, 2, -3, -4, 3 }. If the elements are numbered from 1 to 7, the resulting array after invoking Union(Find(7),Find(1)) with union-by-size and path-compression is:

3.The array representation of the disjoint sets is given by {2, –4, 2, 3, -3, 5, 6, 9, -2}. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(6)) with union-by-size, which elements will be changed in the resulting array?

4.In a disjoint set problem, given a set of m elements S = { 1, 2, 3, …, m } and n ( 0<n<m ) distinct relations, the set S must have __ equivalence classes.

5.已知不相交集合用数组表示为{ 4, 6, 5, 2, -3, -4, 3 }。若集合元素从1到7编号，则调用Union(Find(7),Find(1))（按规模求并，并且带路径压缩）后的结果数组为：

6.若并查集用树表示，其中有n个结点，查找一个元素所属集合的算法的时间复杂度为____。

7.In a disjoint set problem, given a set of m elements S = { 1, 2, 3, …, m } and n ( 0<n<m ) distinct relations, the set S must have __ equivalence classes.

填空题

1.本题要求给出下列并查集操作执行后，集合数组内存储的结果。

union( find(4), find(6) )
union( find(2), find(7) )
union( find(0), find(4) )
union( find(7), find(6) )
union( find(7), find(1) )
1
2
3
4
5

注意：这里假设按规模求并（若两集合规模相等，则把第1个集合的根结点作为结果的根结点），并且用带路径压缩的查找。对所有的0≤i≤7，S[i]被初始化为−1。

程序填空题

1.请填空完成下列代码，功能是实现并查集中的“查”，并且带路径压缩。

SetType Find ( ElementType X, DisjSet S )
{   
   ElementType root, trail, lead;

   for ( root = X; S[root] > 0; root = S[root]) ;  
   for ( trail = X; trail != root; trail = lead ) {
      lead = S[trail] ;   
      S[trail] = root;   
   } 
   return root;
}
1
2
3
4
5
6
7
8
9
10
11