Pular para o conteúdo principal

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

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg046130
Banca
UFSC
Órgão
UFSC
Ano
2023
Nível
Médio
Cargo
Técnico de Tecnologia da Informação
Considere as seguintes definições relacionadas a algoritmos de ordenação e assinale a alternativa que identifica corretamente as três definições, considerando sua ordem.1. O algoritmo consiste em percorrer o vetor de itens desordenados da esquerda para a direita, ordenando um item por vez. A cada passo, o item não ordenado é comparado aos itens à sua esquerda (os quais já estão ordenados) de modo a encontrar em qual posição ele deve ser colocado. Esses passos são repetidos para cada um dos itens não ordenados restantes. O algoritmo termina quando o último item do vetor é colocado na posição correta.2. O algoritmo divide logicamente o vetor em duas partições: uma partição contendo itens ordenados, que é construída da esquerda para a direita na frente (esquerda) do vetor, e uma partição contendo itens restantes não ordenados que ocupam o resto do vetor. Inicialmente, a partição ordenada está vazia e a partição não ordenada é o próprio vetor de entrada. Em cada passo, o algoritmo encontra o menor item na partição não ordenada, trocando-o com o item não ordenado mais à esquerda da partição (colocando-o, portanto, em ordem). Então, o limite lógico entre as partições ordenada e não ordenada é incrementado em uma posição e os passos anteriores são repetidos. O algoritmo termina quando resta apenas um item a ser ordenado.3. O algoritmo divide o problema em partes menores, resolvendo cada parte separadamente e juntando os resultados posteriormente. O vetor é dividido em duas partes iguais, sendo cada uma delas dividida em duas partes, e assim por diante, até restarem partes com um ou dois itens, cuja ordenação é trivial. Para juntar pares de partes ordenadas, os dois primeiros itens de cada parte são separados e o menor deles é selecionado e posicionado como primeiro elemento. Em seguida, os menores entre os restantes são comparados e posicionados e assim se prossegue até que todos os elementos tenham sido juntados. O procedimento é repetido até que todas as partes tenham sido tratadas.
  1. AInsertion Sort (ordenação por inserção) – Selection Sort (ordenação por seleção) – Jungle Sort (ordenação selvagem)
  2. BSelection Sort (ordenação por seleção) – Insertion Sort (ordenação por inserção) – Quick Sort
  3. CSelection Sort (ordenação por seleção) – Insertion Sort (ordenação por inserção) – Bubble Sort
  4. DInsertion Sort (ordenação por inserção) – Selection Sort (ordenação por seleção) – Merge Sort
  5. EMerge Sort – Shell Sort – Bubble Sort
Revelar gabarito e comentário

GabaritoD — Insertion Sort (ordenação por inserção) – Selection Sort (ordenação por seleção) – Merge Sort

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

Algoritmos de ordenação: Insertion Sort, Selection Sort e Merge Sort

Gabarito: letra D. As três descrições correspondem, respectivamente, aos algoritmos de ordenação por inserção (Insertion Sort), ordenação por seleção (Selection Sort) e ordenação por intercalação (Merge Sort). A alternativa D é a única que nomeia corretamente os três, nesta ordem.

A banca testa o reconhecimento dos algoritmos clássicos a partir de suas descrições textuais. Cada descrição contém uma pista-chave:

  1. Descrição 1: "compara o item com os já ordenados à sua esquerda" → Insertion Sort.

  2. Descrição 2: "encontra o menor elemento da parte não ordenada e troca com o primeiro" → Selection Sort.

  3. Descrição 3: "divide recursivamente ao meio e depois intercala" → Merge Sort.

Alternativa A — ❌ Incorreta

Insere "Jungle Sort", que não é um algoritmo de ordenação real. O terceiro algoritmo descrito é claramente Merge Sort, e não qualquer "Jungle Sort".

Alternativa B — ❌ Incorreta

Inverte a ordem: apresenta Selection Sort como primeiro e Insertion Sort como segundo. Além disso, coloca Quick Sort no lugar de Merge Sort no terceiro algoritmo.

Alternativa C — ❌ Incorreta

Também inverte a ordem dos dois primeiros e substitui Merge Sort por Bubble Sort, que não corresponde à descrição de divisão e intercalação.

Alternativa D — ✅ Correta ⟵ GABARITO

Ordenação correta: Insertion Sort, Selection Sort, Merge Sort. Cada nome casa exatamente com o comportamento descrito.

Alternativa E — ❌ Incorreta

O primeiro algoritmo descrito é Merge Sort, que não é o Insertion Sort, e os outros dois (Shell Sort e Bubble Sort) não se encaixam nas descrições.

Conclusão: a sequência correta é Insertion Sort → Selection Sort → Merge Sort, portanto a alternativa D é o gabarito.

NÃO CAIA NESSA!

A banca troca a ordem dos algoritmos (alternativas B e C) e insere nomes fictícios ou inadequados (Jungle Sort, Quick Sort, Bubble Sort). O candidato deve ler atentamente cada descrição e identificar a característica central de cada método.

Gabarito: letra D

Link permanente: /questoes/qg046130