085-2007

MO640 - Questão para a prova oral
Número: 085
Enunciado:
Dentre as operações a seguir, qual não está relacionada ao algoritmo de construção de árvores PQR em tempo quase linear, de Telles e Meidanis?

1. Encontrar o mínimo ancestral comum ("least common ancestor") de um determinado conjunto de folhas.
2. Colorir nós da árvore PQR em três cores: branco, preto e cinza.
3. Fazer com que a árvore PQR não possua nós cinzas.
4. Utilizar divisão e conquista para decompor o problema de construção da árvore PQR em dois subproblemas menores, os quais originam duas sub-árvores PQR que são transformadas em uma única árvore PQR.
5. NDA

Autor: Celmar Guimarães da Silva