Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FUNDATEC 2023
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq896690
Banca
FUNDATEC
Órgão
PROCERGS
Ano
2023
Nível
Superior
Cargo
ANC - Analista em Computação - Ênfase em Administração de Dados
Quais as principais diferenças entre as tabelas hash com encadeamento e com endereçamento aberto?
AEncadeamento tem menor chance de colisões; endereçamento aberto é mais rápido para inserção e remoção.
BEncadeamento é mais rápido para busca; endereçamento aberto tem menor chance de colisões.
CEncadeamento usa menos memória; endereçamento aberto é mais rápido para busca.
DEncadeamento tem maior chance de colisões; endereçamento aberto é mais lento para inserção e remoção.
EEncadeamento é mais fácil de implementar; endereçamento aberto é mais difícil de implementar.
Revelar gabarito e comentário▾
GabaritoD — Encadeamento tem maior chance de colisões; endereçamento aberto é mais lento para inserção e remoção.
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: Encadeamento vs Endereçamento Aberto
Gabarito: letra D. A principal diferença de desempenho é que o endereçamento aberto é mais lento para inserção e remoção devido à necessidade de sondagem, enquanto o encadeamento é mais rápido nesses aspectos. A afirmação sobre 'maior chance de colisões' no encadeamento é discutível, mas a parte sobre velocidade é correta e suficiente para diferenciar as alternativas.
A banca cobra as diferenças operacionais entre os dois métodos de resolução de colisões. Vejamos cada alternativa:
Característica
Encadeamento
Endereçamento Aberto
Velocidade de inserção e remoção
Mais rápido (insere/remove diretamente na lista encadeada)
Mais lento (requer sondagem e tratamento de remoções com marcação)
Uso de memória
Mais memória (ponteiros extras para listas encadeadas)
Menos memória (apenas o array principal)
Localidade de cache
Pior (dados espalhados em listas)
Melhor (dados no mesmo array)
Chance de colisões
Maior (colisões são aceitas e armazenadas em listas)
Menor (sondagem tenta evitar colisões futuras)
Tabelas hash
1Encadeamento
Colisões: aceitas em listas
Inserção/remoção: rápidas
Memória: maior (ponteiros)
2Endereçamento aberto
Colisões: evitadas por sondagem
Inserção/remoção: lentas (sondagem)
Memória: menor
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que encadeamento tem menor chance de colisões e que endereçamento aberto é mais rápido para inserção e remoção. Ambas as afirmações são falsas: a chance de colisão depende da função hash e do fator de carga, não do método de resolução; e o endereçamento aberto é mais lento para inserção e remoção por causa da sondagem.
Alternativa B — ❌ Incorreta
Diz que encadeamento é mais rápido para busca e que endereçamento aberto tem menor chance de colisões. Em média, ambos têm busca O(1), não sendo um mais rápido que o outro intrinsecamente. A chance de colisão não é menor no endereçamento aberto.
Alternativa C — ❌ Incorreta
Afirma que encadeamento usa menos memória e que endereçamento aberto é mais rápido para busca. Na verdade, encadeamento usa mais memória (ponteiros extras). O endereçamento aberto pode ter melhor localidade de cache, mas não é mais rápido para busca de forma geral; ambos têm complexidade média O(1).
Alternativa D — ✅ Correta ⟵ GABARITO
A primeira parte ('encadeamento tem maior chance de colisões') é controversa, mas pode ser interpretada como: no encadeamento, colisões são simplesmente aceitas e armazenadas em listas, enquanto no endereçamento aberto a sondagem tenta evitar colisões futuras. A segunda parte está correta: endereçamento aberto é mais lento para inserção e remoção devido ao processo de sondagem (linear, quadrática, duplo hash) e à necessidade de tratamento de remoções com marcação ('deleted'). Portanto, esta alternativa descreve uma diferença real de desempenho.
Alternativa E — ❌ Incorreta
Afirma que encadeamento é mais fácil de implementar e endereçamento aberto mais difícil. Embora isso seja geralmente verdade, não é uma 'principal diferença' técnica entre as estruturas; a questão espera diferenças de desempenho ou comportamento. Além disso, a facilidade de implementação é subjetiva.
NÃO CAIA NESSA!
A banca insere uma afirmação parcialmente imprecisa na alternativa D ('maior chance de colisões'), mas o candidato deve focar no que é consenso: o endereçamento aberto é mais lento para inserção/remoção. As outras alternativas contêm erros técnicos claros.