Questão de Algoritmos e Estrutura de Dados — Algoritmos de Busca — CESGRANRIO 2021
Algoritmos e Estrutura de Dados›Algoritmos de Busca
Código
cg016251
Banca
CESGRANRIO
Órgão
Banco do Brasil
Ano
2021
Nível
Médio
Cargo
Agente de Tecnologia
Desejam-se realizar buscas nas seguintes coleções de dados, representadas na linguagem Java:I - Um array de 1.000 números inteiros ordenados de forma decrescente;II - Uma lista encadeada desordenada e alocada dinamicamente, cujos 1.000 nós contêm strings (uma string por nó);III - Uma lista encadeada, alocada dinamicamente, cujos 1.000 nós contêm números decimais (um número double por nó) ordenados de forma ascendente.Levando-se em consideração a exequibilidade e a eficiência, quais métodos de busca devem ser empregados, respectivamente, em cada um dos três casos acima?
AI – sequencial; II – sequencial; III – binária
BI – binária; II – sequencial; III – sequencial
CI – binária; II – sequencial; III – binária
DI – sequencial; II – sequencial; III – sequencial
EI – sequencial; II – binária; III – binária
Revelar gabarito e comentário▾
GabaritoB — I – binária; II – sequencial; III – sequencial
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 busca: binária vs sequencial
Gabarito: letra B. A busca binária exige acesso aleatório (em arrays) e dados ordenados. A busca sequencial funciona em qualquer estrutura, mas é O(n). No caso I (array decrescente ordenado), a binária é aplicável e mais eficiente. No II (lista encadeada desordenada), apenas a sequencial é viável. No III (lista encadeada ordenada), apesar da ordenação, a binária é ineficiente por não permitir acesso direto ao meio da lista; portanto, a sequencial é a escolha adequada.
A tabela abaixo resume a aplicabilidade:
Coleção
Característica
Método adequado
I – array ordenado decrescente
Acesso aleatório, ordenado
Binária
II – lista encadeada desordenada
Acesso sequencial, desordenada
Sequencial
III – lista encadeada ordenada
Acesso sequencial, ordenada
Sequencial
Busca binária
1Requisitos
Acesso aleatório (array)
Dados ordenados
2Eficiente: O(log n)
3Busca sequencial
Requisitos
Acesso sequencial (lista)
Qualquer ordenação
Ineficiente: O(n)
4Casos concretos
I – Array ordenado decrescente
Binária ✅
II – Lista encadeada desordenada
Sequencial ✅
III – Lista encadeada ordenada
Sequencial ✅
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Sugere busca binária para a lista encadeada ordenada (III). Apesar de ordenada, a binária não é eficiente em listas encadeadas porque não é possível acessar o elemento do meio em O(1). O correto é sequencial para III.
Alternativa B — ✅ Correta ⟵ GABARITO
Associa binária ao array ordenado (I) e sequencial às listas encadeadas (II e III), exatamente conforme os critérios de eficiência.
Alternativa C — ❌ Incorreta
Propõe binária para III (mesmo erro da A). Lista encadeada ordenada não justifica o uso de binária; o custo de percorrer para acessar o meio inviabiliza a vantagem.
Alternativa D — ❌ Incorreta
Usa sequencial para todos. Ignora que o array ordenado (I) admite busca binária, que é O(log n) contra O(n) da sequencial.
Alternativa E — ❌ Incorreta
Aplica binária na lista encadeada desordenada (II), o que não faz sentido: a binária exige dados ordenados, e a lista desordenada não atende a essa condição. Para II o correto é sequencial.
PEGA ESSA DICA!
Na hora da prova, lembre-se: busca binária só é vantajosa quando a estrutura permite acesso direto aos elementos (array) e os dados estão ordenados. Para listas encadeadas, mesmo ordenadas, a busca sequencial é a escolha natural.