car

MO417 - Questão para a prova oral

Número:

Enunciado: dado o seguente conjunto A = {x1, x2, x3, x4, x5, x6}, e os seguintes algoritmos:

MAKE-SET(x)
1   x.p = x
2   x.rank = 0

UNION(x, y)
1   LINK(FIND-SET(x), FIND-SET(y))
 
LINK(x, y)
1   if x.rank > y.rank
2       y.p = x
3   else x.p = y
4       if x.rank == y.rank
5           y.rank = y.rank + 1
 
FIND-SET(x)
1   if x ≠ x.p
2       x.p = FIND-SET(x.p)
3   return x.p

O valor rank de cada um dos elementos de A depois das seguintes operações (nessa mesma ordem):  MAKE-SET(xi) para i=1:6 ; UNION(x1, x5); UNION(x3, x4); UNION(x2, x6); UNION(x1, x2); UNION(x3, x1); é?

a) x1=1, x2=0, x3=1, x4=0, x5=2, x6=0
b) x1=0, x2=0, x3=0, x4=1, x5=1, x6=2
c) x1=0, x2=0, x3=0, x4=2, x5=1, x6=1
d) x1=1, x2=2, x3=1, x4=0, x5=0, x6=1
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales