Questão de Algoritmos e Estrutura de Dados — Hashing — FUNDATEC 2023

Tabela hash com endereçamento aberto – condição de parada na inserção

Gabarito: letra A. Em uma tabela hash que resolve colisões por endereçamento aberto (sondas lineares, quadráticas ou duplo hash), o algoritmo de inserção percorre as posições da tabela até encontrar um slot vazio. Se a tabela estiver completamente preenchida (nenhuma posição livre), a inserção não pode ser concluída; essa situação é a condição de parada por falta de espaço. A alternativa A (Exceção de tabela cheia) descreve exatamente essa condição: o algoritmo para porque constata que a tabela está cheia. As demais alternativas tratam de ações posteriores ou de técnicas de resolução, não da condição que interrompe a inserção.

Alternativa A — ✅ Correta ⟵ GABARITO

A condição de parada do algoritmo de inserção é a inexistência de posição livre, ou seja, a tabela cheia. Nas implementações típicas, isso gera uma exceção (ou sinaliza erro), mas a condição em si é a constatação de que todos os slots estão ocupados.

Alternativa B — ❌ Incorreta

"Retorno de erro" é uma consequência da condição de parada (tabela cheia), não a condição em si. A pergunta é explícita: qual a condição que faz o algoritmo parar? O retorno de erro é o que se faz quando a condição ocorre, mas não é a condição.

Alternativa C — ❌ Incorreta

"Dupla dispersão" (double hashing) é uma das estratégias de sondagem dentro do endereçamento aberto. Ela define como calcular o próximo índice a ser visitado, não a condição de parada.

Alternativa D — ❌ Incorreta

"Remoção de item aleatório" não é uma prática padrão em tabelas hash com endereçamento aberto. Remover um item para liberar espaço é uma possível ação após a parada, mas não é a condição que a causa.

Alternativa E — ❌ Incorreta

"Redimensionamento da tabela" é uma ação corretiva que pode ser tomada quando a tabela fica cheia (realocar para um tamanho maior). Assim como o retorno de erro, não é a condição de parada, mas uma resposta a ela.