MO417 - Questão para a prova oral

Número: 2009-114

Enunciado: Sobre florestas de conjuntos disjuntos com heurísticas de união por posto e compressão de caminho é correto afirmar que:

1. A compressão de caminhos não altera o posto dos nós.
2. Na operação de união de conjuntos as raízes se conectam, tornando-se o pai a raiz da árvore de maior altura.
3. Após a operação de encontrar o representante do conjunto de um dado elemento, as folhas ficam todas no mesmo nível.
4. O tempo de execução da operação de criação de um conjunto com um elemento é ϴ(α(n)), onde α(n) é a inversa da função de Ackerman e n é o número total de elementos na estrutura.
5. NDA

Ideia original de: Milton Aparecido Soares Junior