Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2019

Algoritmos e Estrutura de DadosAlgoritmos
Código
fg035850
Banca
FGV
Órgão
DPE-RJ
Ano
2019
Nível
Superior
Cargo
Técnico Superior Especializado - Tecnologia da Informação
Considere os seguintes métodos de busca/indexação:I. Busca bináriaII. Tabelas hashIII. Índices B-treesConsidere ainda um universo de busca com aproximadamente um milhão de chaves, para o qual cada método tenha sido implementado adequadamente.Num benchmark extensivo, cada método apresentou um número médio de acessos até que cada chave fosse localizada.Esses tempos médios, em ordem crescente, correspondem aos métodos:
  1. AI, II, III;
  2. BI, III, II;
  3. CII, I, III;
  4. DII, III, I;
  5. EIII, I, II.
Revelar gabarito e comentário

GabaritoD — II, III, I;

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

Análise de desempenho de métodos de busca

Gabarito: letra D – a ordem crescente de número médio de acessos é: tabelas hash (II), B-trees (III), busca binária (I).

A complexidade média de cada método para um universo de aproximadamente um milhão de chaves (10⁶) é:

  • Tabela hash: busca em média O(1), tipicamente 1 ou 2 acessos (função hash boa e tratamento de colisões adequado).

  • B-tree: altura O(log_f N), com fator de ramificação f grande (ex.: centenas), resultando em ≈2–3 acessos.

  • Busca binária: O(log₂ N) ≈ 20 acessos (para 10⁶, log₂ ≈ 19,93).

Portanto, do menor para o maior número de acessos: II → III → I.

  1. 1Tabela hashO(1) ≈ 1-2 acessos
  2. 2B-treeO(log_f N) ≈ 2-3 acessos
  3. 3Busca bináriaO(log₂ N) ≈ 20 acessos
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma I, II, III (busca binária, hash, B-tree). Coloca a busca binária como a mais rápida, o que é falso – ela é a mais lenta das três.

Alternativa B — ❌ Incorreta

Ordem I, III, II: busca binária, B-tree, hash. Hash é mais rápida que B-tree, logo não pode vir depois.

Alternativa C — ❌ Incorreta

Ordem II, I, III: hash, busca binária, B-tree. B-tree é mais rápida que busca binária, portanto deveria vir antes.

Alternativa D — ✅ Correta ⟵ GABARITO

Ordem II, III, I: hash → B-tree → busca binária. Coerente com as complexidades médias.

Alternativa E — ❌ Incorreta

Ordem III, I, II: B-tree, busca binária, hash. Hash é o método mais rápido, logo deveria ser o primeiro.

Conclusão: A sequência correta é II (tabelas hash), III (B-trees), I (busca binária). Portanto, gabarito: D.

Link permanente: /questoes/fg035850