MO640 - Questão para a prova oral

Número: 112

Sobre o texto "On the consecutive ones property", de Meidanis, Porto e Telles, 1998, e o algoritmo de montagem de árvores PQR proposto, considere as seguintes afirmações:

I - o algoritmo é um método ONLINE.
II - o algoritmo tem complexidade de tempo quadrática.
III - o algoritmo sempre consegue montar uma árvore PQR dado um conjunto universo e uma coleção (subconjuntos do universo).

São corretas as afirmações:

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

Autor(a): Gustavo Waku