MO417 - Questão para a prova oral

Número: 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

Autor(a): Paulo Gurgel Pinheiro