Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg065338
Banca
FGV
Órgão
PGM - Niterói
Ano
2023
Nível
Superior
Cargo
Analista de Tecnologia da Informação
João está trabalhando com uma base de dados que contém centenas de milhares de registros de pessoas, na qual a chave de busca é o CPF.Nesse contexto, o algoritmo/método de busca que, corretamente empregado, oferece a melhor complexidade é:
AÁrvore B;
BBitmap;
CBusca binária;
DLista encadeada;
ETabela Hash.
Revelar gabarito e comentário▾
GabaritoE — Tabela Hash.
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 em base de dados com chave CPF: melhor complexidade
Gabarito: letra E (Tabela Hash). Para uma base com centenas de milhares de registros onde a chave de busca é o CPF, a tabela hash oferece, em média, complexidade O(1) para operações de busca, inserção e remoção. As demais estruturas apresentam complexidade superior (O(log n) ou O(n)), tornando a hash table a opção mais eficiente nesse cenário.
A questão testa o conhecimento prático de complexidade de algoritmos aplicados a grandes volumes de dados com busca por chave única. A tabela hash é projetada exatamente para esse propósito: mapear chaves a valores com acesso quase instantâneo, desde que a função hash seja bem projetada e haja tratamento adequado de colisões.
Busca por chave única (CPF): Tabela Hash (O(1) médio, Acesso direto por chave); Árvore B (O(log n), Melhor para intervalos); Busca binária (O(log n), Exige dados ordenados); Lista encadeada (O(n), Busca sequencial); Bitmap (O(n), Só presença/ausência)
Alternativa A — ❌ Incorreta
Árvore B é uma estrutura balanceada usada em bancos de dados e sistemas de arquivos, com complexidade O(log n) para busca. Embora eficiente, é inferior ao O(1) médio da hash table para acesso direto por chave. É mais adequada para buscas por intervalo ou quando a ordenação é necessária.
Alternativa B — ❌ Incorreta
Bitmap é uma estrutura para representar conjuntos de bits, indicando presença/ausência. Não é apropriada para busca por chave (CPF) e não oferece recuperação direta do registro. Sua complexidade seria O(n) se usada de forma trivial.
Alternativa C — ❌ Incorreta
Busca binária exige que os dados estejam ordenados e tem complexidade O(log n). Para centenas de milhares de registros, o custo de manter a ordenação (inserções/remoções) compromete a eficiência global, além de ser mais lento que O(1).
Alternativa D — ❌ Incorreta
Lista encadeada tem busca sequencial O(n). Para centenas de milhares de registros, percorrer a lista até encontrar o CPF seria extremamente ineficiente.
Alternativa E — ✅ Correta ⟵ GABARITO
Tabela Hash fornece operações de busca, inserção e remoção com complexidade média O(1), desde que a função hash distribua bem as chaves. É a estrutura ideal quando o acesso é puramente por chave (como CPF) e não há necessidade de ordenação.
NÃO CAIA NESSA!
A banca pode induzir o aluno a escolher Árvore B por ser comum em bancos de dados. Porém, a questão pede o algoritmo/método de busca que oferece a melhor complexidade para busca por chave num cenário de grande volume e sem necessidade de ordenação. Nesse caso, a hash table vence em termos de tempo de acesso médio.
PEGA ESSA DICA!
Memorize as complexidades típicas das principais estruturas de dados: Tabela Hash: O(1) médio; Árvore binária balanceada: O(log n); Lista: O(n); Busca binária (vetor ordenado): O(log n). Para buscas exclusivamente por chave, a hash table é imbatível.