MO417 - Questão para a prova oral

Número: 2003-134

Enunciado: Considere uma estrutura que representa conjuntos disjuntos através de árvores. Seja A uma árvore que implementa esta estrutura e um nó x de A diferente da raiz. Imediatamente após a execução de uma operação FIND-SET(x) (busca para encontrar o representante do conjunto a que pertence x), e considerando que esta operação realiza a heurística de compressão de caminhos, é correto afirmar que

A) Todos os nós que são filhos de x na árvore antes deste FIND-SET passarão a apontar diretamente para o nó raiz de A.

B) Se x é um nó que possui filhos antes do FIND-SET, ele deixará de tê-los, pois passsará a ser um nó folha.

C) Se antes do FIND-SET o elemento p é pai de x e p não é a raiz de A, então os filhos de x passam a ser filhos de p.

D) Se antes do FIND-SET o elemento p é pai de x e p não é a raiz de A, então x deixará de ser filho de p.

E) NDA

Ideia original de: André Santanchè