eri

MO417 - Questão para a prova oral

Número:

Enunciado : Considere a representação de conjuntos disjuntos por listas ligadas abaixo e a definição de suas operações MAKE_SET, UNION e FIND_SET definidas a seguir.

• Inicio: ponteiro para o objeto inicial da lista;
• Fim: ponteiro para o objeto final da lista;
• Cada objeto da lista contém:
• Um elemento de conjunto;
• Um ponteiro para o objeto contendo o próximo elemento do conjunto.
• Este ponteiro do último objeto da lista apontará para NIL.

• MAKE_SET(x): cria um novo conjunto cujo único elemento (e representante do conjunto) é x;
• UNION(x,y): une os conjuntos que contêm x e y em um novo conjunto que é a união desses dois conjuntos. O representante do conjunto resultante é o representante do conjunto de y.
• FIND_SET(x): retorna um ponteiro para o representante que contêm x.

Nesse contexto, qual o tempo de execução no pior caso dos algoritmos para MAKE_SET, FIND_SET e UNION, respectivamente.

a)      Θ(1), Θ(1), Θ(n).

b)     Θ(1), Θ(n), Θ(n).

c)      Θ(n), Θ(1), Θ(n).

d)     Com os parâmetros definidos nas funções, é impossível fazer os três algoritmos da forma como foram definidos.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato