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. Escolha uma: a. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. b. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. c. As asserções I e II são proposições falsas. d. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. e. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. Correto,

Answer 1

Resposta - As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

Answer 2

Correto é letra: e. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.