092-2005

MO640 - Questão para a prova oral
Número: 092
Enunciado:
De acordo com o artigo de Booth e Lueker sobre Árvores PQ (1976), é INCORRETO afirmar que:

1. Árvore PQ é uma estrutura de dados usada para representar as permutações de um conjunto U onde vários subconjuntos de U ocorrem consecutivamente.
2. São apresentados algoritmos para testar a planaridade de um grafo e a propriedade de “uns consecutivos” de uma matriz. Esses algoritmos utilizam árvore PQ e têm complexidade de tempo linear.
3. Em uma árvore PQ própria todos os nós “Q” têm pelo menos 3 filhos.
4. Uma matriz de “zeros e uns” tem a propriedade de “uns consecutivos” para colunas se suas colunas podem ser permutadas de forma que em cada linha todos os “uns” são consecutivos.
5. NDA

Autor(a): Renato Hirata