jho

MO417 - Questão para a prova oral

Número: 

Enunciado: Sobre as representações para conjuntos disjuntos é correto afirmar que :

1. Na representação por listas ligadas é utilizada a heurística weighted-union onde a idéia é sempre concatenar a maior lista no final da menor.
2. Usando a representação por listas ligadas e a heurística weighted-union, uma sequência de m operações (MAKE-SET + UNION + FIND-SET) gasta tempo O(m + mlgm).
3. A representação por disjoint-set forest é uma melhoria assintótica em relação com a representação por listas ligadas, porque utiliza as heurísticas weighted-union e path compression.
4. A idéia da heurística path compression consiste em: ao tentar determinar o representante (raiz da árvore) de um nó fazemos com que todos os nós no caminho apontem para a raiz.
5. NDA.

Ideia original de: Jhon Anthony Campos Arteaga