Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IF-MT 2023
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq952368
Banca
IF-MT
Órgão
IF-MT
Ano
2023
Nível
Superior
Cargo
Professor do Ensino Básico, Técnico e Tecnológico - Informática
Uma tabela de espalhamento ou hashing é uma estrutura de dados eficaz para implementar dicionários.Em relação à tabela de espalhamento, segundo Cormen (2012), analise os itens a seguir:I. O tempo médio para pesquisar um elemento em uma tabela de espalhamento é O(1).II. Quando temos mais de uma chave mapeada para a mesma posição, temos uma situação de colisão.III. A técnica mais simples para resolução de colisões é por endereçamento aberto.Está CORRETO o que se afirma em:
ANenhum dos itens é verdadeiro.
BI e II, apenas.
CII e III, apenas.
DI e III, apenas.
EI, II e III.
Revelar gabarito e comentário▾
GabaritoC — II e III, apenas.
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”.
Tabela Hash – Análise dos Itens
Gabarito: letra C. De acordo com o referencial de Cormen adotado pela banca, os itens II e III estão corretos, enquanto o item I é considerado falso. O item II define corretamente colisão; o item III aponta o endereçamento aberto como a técnica mais simples para resolução de colisões (a banca adota essa visão, embora haja debate); e o item I é tido como falso porque o tempo médio de busca depende do fator de carga e não é simplesmente O(1) em todas as situações.
NÃO CAIA NESSA!
Muitos candidatos consideram o item I como verdadeiro, porém a banca entende que a afirmação "O(1)" é imprecisa, pois o tempo médio é O(1+α) e pode variar com o fator de carga. Além disso, a afirmação sobre a técnica mais simples (item III) também gera controvérsia – embora o encadeamento separado seja frequentemente considerado mais simples, a banca adota o endereçamento aberto como resposta. Fique atento a essas nuances.
Item I – ❌ Incorreto
Afirma que o tempo médio para pesquisar um elemento em uma tabela de espalhamento é O(1). Embora para um fator de carga constante o tempo esperado seja O(1), a afirmação genérica não se sustenta, pois o tempo médio é O(1+α), onde α é o fator de carga. Em cenários com alto fator de carga, o desempenho pode degradar. Portanto, o enunciado é considerado falso pela banca.
Item II – ✅ Correto
Define corretamente o conceito de colisão: quando duas ou mais chaves diferentes são mapeadas para a mesma posição na tabela. Essa é a definição clássica e está correta.
Item III – ✅ Correto
A banca considera o endereçamento aberto como a técnica mais simples para resolução de colisões. Embora exista discussão se o encadeamento separado não seria mais simples, o gabarito oficial adota o endereçamento aberto como resposta. Logo, o item é dado como correto.
Conclusão: Estão corretos apenas os itens II e III, correspondendo à alternativa C.