Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — Instituto Legalle 2026

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
gp019085
Banca
Instituto Legalle
Órgão
CIGA-SC
Ano
2026
Cargo
Programador
Considere uma estrutura de dados do tipotabela de dispersão (hash table), utilizada para armazenare recuperar dados de forma eficiente por meio de umafunção de espalhamento (hash). Durante a inserção deelementos, pode ocorrer colisão, isto é, quando duaschaves diferentes são mapeadas para a mesma posição databela. Para tratar colisões, pode-se utilizar a técnica deendereçamento aberto (Open Addressing), na qual, aoocorrer uma colisão, o sistema procura outra posiçãodisponível na própria tabela, verificando sequencialmenteas próximas posições livres (por exemplo: se a posição 2está ocupada, tenta a 3, depois a 4, e assimsucessivamente). Nesse contexto, qual técnica detratamento de colisões é descrita?
  1. AEncadeamento separado.
  2. BRehashing.
  3. CSondagem linear.
  4. DÁrvore binária.
  5. ELista invertida.
Revelar gabarito e comentário

GabaritoC — Sondagem linear.

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”.

Técnicas de Tratamento de Colisões em Tabelas Hash

Gabarito: letra C. A descrição do enunciado — verificar sequencialmente as próximas posições livres (posição 2 → 3 → 4 ...) — corresponde exatamente à técnica de sondagem linear (linear probing), um método de endereçamento aberto.

A banca testa o conhecimento das principais técnicas de tratamento de colisões. Vamos analisar cada alternativa:

Tratamento de colisões (hash)
  • 1Endereçamento aberto
    • Sondagem linear
      • Próxima posição livre (pos+1)
    • Sondagem quadrática
    • Duplo hash
  • 2Encadeamento separado
    • Listas ligadas por posição
  • 3Rehashing
    • Nova função hash
    • Redimensionamento da tabela
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Encadeamento separado (separate chaining) utiliza listas ligadas (ou outras estruturas) em cada posição da tabela para armazenar todos os elementos que colidem naquele índice. Não é endereçamento aberto, pois a busca por posição livre não ocorre na própria tabela.

Alternativa B — ❌ Incorreta

Rehashing é uma técnica que, ao ocorrer uma colisão, aplica uma segunda função hash (ou redimensiona a tabela e recalcula todos os hashes). Não consiste em sondar posições sequenciais.

Alternativa C — ✅ Correta ⟵ GABARITO

Sondagem linear (linear probing) é uma forma de endereçamento aberto em que, quando a posição calculada pela função hash está ocupada, o algoritmo verifica a próxima posição (posição+1), e assim sucessivamente, até encontrar uma vaga. É exatamente o que foi descrito no enunciado.

Alternativa D — ❌ Incorreta

Árvore binária é uma estrutura de dados hierárquica com até dois filhos por nó, utilizada para buscas e ordenação. Não tem relação com tratamento de colisões em tabelas hash.

Alternativa E — ❌ Incorreta

Lista invertida é um conceito de indexação (usado em bancos de dados e motores de busca), que mapeia termos para documentos. Não é método de resolução de colisões.

Conclusão: A técnica descrita é a sondagem linear.

Gabarito: letra C

Link permanente: /questoes/gp019085