MO417 - Questão para a prova oral

Número: 2013-056

Enunciado: Dado o 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))
FIND-SET(x) 1   if x ≠ x.p 2       x.p = FIND-SET(x.p) 3   return x.p		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

O valor rank de cada um dos elementos de A depois das seguintes operações (nesta 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