Questão de Algoritmos e Estrutura de Dados — Algoritmos — UFLA 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq404555
Banca
UFLA
Órgão
UFLA
Ano
2018
Nível
Superior
Cargo
Analista de Tecnologia da Informação
Analise as proposições abaixo sobre algoritmos e estrutura de dados:I. Os métodos de ordenação por inserção e bolha possuem complexidade O(n² ) em relação ao número de comparações.II. Embora O(n² ), o método de ordenação por inserção possui complexidade Ω(n) em relação ao número de comparações.III. O método de ordenação por inserção, assim como o Quicksort, é estável.IV. O método de ordenação Quicksort tem complexidade O(n² ) em seu pior caso.Assinale a alternativa CORRETA:
ASomente as proposições I e III estão corretas.
BSomente as proposições I e IV estão corretas.
CSomente as proposições II e III estão corretas.
DSomente as proposições I, II e IV estão corretas.
Revelar gabarito e comentário▾
GabaritoD — Somente as proposições I, II e IV estão corretas.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Análise das proposições sobre algoritmos de ordenação
Gabarito: letra D (proposições I, II e IV corretas). A questão cobra conhecimento sobre complexidade de algoritmos de ordenação por comparação e estabilidade. Insertion sort e bubble sort são O(n²) no pior caso; insertion sort possui melhor caso linear Ω(n); quicksort é instável e tem pior caso O(n²).
Proposição
Afirmação
Complexidade/Estabilidade
Correção
Motivo
I
Insertion Sort e Bubble Sort são O(n²) em comparações
O(n²) pior/médio caso
✅ Correta
Ambos têm complexidade quadrática no pior caso
II
Insertion Sort tem Ω(n) em comparações
Ω(n) melhor caso
✅ Correta
Vetor ordenado requer apenas uma comparação por elemento
III
Insertion Sort e Quicksort são estáveis
Estabilidade
❌ Incorreta
Insertion Sort é estável; Quicksort não é estável
IV
Quicksort tem O(n²) no pior caso
O(n²) pior caso
✅ Correta
Partição desbalanceada gera complexidade quadrática
Ordenação por comparação: Insertion Sort (Estável, Melhor caso Ω(n), Pior/médio caso O(n²)); Bubble Sort (Pior/médio caso O(n²)); Quicksort (Instável, Caso médio O(n log n), Pior caso O(n²))
Item I — ✅ Correto
Os métodos de ordenação por inserção (Insertion Sort) e bolha (Bubble Sort) têm, no pior caso e no caso médio, complexidade O(n²) em número de comparações. Isso é válido tanto para o número de comparações quanto para o número de trocas.
Item II — ✅ Correto
Apesar da complexidade de pior caso O(n²), o Insertion Sort apresenta complexidade de melhor caso Ω(n) em relação ao número de comparações. Isso ocorre quando o vetor já está ordenado, onde apenas uma comparação por elemento é necessária. A notação Ω indica o limite inferior assintótico.
Item III — ❌ Incorreto
O Insertion Sort é estável, ou seja, mantém a ordem relativa de elementos iguais. Contudo, o Quicksort não é estável. Conforme a literatura, o Quicksort é um algoritmo de ordenação por comparação não-estável. A proposição afirma que ambos são estáveis, o que é falso.
Item IV — ✅ Correto
O Quicksort tem complexidade O(n²) no pior caso, que ocorre quando a partição é desbalanceada (por exemplo, quando o vetor já está ordenado e o pivô é o primeiro ou último elemento). Apesar disso, seu caso médio é O(n log n).
Conclusão: Estão corretas as proposições I, II e IV. Portanto, a alternativa D é a resposta.