Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2018

Algoritmos e Estrutura de DadosAlgoritmos
Código
cg012201
Banca
CESGRANRIO
Órgão
Petrobras
Ano
2018
Nível
Superior
Cargo
Analista de Sistemas Júnior - Processos de Negócio
Dada a sequência numérica (15,11,16,18,23,5,10,22,21,12) para ordenar pelo algoritmo Selection Sort, qual é a sequência parcialmente ordenada depois de completada a quinta passagem do algoritmo?
  1. A[15, 11, 16, 18, 12, 5, 10, 21, 22, 23]
  2. B[15, 11, 5, 10, 12, 16, 18, 21, 22, 23]
  3. C[15, 11, 16, 10, 12, 5, 18, 21, 22, 23]
  4. D[10, 11, 5, 12, 15, 16, 18, 21, 22, 23]
  5. E[12, 11, 5, 10, 15, 16, 18, 21, 22, 23]
Revelar gabarito e comentário

GabaritoB — [15, 11, 5, 10, 12, 16, 18, 21, 22, 23]

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

Selection Sort – Simulação passo a passo

Gabarito: letra B. A questão aplica o Selection Sort na variante que seleciona o maior elemento da parte não ordenada e o coloca no final. Após 5 passagens, os 5 maiores elementos já estão posicionados corretamente ao final, resultando no vetor [15, 11, 5, 10, 12, 16, 18, 21, 22, 23].

O Selection Sort tradicional (seleciona o menor e coloca no início) produziria [5, 10, 11, 12, 15, 23, 16, 22, 21, 18] após 5 passagens, que não corresponde a nenhuma alternativa. Logo, a banca utilizou a variante de seleção do máximo (ordenação decrescente progressiva).

Simulação (máximo para o final)

Vetor inicial: [15, 11, 16, 18, 23, 5, 10, 22, 21, 12]

Passagem

Intervalo analisado

Maior encontrado

Posição do maior

Troca com

Vetor resultante

1ª

[0..9]

23 (índice 4)

4

índice 9

[15, 11, 16, 18, 12, 5, 10, 22, 21, 23]

2ª

[0..8]

22 (índice 7)

7

índice 8

[15, 11, 16, 18, 12, 5, 10, 21, 22, 23]

3ª

[0..7]

21 (índice 7)

7

índice 7

[15, 11, 16, 18, 12, 5, 10, 21, 22, 23]

4ª

[0..6]

18 (índice 3)

3

índice 6

[15, 11, 16, 10, 12, 5, 18, 21, 22, 23]

5ª

[0..5]

16 (índice 2)

2

índice 5

[15, 11, 5, 10, 12, 16, 18, 21, 22, 23]

Após a 5ª passagem, os elementos das posições 5 a 9 (16, 18, 21, 22, 23) já estão ordenados. A parte não ordenada (posições 0 a 4) será tratada nas passagens seguintes.

NÃO CAIA NESSA!

A banca usou a variante que seleciona o maior elemento, enquanto muitos candidatos estudam a versão que seleciona o menor. Se você simular a versão do menor (tradicional), o resultado após 5 passagens é [5, 10, 11, 12, 15, 23, 16, 22, 21, 18], que não aparece nas opções. Fique atento ao comportamento real do algoritmo na questão.

  1. 11ª: 23 troca com 12[15,11,16,18,12,5,10,22,21,23]
  2. 22ª: 22 troca com 21[15,11,16,18,12,5,10,21,22,23]
  3. 33ª: 21 já está[15,11,16,18,12,5,10,21,22,23]
  4. 44ª: 18 troca com 10[15,11,16,10,12,5,18,21,22,23]
  5. 55ª: 16 troca com 5[15,11,5,10,12,16,18,21,22,23]
LEVEL · soulevel.com.br

Análise das alternativas

  • A) ❌ Incorreta. Não corresponde a nenhuma sequência esperada após 5 passagens, seja na variante do menor ou do maior.

  • B) ✅ Correta. Exatamente o resultado da simulação acima (máximo no final).

  • C) ❌ Incorreta. É o vetor após a 4ª passagem da variante do maior, não após a 5ª.

  • D) ❌ Incorreta. Se fosse a variante do menor, após 4 passagens teríamos [5, 10, 11, 12, 23, 15, 16, 22, 21, 18], não essa sequência.

  • E) ❌ Incorreta. Também não se alinha com as simulações.

Gabarito: letra B.

Link permanente: /questoes/cg012201