Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg077360
Banca
FGV
Órgão
CVM
Ano
2024
Nível
Superior
Cargo
Analista - Perfil 8 - TI / Sistemas e Desenvolvimento - Tarde
Para acelerar a busca sobre uma lista de mensagens, Beatriz adotou uma tabela de dispersão, na qual o e-mail do emissor é quem define o hash.N: INTEIROV: VETOR [0..N-1] de LISTA<MENSAGEM>Algoritmo Adicionar (M: MENSAGEM)H <- 0Para i de 0 até Tamanho (M.email) - 1H <- H + Ord (M.email[i])Fim ParaH <- H Mod NV[H].Incluir(M)Fim AlgoritmoO hash é dado pelo resto da divisão entre a soma dos códigos ASCII do email e o tamanho do vetor de listas. Para que Beatriz obtenha a melhor distribuição das mensagens nas listas:
Ao valor dos códigos ASCII, obtidos pela função Ord, deve ser multiplicado por N;
Ba soma dos códigos ASCII deve ser feita do final para o início do campo email de M;
Co número N deve ser primo;
Da mensagem M deve ser incluída na lista da posição N – H do vetor V;
Eo número N precisa ser par.
Revelar gabarito e comentário▾
GabaritoC — o número N deve ser primo;
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: escolha do tamanho N
Gabarito: letra C. Para obter a melhor distribuição das mensagens nas listas, o número N (tamanho do vetor) deve ser primo. Isso porque, na função hash apresentada, o índice é calculado como (soma dos códigos ASCII) mod N. Quando N é primo, o módulo tende a espalhar uniformemente as chaves, reduzindo colisões. Se N for par ou composto, padrões comuns nos e-mails podem concentrar os hashes em poucas posições.
A banca testa o conhecimento sobre como a escolha do tamanho da tabela afeta a distribuição dos elementos. A função hash descrita é simples e a soma de caracteres ASCII é sensível a agrupamentos; usar um número primo é uma prática clássica para melhorar o espalhamento.
Alternativa A — ❌ Incorreta
Multiplicar os códigos ASCII por N antes do módulo não melhora a distribuição. Na verdade, o efeito é anulado pela operação mod N, pois (valor * N) mod N = 0 para qualquer valor que seja múltiplo de N, o que poderia gerar ainda mais colisões.
Alternativa B — ❌ Incorreta
A soma dos códigos ASCII é comutativa e associativa; percorrer o e-mail do final para o início produz exatamente a mesma soma. Portanto, a ordem não altera o hash.
Alternativa C — ✅ Correta ⟵ GABARITO
Usar N primo é a recomendação padrão em tabelas hash, especialmente quando a função é uma soma simples. Um número primo evita que divisores comuns entre a chave e N gerem padrões de distribuição ruins. Por exemplo, se N fosse par, o hash dependeria apenas da paridade da soma, causando colisões se muitas chaves tivessem soma par ou ímpar de forma similar.
Alternativa D — ❌ Incorreta
Incluir a mensagem na posição N - H apenas espelha os índices, mas não melhora a distribuição intrínseca. O mapeamento é bijetivo (cada H muda para N-H), mas o problema de distribuição permanece o mesmo.
Alternativa E — ❌ Incorreta
N par é a pior escolha. Como mencionado, a função hash baseada em soma de caracteres terá seu resultado influenciado pela paridade, concentrando os índices em metade do vetor ou gerando muitas colisões.
NÃO CAIA NESSA!
A alternativa A parece tentadora (“multiplicar por N para aumentar o espalhamento”), mas o módulo anula esse efeito. Já a alternativa C (N primo) é a técnica consagrada e nem sempre intuitiva para quem não conhece hashing.