MO417 - Questão para a prova oral

Número: 070

Enunciado:
Sobre o problema de encontrar a árvore de pesquisa binária que minimiza o número esperado de comparações com chaves, dadas as probabilidades das chaves e dos intervalos entre elas, é CORRETO afirmar que:

1. É um problema que pode ser resolvido por programação dinâmica.
2. O tempo de execução para encontrar a árvore ótima é O(n lg n).
3. A solução sempre apresentará a menor altura global possível.
4. A solução terá no nó raiz a chave que tiver maior probabilidade.
5. NDA

Autor(a): Paulo Gurgel Pinheiro