Existe uma estrutura de dados que permite inserção, remoção e busca de dados em tempo constante, no melhor caso. É o caso das Tabelas Hash, também conhecidas como Tabelas de Dispersão ou Escrutínio.
Com base em seus conhecimentos a respeito de Tabelas de Dispersão, avalie as afirmações a seguir.
I - A função h(x) = x*x % 10, aonde o caractere % indica o resto da divisão inteira, pode ser considerada uma função hash adequada para uma tabela de 10 elementos.
II - O conceito de colisão em Tabelas Hash podem ser tratados por meio de tecnicas que envolvam listas encadeadas.
III - Em certos momentos, quando ocorre uma colisão, pode ser necessário realizar uma busca sequêncial pela tabela.
Dessa forma é correto o que se afirma em:
Alternativas
Alternativa 1:
I, apenas.
Alternativa 2:
I e II, apenas.
Alternativa 3:
I e III, apenas.
Alternativa 4:
II e III, apenas.
Alternativa 5:
I, II e III.
Respostas
Resposta:
marquei II e III n achei nada sobre a primeira alternativa no livro
Explicação:
pg 147 livro
II- Outro método de solução de colisões consiste em combinar o caráter estático de vetores com o potencial de alocação dinâmico dos ponteiros. Assim, caso haja uma colisão, podemos “pendurar” mais elementos naquela posição do vetor de maneira dinâmica. Ou seja, o vetor passa a ser uma tabela na qual cada posição do vetor pode dar origem a uma lista encadeada distinta.
pg 146 livro
III- Todavia, nosso algoritmo sabe que pode ter havido alguma colisão. Por isso, a busca continua sequencialmente, verificando se existe algum elemento posterior ao 72 que seja igual ao 88.
Sabendo os conceitos de tabelas de dispersão, pode-se afirmar que realizando a interpretação correta, temos que:
- I - a função h(x) = x*x % 10 pode ser considerada uma função de hash adequada;
- II - a colisão de hash pode ser tratada pro meio de técnicas que envolvam listas;
- III - pode ser necessário realizar uma busca sequencial na tabela após uma colisão.
Portanto, conclui-se que a alternativa correta que deve ser assinalada é a alternativa 5.
O que é uma tabela de dispersão?
Para a ciência da computação a tabela de dispersão é uma estrutura especial, na qual os dados se associam por chaves de pesquisa a valores. O principal objetivo é que a partir de uma chave simples possa se fazer uma busca rápida e eficiente para obter o valor desejado. Atualmente as duas funções mais utilizadas nesta tabela é a de registros de dados (consultas unidirecionais simples) e validação de dados.
Saiba mais sobre a tabela de dispersão em:
brainly.com.br/tarefa/24845855
#SPJ2
