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?
- Encontrar o mínimo ancestral comum ("least common ancestor") de um determinado conjunto de folhas.
- Colorir nós da árvore PQR em três cores: branco, preto e cinza.
- Fazer com que a árvore PQR não possua nós cinzas.
- 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.
- NDA
Autor: Celmar Guimarães da Silva