COM160 - OBJETO EDUCACIONAL SEM4

Prévia do material em texto

OBJETO EDUCACIONAL
Pergunta 1
Questão referente ao Texto-base: Estruturas de dados e seus algoritmos (Leia as páginas 232
a 250) | Jayme Luiz Szwarcfiter e Lilian Markezon
O tratamento de colisões usando listas encadeadas fora do vetor é uma solução muito usada.
Sobre esse mecanismo de tratamento de colisões, assinale a alternativa correta.
✅ É usual efetuar-se a inclusão dos elementos no final da lista encadeada
correspondente à função de hash de sua chave, dado que a lista precisaria ser
percorrida de qualquer maneira para garantir que a chave já não estava na lista
antes.
 Para remover o elemento de uma tabela hash quando o tratamento de colisões é feito
externamente por listas encadeadas, precisamos procurar na lista encadeada
correspondente à função de hash de sua chave. Se o elemento não for encontrado,
procuramos na lista encadeada seguinte, e assim por diante, até encontrar o elemento.
 Uma desvantagem da utilização de listas encadeadas é que o número de elementos na
tabela hash deverá ser fixado em tempo de compilação, não sendo possível inserir
novos elementos na estrutura quando o espaço alocado se esgotar.
 Quando temos chaves sinônimas, isto é, chaves em que a função de hash mapeia para
o mesmo endereço, alocamos os elementos em listas encadeadas diferentes para
garantir que a busca por uma chave ocorrerá no menor tempo possível.
 A utilização de listas encadeadas para tratamento de colisões permite a
implementação de tabelas hash sem a necessidade de estudar o fator de carga, dado
que este se torna irrelevante por podermos inserir e remover elementos em tempo
constante de listas encadeadas.