Algoritmos e Estrutura de Dados · FGV · 2026 | Questão sqc-fg127412

Tabelas Hash: Endereçamento Aberto e Sondagem Linear

Gabarito: letra B. O efeito principal de uma alta taxa de ocupação (α ≈ 0,8) em uma tabela hash com endereçamento aberto e sondagem linear é o agrupamento primário (primary clustering), que consiste na formação de longos blocos contíguos de slots ocupados, aumentando drasticamente o número médio de sondagens necessárias para inserir ou buscar uma chave.

A sondagem linear resolve colisões percorrendo sequencialmente os slots seguintes até encontrar uma posição livre. Quando a tabela está muito cheia, as chaves que colidem tendem a se acumular em clusters, fazendo com que o tempo de operação degrade de O(1) esperado para O(n) no pior caso (tabela quase cheia ou totalmente ocupada).

Efeito	Descrição	Relação com Sondagem Linear	Consequência
Agrupamento Primário (B)	Formação de longos blocos contíguos de slots ocupados	Causado pela sondagem linear quando α está alto	Degradação do tempo de operação de O(1) para O(n)
Underflow (A)	Estouro negativo ou valor abaixo do mínimo representável	Não se aplica a tabelas hash	Sem relação com o contexto
Overflow de Pilha (C)	Excesso de capacidade de memória em estrutura LIFO	Estrutura de dados diferente	Não se aplica a tabelas hash
Agrupamento Secundário (D)	Chaves que colidem seguem mesma sequência de sondagem	Ocorre em sondagem quadrática ou hashing duplo	Não é o efeito principal da sondagem linear
Complexidade O(log n) (E)	Complexidade típica de árvores balanceadas	Tabela hash esperada é O(1)	Afirmação incorreta para o contexto

1Colisão ocorre
2Busca slot livre sequencial
3Forma cluster contíguo
4Agrupamento primário

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

O termo underflow refere-se a situações de estouro negativo (ex.: pilha vazia) ou a valores abaixo do mínimo representável, não tendo relação com tabelas hash. Não há perda de dados por underflow nesse contexto.

Alternativa B — ✅ Correta ⟵ GABARITO

O agrupamento primário é exatamente o fenômeno descrito: a sondagem linear provoca que colisões subsequentes estendam o mesmo cluster, criando regiões densamente ocupadas que prejudicam o desempenho. Quanto maior α, pior o efeito.

Alternativa C — ❌ Incorreta

Overflow de pilha (stack overflow) ocorre quando uma pilha excede sua capacidade de memória, geralmente por recursão excessiva ou alocação inadequada. É uma estrutura de dados diferente (LIFO) e não se aplica a tabelas hash.

Alternativa D — ❌ Incorreta

O agrupamento secundário (secondary clustering) é um problema de outros métodos de resolução de colisão, como a sondagem quadrática ou hashing duplo, nos quais chaves que colidem no mesmo slot inicial seguem a mesma sequência de sondagem – mas não é o efeito principal da sondagem linear, que sofre primariamente do agrupamento primário.

Alternativa E — ❌ Incorreta

A complexidade esperada de uma tabela hash é O(1) para inserção e busca. Embora no pior caso (tabela cheia ou com muitos clusters) possa degradar para O(n), não se torna O(log n) – isso seria típico de árvores balanceadas. A afirmação está fora do contexto de hash.

NÃO CAIA NESSA!

A banca pode tentar confundir o candidato entre agrupamento primário e secundário. Lembre-se: sondagem linear → agrupamento primário (clusters contíguos); sondagem quadrática e double hashing → agrupamento secundário (mesma sequência para chaves que colidem no mesmo endereço inicial).

Gabarito: letra B.