Questão para a Prova Oral 070

Semana 5: 17 a 21/03/03
Assunto: Ordenação em Tempo Linear e Estatísticas de Ordem


Quanto à relação entre algoritmos de ordenação por comparação e o modelo de árovres de decisão apresentado no livro, assinale a alternativa correta:

A) Para que a ordenação por comparação seja correta, é necessário que cada uma das n! permutações apareça como uma das folhas da árvores, e que cada uma dessas folhas seja acessível a partir da raiz por um caminho correspondente a uma execução real da ordenação

B) O comprimento do caminho mais curto da raiz até qualquer de suas folhas acessíveis representa o número de comparações do pior caso

C) A altura da árvore é Theta(lg n)

D) A árvore de decisão é n-ária, onde n é o tamanho da entrada do algoritmo (número de elementos a serem ordenados)

E) N.D.A.

Autor: Augusto Jun Devegili
RA: 25620