Question

Uma Tabela de Espalhamento pode ter seu desempenho comprometido à medida que ela vai ficando cheia. Enquanto ela possui poucos elementos, a busca é muito eficiente e rápida para qualquer tipo de Função de Espalhamento adotada.



O desempenho da tabela diminui devido à falta de posições disponíveis, ocasionando o problema lentidão e uma solução seria necessário aumentar a tabela e reinserir todos os elementos novamente, operação ineficiente para ser executada. Considerando o contexto apresentado, avalie as seguintes asserções e a relação proposta entre elas.



I - Como forma de melhorar a performance de uma Função de Espalhamento, Luiz sugeriu a implementação da tabela dinâmica na Função de Espalhamento conforme o código abaixo:


int insere_nova(item chave) {
int i = espalha(chave, NN);
/* Busca a próxima posição livre */
/* Com a tabela duplicada, sempre haverá posição disponível */
while (q[ i ] != VAZIO) {
i = (i+1) % NN; /* Cálcula o índice */
}
/* Insere na posição livre encontrada */
q[ i ] = chave;
return i;
}
void expande() {
int i, NN = 2*N;
q = malloc(NN*sizeof(item));
12
limpa(q, NN);
/* Insere todos os elementos na nova tabela */
for (i = 0; i < N; i++)
if (p[ i ] != VAZIO)
insere_nova(p[ i ]);
N = NN;
free(p);
p = q;
}
void insere(item chave) {
int i;
//Verifica se o tamanho da tabela é menor que a soma da quantidade de elementos da tabela
if (N < M+M)
expande(); /* Chama a função para expandir a tabela */
i = espalha(chave, N);
/* Busca a próxima posição livre */
while (p[ i ] != VAZIO) {
if (p[ i ] == chave)
return –1; /* Retorna se o elemento já existe na tabela */
i = (i+1) % N; /* Calcula o índice */
}
/* Insere na posição livre encontrada */
p[ i ] = chave;
M++;
return i;
}



PORQUE



II - Para melhorar o espalhamento, uma solução é a utilização de tabelas dinâmicas na estrutura ao invés de utilizar uma Lista Ligada para armazenar os valores, podendo ser utilizada tanto com a Função de Espalhamento Linear, como com a Função de Espalhamento Duplo. Assim, quando utilizamos este método, no momento em que a tabela passa de N/2 elementos, dobramos o seu tamanho, fazendo com que a tabela sempre tenha menos da metade dos elementos ocupados.



A respeito dessas asserções, assinale a alternativa correta.

Answer 1

As acerções I e II são verdadeiras e a II é a justificativa da I

Answer 2

Resposta:

Explicação:

As acerções I e II são verdadeiras e a II é a justificativa da I