Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2021
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg043745
Banca
FGV
Órgão
IMBEL
Ano
2021
Nível
Superior
Cargo
Supervisor - Tecnologia da Informação - Reaplicação
Considere um conjunto de 65.536 chaves ordenadas, distintas entre si, armazenadas num array.Com relação ao processo de busca binária, assinale a opção que indica o número máximo de acessos ao array necessários para localizar uma determinada chave qualquer.
A10
B16
C64
D256
E32.768
Revelar gabarito e comentário▾
GabaritoB — 16
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”.
Busca binária: número máximo de acessos
Gabarito: letra B. Para um array ordenado com 65.536 (2^16) chaves, o número máximo de acessos necessários na busca binária é igual ao logaritmo de base 2 do número de elementos, ou seja, 16. Cada acesso reduz o espaço de busca pela metade; após 16 acessos, resta apenas um elemento, garantindo a localização de qualquer chave.
A busca binária é um algoritmo eficiente que, a cada iteração, compara a chave procurada com o elemento do meio do intervalo e descarta a metade que não pode conter a chave. O número máximo de iterações (acessos) é, portanto, o número de vezes que se pode dividir o conjunto ao meio até restar um único elemento. Para N = 65536 = 2^16, esse número é exatamente 16.
1N = 65.536 = 2^16
2Cada acesso divide ao meio
3Após 16 acessos, resta 1
4Máximo = log₂(N) = 16
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
10 acessos seriam suficientes para, no máximo, 2^10 = 1024 chaves. Para 65536 chaves, 10 acessos não são suficientes.
Alternativa B — ✅ Correta ⟵ GABARITO
Como explicado, log₂(65536) = 16. É o valor correto para o pior caso.
Alternativa C — ❌ Incorreta
64 acessos corresponderiam a 2^64, um número astronomicamente maior que 65536. Não há relação com o problema.
Alternativa D — ❌ Incorreta
256 = 2^8, suficiente para apenas 256 elementos. Totalmente insuficiente para 65536.
Alternativa E — ❌ Incorreta
32768 acessos é um número muito acima do necessário; sequer é uma potência de dois do logaritmo. O pior caso é 16, não 32768.
PEGA ESSA DICA!
Decore a relação entre potências de dois e o número de elementos: N = 2^k ⇒ máximo de comparações = k. Memorize os valores comuns: 2^10=1024, 2^16=65536, 2^20=1.048.576.