101-2005

MO640 - Questão para a prova oral
Número: 101
Enunciado:
A repeito do algoritmo quase linear de construção de uma árvore PQR (Meidanis e Telles, 2004), assinale a alternativa INCORRETA:

1. É baseado na inserção de uma restrição por vez, utilizando como árvore inicial um único nó P que tem como filhos todos os elementos de U
2. Ao inserir uma restrição, encontra o nó que seja o ancestral comum mais próximo de todas as folhas envolvidas na restrição, e este nó é chamado de LCA
3. As folhas envolvidas pela restrição sempre são coloridas como pretas, e os nós intermediários da árvore são coloridos como cinzas caso sejam ortogonais à restrição em questão
4. Após a inserção de uma restrição, os nós que foram coloridos com a cor cinza devem ser eliminados por meio de uma reestruturação da árvore
5. NDA

Autor(a): Leonardo Elias Mariote