Question

Conhecido também como re-hash, a Função de Espalhamento Duplo, ao invés de incrementar a posição do elemento até a próxima posição vazia, ela utiliza uma função de espalhamento auxiliar para calcular qual o incremento que será dado à posição, levando em consideração o valor da chave.



Na Coluna I encontra-se uma possível implementação da Função de Espalhamento Duplo com base no trecho de código abaixo. No código é apresentado alguns comentários em negrito que devem ser substituídos pelos comentários apresentados abaixo do código (Coluna II).



COLUNA I

int espalha(int chave, int N)

{
return (chave % N); /* Cálcula o índice da tabela */
}
int espalha2(int chave, int N)

{
return (1 + (chave % (N-1))); /* Cálcula o segundo índice da tabela */
}
int insere(item a[ ], item chave, int N)

{
int i = espalha(chave, N); /* Variável i recebe retorna da função */
int k = espalha2(chave, N); /* Variável k recebe retorna da 2ª função */
int cont = 0;
/* cometário A) */
while (a[ i ] != -1)

{
if (a[ i ] == chave)
return –1; /* Retorna se o elemento já existe na tabela */
if (++cont == N)
return –2; /* Retorna que a tabela está cheia */
i = ((i + k) % N); /* cometário B) */
}
/* Insere na próxima posição livre encontrada */
a[ i ] = chave;
return i;
}
int busca_espalha (item a[ ], item chave, int N)

{
int i = espalha(chave, N); /* Variável i recebe retorna da função */
int k = espalha2(chave, N); /* Variável k recebe retorna da 2ª função */
int cont = 0 ;
/* Procura a chave a partir da posição i */
while (a[ i ] != chave)

{
if (a[ i ] == -1)
return –1; /* cometário C) */
if (++cont == n)
return –2; /* Retorna que a tabela está cheia */
i = (i + k) % N; /* Calcula a função re-hash */
}
/* cometário D) */
return i;
}



COLUNA II

I - /* Busca a próxima posição livre */

II - /* Calcula a função re-hash */

III - /* Retorna que não achou a chave, pois existe uma posição vazia */

IV - /* Retorna a posição que encontrou */



Assinale a alternativa que contém a sequência correta da associação entre as colunas.

Escolha uma:
a.
Comentário A) com I ; Comentário B) com II ; Comentário C) com IV ; Comentário D) com III ;

b.
Comentário A) com I ; Comentário B) com II ; Comentário C) com III ; Comentário D) com IV ; Correto

c.
Comentário A) com II ; Comentário B) com I ; Comentário C) com III ; Comentário D) com IV ;

d.
Comentário A) com IV ; Comentário B) com II ; Comentário C) com III ; Comentário D) com I ;

e.
Comentário A) com IV ; Comentário B) com III ; Comentário C) com II ; Comentário D) com I ;

Answer 1

 Comentário A) com I ; Comentário B) com II ; Comentário C) com III ; Comentário D) com IV