116-2008

MO640 - Questão para a prova oral
Número: 116
Enunciado:
Sobre o artigo "Building PQR Trees in Almost-Linear Time" [Meidanis e Telles, 2007], qual(is) das afirmações abaixo é (são) verdadeiras.

I- O algoritmo apresentado é offline.

II- O algoritmo incia com uma árvore universal, na qual todas as folhas são filhas de um mesmo nó P.

III- Todos os nós brancos devem ser eliminados durante a execução do algoritmo.

IV- Os conjuntos de filhos dos nós Q e R são implementados como estruturas "union-find", o que garante complexidade de tempo quase linear ao algoritmo.

1. III, apenas.
2. II e IV.
3. II, e III.
4. I, II e IV.
5. NDA

Autor(a): Maria Angélica Lopes de Souza