MO417 - Questão para a prova oral

Número: 2010-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 r[x] ← 0

UNION(x, y) 1 x ← FIND(x) 2 y ← FIND(y) 3 if x ≠ y then 4     LINK(x,y)

LINK(x, y) 1 if r[x] > r[y] then 2     p[y] ← x 3 else 4     p[x] ← y 5     if r[x] = r[y] then 6         r[y] = r[y] + 1

FIND(x) 1 if x ≠ p[x] then 2     p[x] ← FIND(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/2 do 4     UNION(x2i-1,x2i) 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/2 do 4     UNION(x2i-1,x2i) 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/2 do 4     UNION(x2i-1,x2i) 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/2 do 4     UNION(x2i-1,x2i) 5 UNION(1, 4) 6 UNION(5, 7) 7 UNION(2, 4)

E NDA

Ideia original de: Maikon Cismoski dos Santos