Questão de Algoritmos e Estrutura de Dados — Hashing — FCC 2015
Algoritmos e Estrutura de Dados›Hashing
Código
fc019780
Banca
FCC
Órgão
DPE-SP
Ano
2015
Nível
Médio
Cargo
Programador
Um Programador da Defensoria Pública do Estado de São Paulo foi solicitado a propor uma solução para o problema: Há uma quantidade grande de dados classificáveis por chave e estes dados devem ser divididos em subconjuntos com base em alguma característica das chaves. Um método eficiente deve ser capaz de localizar em qual subconjunto deve-se colocar cada chave e depois estes subconjuntos bem menores devem ser gerenciados por algum método simples de busca para que se localize uma chave rapidamente. O Programador propôs como solução, corretamente, a implementação de
ADeques.
BTabela e função hash.
CPilhas.
DFila duplamente encadeada.
EÁrvore Binária de Busca.
Revelar gabarito e comentário▾
GabaritoB — Tabela e função 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”.
Tabela Hash: solução para busca por chave com subdivisão eficiente
Gabarito: letra B. O enunciado descreve um problema de mapeamento de chaves para subconjuntos (baldes) e posterior busca nesses subconjuntos. A estrutura que realiza exatamente isso é a tabela hash, que utiliza uma função de espalhamento (hash) para determinar em qual posição de um array a chave será armazenada, dividindo os dados em partes menores que podem ser geridas por buscas simples (como busca linear em cada balde).
O fragmento do contexto sobre estruturas de dados canônicas confirma: "A tabela de dispersão implementa o mapeamento entre chaves e valores através de funções de espalhamento (funções hash)."
Estrutura
Mapeamento por chave
Divisão em subconjuntos (baldes)
Busca rápida em subconjuntos menores
Adequação ao problema
Tabela hash (B)
Sim (função hash)
Sim (baldes/posições)
Sim (busca linear ou lista)
✅ Correta
Deques (A)
Não
Não
Não
❌ Incorreta
Pilhas (C)
Não
Não
Não
❌ Incorreta
Fila duplamente encadeada (D)
Não
Não
Não
❌ Incorreta
Árvore Binária de Busca (E)
Sim (por comparação)
Não (estrutura única)
Sim (O(log n))
❌ Incorreta
Alternativa A — ❌ Incorreta
Deques (filas duplas) são estruturas lineares que permitem inserção e remoção em ambas as extremidades, mas não oferecem nenhum mecanismo de mapeamento por chave ou divisão em subconjuntos baseados em características das chaves.
Alternativa B — ✅ Correta ⟵ GABARITO
A tabela hash (ou tabela de espalhamento) é a implementação clássica para dicionários que exigem busca rápida. Ela usa uma função hash para calcular um índice a partir da chave, distribuindo os itens em um array (baldes). Cada balde contém um subconjunto muito menor do que o total, que pode ser pesquisado com métodos simples (busca linear, lista encadeada). O problema descrito no enunciado é exatamente o propósito dessa estrutura.
Alternativa C — ❌ Incorreta
Pilhas operam no princípio LIFO (último a entrar, primeiro a sair). Não há relação entre chave e posição; não servem para particionar dados por característica da chave.
Alternativa D — ❌ Incorreta
Uma fila duplamente encadeada é uma fila (FIFO) com encadeamento em ambos os sentidos. Assim como deques, não possui mapeamento de chave para subconjuntos.
Alternativa E — ❌ Incorreta
Árvores binárias de busca (ABB) organizam os elementos comparando chaves, mas não dividem os dados em subconjuntos gerenciados separadamente. Embora a busca seja eficiente (O(log n) em árvores balanceadas), a estrutura é única, sem a divisão em baldes menores descrita no enunciado.
PEGA ESSA DICA!
A chave da questão está no termo "divididos em subconjuntos com base em alguma característica das chaves". Isso descreve exatamente o funcionamento de uma função hash: ela transforma a chave em um índice (característica) que define o subconjunto. Lembre-se de que tabelas hash são a única estrutura entre as opções que faz esse particionamento.