Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — UFSC 2022

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq808676
Banca
UFSC
Órgão
UFSC
Ano
2022
Nível
Médio
Cargo
Técnico de Tecnologia da Informação
Considere o problema de ordenar em ordem crescente o vetor (array) de números inteiros [7, 30, 2, 45, 66, 13, 17, 23, 1, 15] utilizando o algoritmo de ordenação Bubble Sort em sua versão não recursiva. Analise as afirmativas abaixo e assinale a alternativa correta.I. São feitas 23 trocas de elementos do vetor até que ele esteja totalmente ordenado.II. A ordem dos elementos do vetor será [2, 7, 30, 13, 17, 23, 1, 15, 45, 66] após 10 trocas de elementos.III. O número de trocas de elementos diminui à medida que a execução do algoritmo de ordenação avança.
  1. ASomente as afirmativas I e II estão corretas.
  2. BSomente as afirmativas II e III estão corretas.
  3. CSomente a afirmativa III está correta.
  4. DSomente a afirmativa I está correta.
  5. ETodas as afirmativas estão corretas.
Revelar gabarito e comentário

GabaritoC — Somente a afirmativa III está correta.

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”.

Bubble Sort — contagem de trocas

Gabarito: letra C (somente a afirmativa III está correta). A simulação do Bubble Sort no vetor [7,30,2,45,66,13,17,23,1,15] mostra que são necessárias 24 trocas (e não 23) para ordená-lo; a afirmativa II apresenta uma ordem incorreta após 10 trocas; já a afirmativa III é verdadeira, pois o número de trocas tende a diminuir a cada passada.

A questão exige a simulação passo a passo do algoritmo de ordenação Bubble Sort (versão não recursiva) para verificar cada uma das três afirmações.

Simulação completa (contagem de trocas)

Vetor inicial: [7, 30, 2, 45, 66, 13, 17, 23, 1, 15].

Passo 1 (i=0..8): 6 trocas → [7,2,30,45,13,17,23,1,15,66] Passo 2 (i=0..7): 6 trocas → [2,7,30,13,17,23,1,15,45,66] Passo 3 (i=0..6): 5 trocas → [2,7,13,17,23,1,15,30,45,66] Passo 4 (i=0..5): 2 trocas → [2,7,13,17,1,15,23,30,45,66] Passo 5 (i=0..4): 2 trocas → [2,7,13,1,15,17,23,30,45,66] Passo 6 (i=0..3): 1 troca → [2,7,1,13,15,17,23,30,45,66] Passo 7 (i=0..2): 1 troca → [2,1,7,13,15,17,23,30,45,66] Passo 8 (i=0..1): 1 troca → [1,2,7,13,15,17,23,30,45,66] Passo 9 (i=0..0): 0 trocas (vetor ordenado, algoritmo termina).

Total de trocas = 24.

Análise das afirmativas

  1. 1Passo 1: 6 trocas[7,2,30,45,13,17,23,1,15,66]
  2. 2Passo 2: 6 trocas[2,7,30,13,17,23,1,15,45,66]
  3. 3Passo 3: 5 trocas[2,7,13,17,23,1,15,30,45,66]
  4. 4Passo 4: 2 trocas[2,7,13,17,1,15,23,30,45,66]
  5. 5Passo 5: 2 trocas[2,7,13,1,15,17,23,30,45,66]
  6. 6Passo 6: 1 troca[2,7,1,13,15,17,23,30,45,66]
  7. 7Passo 7: 1 troca[2,1,7,13,15,17,23,30,45,66]
  8. 8Passo 8: 1 troca[1,2,7,13,15,17,23,30,45,66]
  9. 9Passo 9: 0 trocasOrdenado
LEVEL · soulevel.com.br

Afirmativa I — ❌ Incorreta

Afirma que são feitas 23 trocas. A simulação comprova que o algoritmo realiza exatamente 24 trocas até a ordenação completa. Portanto, o número está incorreto.

Afirmativa II — ❌ Incorreta

Após 10 trocas (final do Passo 2, swap nº 10), o vetor encontra-se na configuração [2, 7, 30, 13, 17, 23, 45, 1, 15, 66], e não [2, 7, 30, 13, 17, 23, 1, 15, 45, 66] como afirmado. A posição dos elementos 1 e 45 está trocada.

Afirmativa III — ✅ Correta

No Bubble Sort, a cada passada os maiores elementos já estão nas suas posições finais (no final do vetor). Consequentemente, o número de comparações e de trocas diminui progressivamente ao longo da execução. Na simulação, as trocas por passada foram: 6, 6, 5, 2, 2, 1, 1, 1, 0 – clara tendência de redução. A afirmativa está correta.

Conclusão

Apenas a afirmativa III é verdadeira. Logo, a alternativa correta é a letra C.

Gabarito: letra C

Link permanente: /questoes/qq808676