Handbook-de-TI-Cesgranrio (6)

Text Material Preview

Handbook de Questões de TI Comentadas para Concursos Volume 02 � Edição 2
• veri�que qual é a primeira comparação do algoritmo, que pode resultar em �sim� ou
�não�. Nesse passo, é necessário saber quais são os índices que estão sendo comparados;
• a primeira comparação é colocada na raiz da árvore de decisão, incluindo os arcos �sim�
e �não�;
• repita os passos anteriores para cada nó da árvore. Em cada comparação, é necessário
saber quais são os índices que estão sendo comparados. Observe que sempre se deve
analisar os índices originais, ou seja, não devem ser consideradas as trocas de índices
ocorridas durante a execução do algoritmo.
Tendo em vista os conceitos apresentados, conclui-se que o algoritmo Heapsort pode ser
representado por uma árvore de decisão, já que é um dos algoritmos que realiza ordenação
por comparação. Portanto, essa alternativa está errada.
(B) CORRETA
Considerando a explicação apresentada acima, se torna fácil concluir que é essa a alter-
nativa correta.
(C) ERRADA
Seu desempenho no pior caso (igual ao do melhor ou médio caso) é O(n log n). Esse é
o melhor resultado dentre os algoritmos baseados em comparações. Esse conhecimento já
bastaria para concluir que essa alternativa está incorreta. As complexidades do algoritmo
Quicksort são O(nlogn) para o melhor caso e O(n2) para o pior caso. É sempre importante
ter em mente que quanto mais e�ciente for a escolha do pivot, mais e�ciente será o desem-
penho da ordenação do algoritmo Quicksort.
(D) ERRADA
No pior caso, a ordenação por inserção apresenta complexidade igual a O(n2), pois nesse
caso são necessárias n(n− 1)/2 ≈ (n2)/2 comparações. Esse cenário sempre ocorre quando
a sequência de entrada está ordenada na ordem inversa à desejada.
(E) ERRADA
Também chamado de Mergesort, o algoritmo de ordenação por intercalação, um algoritmo
recursivo, se utiliza da técnica �dividir para conquistar�. Sua idéia básica é que é mais fácil
criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele
divide a sequência original em pares de dados, as ordena, depois as agrupa em sequências
de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas
partes. Sua complexidade tanto para o pior quanto para o melhor caso é O(n log n). Seu
ponto fraco é a �baixa� e�ciência na utilização de memória, complexidade espacial O(n).
Contudo, existe uma variante desse algoritmo que realiza a ordenação no próprio vetor de
entrada, ou seja, complexidade espacial O(1), mas a sua implementação é extremamente
complicada.
Página 81 de 114
www.handbookdeti.com.br
www.handbookdeti.com.br