108-2008

MO640 - Questão para a prova oral
Número: 108
Enunciado:
Das afirmações abaixo, quais são verdadeiras sobre o algoritmo para a construção de árvores PQ de Booth e Lueker [1976]:
I- O algoritmo possui duas passagens, a primeira para identificação dos nós a serem processados e a segunda para aplicação de reduções.
II- Todos filhos de nós Q tem ponteiros para os pais.
III- A complexidade linear é confirmada por uma análise amortizada.

1. I e II.
2. I e III.
3. II.
4. III.
5. NDA

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