MO417 - Questão para a prova oral

Número: 2009-110

Enunciado:

Dentre as operações que se pode realizar com conjuntos disjuntos, está a operação de UNION (x,y), em que se une o conjunto que contém x com o conjunto que contém y, e a operação FIND-SET(x), que retorna um ponteiro para o representante do conjunto que contém x. Utilizando a heurística de união por posto e a heurística de compressão de caminho, foram obtidas as duas árvores abaixo, que representam dois conjuntos disjuntos. A árvore da esquerda representa o conjunto disjunto {a, b, c, d} e a árvore da direita o conjunto disjunto {e, f}. A partir deste estado, foram realizadas as seguintes operações em sequência: UNION (d, f); FIND-SET (f); Assinale a alternativa que contém a resposta correta às seguintes duas perguntas: I. Qual a altura da árvore resultante após todas as operações? II. A operação FIND-SET( f ) retornou um ponteiro para qual nó?

1. I = 1, II = a
2. I = 1, II = e
3. I = 2, II = a
4. I = 2, II = e
5. NDA

Ideia original de: Paulo Gurgel Pinheiro