Algoritmos e Estrutura de Dados · Instituto Access · 2026 | Questão sqc-qg736036

Algoritmos e Estrutura de DadosAlgoritmos

Código: qg736036
Banca: Instituto Access
Órgão: Prefeitura de Contagem - MG
Ano: 2026
Nível: Superior

Cargo: Analista de Sistemas

Ao desenvolver algoritmos de ordenação para sistemas que processam grandes volumes de dados heterogêneos, a estabilidade é um critério técnico fundamental para preservar a ordem relativa de elementos com chaves idênticas. No contexto do algoritmo Timsort (Algoritmo de Ordenação Híbrido), que é o padrão em diversas linguagens modernas, a eficiência é alcançada através da identificação de sequências de dados já ordenadas. Considerando o funcionamento interno deste algoritmo para a otimização de recursos de memória e tempo, assinale a alternativa correta.

AO algoritmo em questão é classificado como instável, pois prioriza a velocidade de execução em sistemas de Tempo Real (Real-Time Systems) sobre a preservação da ordem original de registros que possuem valores de chaves duplicadas.
BA eficiência do Timsort (Algoritmo de Ordenação Híbrido) deriva da substituição integral da recursividade por uma estrutura de Pilha (Stack) estática, o que elimina a necessidade de memória auxiliar durante a fase de Merge (Intercalação).
CA identificação de "runs" (sequências ordenadas) no Timsort (Algoritmo de Ordenação Híbrido) é aplicada exclusivamente em vetores que já ultrapassaram o limite de memória da Cache L1 (Cache de Nível Um) do processador central.
DO Timsort (Algoritmo de Ordenação Híbrido) utiliza a técnica de identificação de "runs" (sequências ordenadas) e aplica uma estratégia de intercalação adaptativa que garante complexidade de tempo de pior caso igual a O(nlogn).

Revelar gabarito e comentário

GabaritoD — O Timsort (Algoritmo de Ordenação Híbrido) utiliza a técnica de identificação de "runs" (sequências ordenadas) e aplica uma estratégia de intercalação adaptativa que garante complexidade de tempo de pior caso igual a O(nlogn).

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

Timsort (Algoritmo de Ordenação Híbrido)

Gabarito: letra D. O Timsort é um algoritmo de ordenação estável, híbrido (combina Merge Sort e Insertion Sort), que identifica sequências ordenadas ("runs") e aplica uma intercalação adaptativa, garantindo complexidade O(n log n) no pior caso. As demais alternativas contêm erros conceituais sobre estabilidade, uso de memória e aplicação das runs.

Timsort: Características (Estável, Híbrido (Merge Sort + Insertion Sort), Identifica "runs" (sequências ordenadas), Intercalação adaptativa); Complexidade (Pior caso: O(n log n), Melhor caso: O(n)); Memória (Auxiliar O(n) para merge, Pilha para gerenciar runs); Funcionamento (Varre vetor buscando runs, Runs pequenas: Insertion Sort, Runs grandes: merge otimizado)

Alternativa A — ❌ Incorreta

Afirma que o Timsort é instável e prioriza velocidade em sistemas de tempo real. Na verdade, o Timsort é estável: preserva a ordem relativa de elementos com chaves idênticas. A estabilidade é uma característica herdada do Merge Sort, base do algoritmo. A menção a sistemas de tempo real é irrelevante e não altera essa propriedade.

Alternativa B — ❌ Incorreta

Diz que a eficiência do Timsort deriva da substituição integral da recursividade por uma pilha estática, eliminando memória auxiliar durante o merge. Isso é falso: o Timsort usa recursão (ou pilha explícita) para gerenciar as runs, mas necessita de memória auxiliar O(n) para realizar a intercalação (merge). A afirmação de que elimina memória auxiliar contradiz o funcionamento de qualquer algoritmo do tipo merge.

Alternativa C — ❌ Incorreta

Alega que a identificação de "runs" é aplicada exclusivamente em vetores que ultrapassaram o limite da cache L1. A identificação de runs ocorre independentemente do tamanho do vetor ou do estado da cache. O Timsort varre o vetor inteiro em busca de sequências já ordenadas (crescentes ou decrescentes) desde o início, sendo uma etapa central do algoritmo. A restrição à cache L1 é um detalhe de hardware que não define o funcionamento do algoritmo.

Alternativa D — ✅ Correta ⟵ GABARITO

O Timsort identifica runs (sequências ordenadas) e aplica uma estratégia de intercalação adaptativa que combina essas runs de forma eficiente. O pior caso do algoritmo é O(n log n), mesma complexidade do Merge Sort, garantindo desempenho previsível mesmo para grandes volumes de dados. A adaptatividade (uso de Insertion Sort para runs pequenas e merge otimizado) não altera a complexidade assintótica do pior caso.

NÃO CAIA NESSA!

A principal pegadinha da questão é associar o Timsort à instabilidade. Lembre-se: todo algoritmo de ordenação baseado em Merge Sort (como o Timsort) é estável por construção. Além disso, a complexidade O(n log n) no pior caso é uma propriedade fundamental do Timsort, herdada do Merge Sort. Para gravar: Timsort = estável + O(n log n) pior caso + runs adaptativas.

Gabarito: letra D

Link permanente: /questoes/qg736036