dam

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Suponha uma implementação de conjuntos disjuntos com o uso de florestas, que ofereça os seguintes comandos:

1. Make-Set(x): cria um conjunto cujo único elemento é x;

2. Find-Set(x): retorna o elemento representante do conjunto de x, com o uso da heurística de path compression;

3. Union(x, y): unifica os conjuntos de x e de y, com o uso da heurística de union by rank (seu código segue abaixo).

Union(x, y) // mesma implem. de "Intro. to Algorithms" (Cormen et al., 3a ed)

1. e1 = Find-Set(x);

2. e2 = Find-Set(y);

3. if e1.rank > e2.rank

4.      e2.pai = e1;

5. else

6.      e1.pai = e2;

7.      if e1.rank == e2.rank;

8.           e2.rank = e2.rank + 1;

Selecione a árvore resultante da seguinte sequência de comandos, onde cada nó é rotulado com seu elemento x, e seu valor de rank r (<x, r>):

01. Make-Set(a);

02. Make-Set(b);

03. Make-Set(c);

04. Make-Set(d);

05. Make-Set(e);

06. Make-Set(f);

07. Make-Set(g);

08. Union(b, a);

09. Union(e, d);

10. Union(d, f);

11. Union(d, a);

12. Union(g, c);

13. Union(f, g);

a.   b.

c.        d.

e. N.D.A

Ideia original de: Daniel Henriques Moreira