Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IADES 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg205171
Banca
IADES
Órgão
BRB
Ano
2024
Nível
Superior
Cargo
Analista de Tecnologia da Informação
No que se refere ao uso de tabelas de hash para armazenamento de informação, assinale a alternativa correta.
AA busca por um elemento em uma tabela de hash tem complexidade de tempo O(log n).
BO espaço de armazenamento de uma tabela de hash é igual ao de uma tabela com acesso direto por endereço, em que a quantidade de chaves possíveis é igual a K.
CÉ impossível garantir que uma tabela de hash seja completamente livre de colisões de chaves.
DPara maior eficiência, recomenda-se a inserção de elementos de maneira ordenada em uma tabela de hash.
EA área de memória ocupada por uma tabela de hash necessita ser pré-alocada antes do carregamento dos dados.
Revelar gabarito e comentário▾
GabaritoC — É impossível garantir que uma tabela de hash seja completamente livre de colisões de chaves.
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”.
Tabelas Hash
Gabarito: letra C. Em tabelas hash, colisões são inevitáveis pelo princípio da casa dos pombos: se o número de chaves possíveis supera o número de slots, não é possível garantir uma função hash que evite colisões (a menos que se conheça todo o conjunto de chaves antecipadamente).
A banca testa conceitos fundamentais sobre hash tables. Vamos analisar cada alternativa:
Alternativa A — ❌ Incorreta
Afirma que a busca em tabela hash tem complexidade O(log n). Na prática, a busca em uma tabela hash bem projetada é O(1) em média. O(log n) refere-se a estruturas como árvores binárias balanceadas (AVL, Rubro-Negra). A confusão comum é trocar a complexidade da hash pela de árvores.
Alternativa B — ❌ Incorreta
Diz que o espaço de armazenamento da tabela hash é igual ao de uma tabela de acesso direto (endereçamento direto) quando o número de chaves possíveis é K. No endereçamento direto, alocamos espaço para todas as K chaves possíveis; na tabela hash, alocamos espaço proporcional ao número real de elementos (n), geralmente O(n). Como K costuma ser muito maior que n, o espaço da hash é muito menor. A alternativa erra ao igualá-los.
Alternativa C — ✅ Correta ⟵ GABARITO
"É impossível garantir que uma tabela de hash seja completamente livre de colisões de chaves." Correto. Pelo princípio da casa dos pombos, se o domínio das chaves é maior que o número de slots (o que é comum), colisões são inevitáveis. Mesmo com uma função hash perfeita, isso só é possível se o conjunto de chaves for conhecido e estático. Em geral, colisões são tratadas com encadeamento ou endereçamento aberto.
Alternativa D — ❌ Incorreta
Recomenda inserir elementos de maneira ordenada para maior eficiência. Em tabelas hash, a ordem de inserção não afeta o desempenho; a posição é determinada pela função hash. Inserir ordenado só adicionaria custo desnecessário. Essa alternativa confunde hash com estruturas que dependem de ordenação (como árvores de busca).
Alternativa E — ❌ Incorreta
Afirma que a área de memória precisa ser pré-alocada antes do carregamento dos dados. Muitas implementações (ex.: dict do Python) alocam dinamicamente e redimensionam conforme necessário. Embora algumas implementações usem uma tabela de tamanho fixo pré-alocado, não é uma necessidade — a tabela hash pode crescer conforme os elementos são inseridos. Portanto, a afirmação é falsa.
PEGA ESSA DICA!
Em questões sobre hash, grave os três pilares: (1) busca O(1) em média; (2) colisões inevitáveis; (3) a função hash determina a posição, não a ordem de inserção. Esses pontos eliminam rapidamente a maioria dos distratores.