MO417 - Questão para a prova oral

Número: 113

Enunciado: Uma forma de representar conjuntos disjuntos é utilizar florestas onde os conjuntos são representados por árvores enraizadas, com cada nó contendo um elemento e cada árvore representando um conjunto. Além disso, cada nó da árvore aponta apenas para seu pai e o nó raiz da árvore contém o elemento representante e é seu próprio pai.

Considere os algoritmos abaixo utilizados em operações de conjuntos disjuntos representados por florestas de conjuntos disjuntos. O pai de um nó x em uma árvore é dado por p[x].

MAKE-SET(x)
1 p[x] ← x
2 posto[x] ← 0 		UNION(x, y)
1 x ← FIND-SET(x)
2 y ← FIND-SET(y)
3 if x ≠ y then
4     LINK(x,y) 		LINK(x, y)
1 if posto[x] > posto[y] then
2     p[y] ← x
3 else
4     p[x] ← y
5     if posto[x] = posto[y] then
6         posto[y] = posto[y] + 1 		FIND-SET(x)
1 if x ≠ p[x] then
2     p[x] ← FIND-SET(p[x])
3 return p[x]


Empregando o conceito florestas de conjuntos disjuntos, dados n=8 elementos distintos, quais dos algoritmos abaixo resulta em uma única árvore contendo os n elementos?

A

1 for i ← 1 to n do
2     MAKE-SET(xi)
3 for i ← 1 to n-1 by 2 do
4     UNION(xi, xi+1)
5 UNION(1, 3)
6 UNION(6, 8)
7 UNION(5, 8) 		B

1 for i ← 1 to n do
2     MAKE-SET(xi)
3 for i ← 1 to n-1 by 2 do
4     UNION(xi, xi+1)
5 UNION(8, 2)
6 UNION(6, 5)
7 UNION(3, 4) 		C

1 for i ← 1 to n do
2     MAKE-SET(xi)
3 for i ← 1 to n-1 by 2 do
4     UNION(xi, xi+1)
5 UNION(4, 6)
6 UNION(8, 2)
7 UNION(5, 2) 		D

1 for i ← 1 to n do
2     MAKE-SET(xi)
3 for i ← 1 to n-1 by 2 do
4     UNION(xi, xi+1)
5 UNION(1, 4)
6 UNION(5, 7)
7 UNION(2, 4) 		NDA


Autor(a): Maikon Cismoski dos Santos