Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CEPS-UFPA 2022
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
gp036805
Banca
CEPS-UFPA
Órgão
UFPA
Ano
2022
Cargo
CEPS - - Analista de Tecnologia da Informação / Área: Desenvolvimento
Analise as seguintes afirmativas sobre os conceitos relacionados às tabelas de dispersão. I. Esse método aproveita a possibilidade de acesso randômico à memória para alcançar umacomplexidade temporal média por operação de O(1), sendo o pior caso, entretanto, O(log n), em quen é a quantidade de chaves a serem armazenadas na tabela.II. Uma das estratégias conhecidas para tratar colisões consiste em armazenar as chaves com omesmo endereço-base em listas encadeadas. As listas podem se encontrar no exterior da tabela oucompartilhar o mesmo espaço dela. III. A ideia básica do método de endereçamento aberto para tratamento de colisões é, caso aindahaja espaço, armazenar as chaves com o mesmo endereço-base na própria tabela, mas sem anecessidade da criação de listas encadeadas. Com relação a essas afirmativas, pode-se afirmar que
AI, II e III são corretas.
BI e II, apenas, são corretas.
CI e III, apenas, são corretas.
DII e III, apenas, são corretas.
EI, II e III são falsas.
Revelar gabarito e comentário▾
GabaritoD — II e III, apenas, são corretas.
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 de dispersão (Hash Tables): análise de afirmativas
Gabarito: letra D — apenas as afirmativas II e III estão corretas. A afirmativa I erra ao afirmar que o pior caso da tabela hash é O(log n); na verdade, o pior caso é O(n) quando todos os elementos colidem para o mesmo índice. As afirmativas II e III descrevem corretamente as técnicas de encadeamento separado e endereçamento aberto, respectivamente.
A banca testa o conhecimento das características essenciais das tabelas hash: complexidade, tratamento de colisões e variantes. Vamos analisar cada item.
Afirmativa
Conteúdo
Correção
Justificativa
I
Complexidade temporal média O(1) e pior caso O(log n)
❌ Incorreto
O pior caso é O(n), quando todas as chaves colidem para o mesmo índice.
II
Tratamento de colisões com listas encadeadas (encadeamento separado)
✅ Correto
Descreve corretamente a técnica de encadeamento separado, com listas dentro ou fora da tabela.
III
Endereçamento aberto: armazenar chaves colidentes na própria tabela sem listas
✅ Correto
Descreve corretamente a técnica de endereçamento aberto, com sondagem para encontrar posições livres.
Tabela hash
1Complexidade
Médio: O(1)
Pior: O(n)
2Tratamento de colisões
Encadeamento separado
Listas externas
Listas no mesmo espaço
Endereçamento aberto
Sondagem linear
Sondagem quadrática
Duplo hash
LEVEL · soulevel.com.br
Item I — ❌ Incorreto
Afirma que o pior caso da tabela hash é O(log n). Isso está errado. Em uma tabela hash, a complexidade média de busca, inserção e remoção é O(1) graças ao acesso randômico pela função de espalhamento. Porém, no pior cenário — quando a função hash não distribui bem as chaves ou todas elas caem no mesmo bucket — as operações podem degradar para O(n), pois seria necessário percorrer todos os elementos de uma lista (ou estrutura) no bucket. O valor O(log n) é típico de árvores balanceadas (como AVL ou Rubro-Negra), não de tabelas hash.
PEGA ESSA DICA!
Na hora da prova, lembre-se: tabela hash → O(1) médio, O(n) pior caso. Árvores balanceadas → O(log n) médio e pior caso. É uma troca clássica que a banca adora explorar.
Item II — ✅ Correto
Descreve a técnica de encadeamento separado (separate chaining). Nessa abordagem, cada posição da tabela armazena um ponteiro para uma lista encadeada (ou outra estrutura) onde são colocados todos os elementos que colidiram para aquele índice. Essas listas podem ser alocadas fora da tabela (em memória dinâmica) ou compartilhar o mesmo espaço da tabela com uma estratégia de alocação própria. A descrição está correta.
Item III — ✅ Correto
Descreve a técnica de endereçamento aberto (open addressing). No endereçamento aberto, quando ocorre uma colisão, o elemento é armazenado em outra posição livre dentro da própria tabela, seguindo alguma regra de sondagem (linear, quadrática, duplo hash). Não há criação de listas externas; todos os dados ficam no próprio array da tabela. A afirmativa está correta.
Conclusão: São corretas apenas as afirmativas II e III. Portanto, o gabarito é a letra D.