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