Questão nº 44
Questão de Tecnologia da Informação · FGV TRF1 2024 (nº 44)
Considere as afirmações a seguir.
I. Função de Hash: h(x) = x % 10 mapeia uma chave x para um
índice entre 0 e 9.
II. Operação de Módulo: % retorna o resto da divisão.
III. Colisões: quando várias chaves mapeiam para o mesmo
índice, ocorre uma colisão.
IV. Encadeamento: técnica para resolver colisões na qual cada
posição na tabela contém uma lista de chaves.
Nesse contexto, o analista Zudo está implementando um sistema
de armazenamento de dados utilizando uma tabela Hash de
tamanho 10. Ele escolhe a função de Hash h(x) = x % 10 para
mapear as chaves. Ao enfrentar o desafio das colisões, Zudo opta
pela técnica de encadeamento para gerenciá-las. Ele então insere
as chaves {15, 25, 35, 45, 55} na tabela Hash.
A estrutura final dessa tabela será:
- A[], [], [], [], [], [15], [25], [35], [45], [55];
- B[], [], [], [], [], [15, 25], [35], [45], [55], [];
- C[], [], [], [], [], [15, 25, 35, 45], [], [], [], [55];
- D[], [], [], [], [], [15, 25, 35, 45, 55], [], [], [], []; (alternativa correta)
- E[], [], [], [], [], [15, 25, 35, 45, 55], [], [], [], [55].
Resposta comentada
Gabarito Alternativa D
Uma Tabela Hash é como um armário com várias gavetas (índices), onde uma função de hash decide em qual gaveta cada item será guardado. Se duas chaves diferentes tentam ir para a mesma gaveta, ocorre uma colisão. Para resolver isso, o encadeamento faz com que cada gaveta possa guardar uma lista de itens, em vez de apenas um.
- (A) Incorreta: Esta alternativa distribui as chaves para índices diferentes (15 para 5, 25 para 6, etc.), o que não ocorre com a função para as chaves dadas.
- (B) Incorreta: Semelhante à alternativa A, ela distribui incorretamente as chaves 35, 45 e 55 para outros índices, quando todas deveriam ir para o índice 5.
- (C) Incorreta: Esta é a alternativa mais tentadora. Ela acerta ao colocar 15, 25, 35 e 45 no índice 5, mas erra ao colocar 55 no índice 9. A armadilha é um erro de cálculo para a última chave: , não 9.
- (D) Correta: A função de hash aplicada a cada chave resulta em:
Como todas as chaves mapeiam para o mesmo índice (5) e a técnica de encadeamento é usada, todas as chaves serão adicionadas à lista no índice 5. Os outros índices permanecerão vazios.
- (E) Incorreta: Esta alternativa coloca corretamente todas as chaves no índice 5, mas duplica a chave 55, colocando-a também no índice 9, o que está incorreto.
Fonte: FGV TRF1 2024 Técnico Judiciário - Desenvolvimento de Sistemas (Caderno Tipo 1). Reproduzida para fins de estudo.