Conhecido também como re-hash, a Função de Espalhamento Duplo,...

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.