109-2008

MO640 - Questão para a prova oral
Número: 109
Sobre o texto de K. S. Booth and G. S. Lueker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", considere as seguintes afirmações:

I - A implementação que manipula as árvores PQ discutida no artigo basicamente se divide em dois algoritmos, BUBBLE e REDUCE, onde cada um destes percorre a árvore PQ duas vezes.
II - O algoritmo REDUCE realiza a redução em uma subárvore podada de T em relação a S. ( T = árvore PQ original, S = subconjunto de U, U = conjunto universo).
III - O número de nós com ponteiros para os pais é reduzido, porque o esforço para manutenção dos ponteiros corretos geraria um trabalho pribitivo caso um nó interno que tivesse um grande número de filhos vazios fosse apagado.
IV - Se a árvore só possuir nós tipo P, em cada nó, o número de FILHOS pertinentes será sempre igual ao número de FOLHAS pertinentes.

São corretas as afirmações:

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

Autor(a): Gustavo Waku