Question

uma função de mapeamento de strings para inteiros pontua as vogais como: a = 1, e = 3, i = 5, o = 7, u = 9. todos os outros caracteres são pontuados com 0 (zero). um inteiro que representa a string é computado com a soma das pontuações dos caracteres. quantas colisões ocorrem se tivermos as palavras: ulisses, arthur, danielle, christina, paula. considere que as duas palavras possuem o mesmo valor de hash, então isso corresponde a uma colisão.

Answer 1

Resposta:

1. Sobre Tabelas Hash, é possível afirmar que:    

Uma Tabela Hash difere dos vetores porque na Tabela Hash temos índices do tipo string e valores do tipo inteiro, enquanto nos vetores temos índices do tipo inteiro e valores do tipo string.  

Em uma Tabela Hash implementada como vetor, o tamanho do vetor não costuma interferir na presença de colisões, a não ser que algum erro de projeto tenha sido cometido pelos desenvolvedores.  

Se internamente implementamos uma Tabela Hash como um vetor, precisaremos de uma função de mapeamento que mapeie as chaves para inteiros, dentro dos limites estabelecidos pelo vetor.  

Em uma Tabela Hash, cada entrada é do tipo (k,v), onde a chave k precisa ser do tipo inteiro e v pode receber qualquer tipo <------ INCORRETA

A implementação de uma Tabela Hash faz com que as buscas ocorram em tempo constante. As deleções e inserções ocorrem em tempo O(log n) .  <--------- INCORRETA

PERGUNTA 2

1. Sobre o teste linear para tratamento de colisão em uma tabela hash, assinale a alternativa correta sabendo que posições na implementação interna do vetor podem estar "ocupadas", "vazias" ou "disponíveis".  

A função de busca de um elemento procura a chave de entrada, inicialmente na posição indicada pela função de hash, mas, caso ela esteja ocupada por outra entrada, inicia uma busca sequencial nas posições seguintes e só pára quando encontrar o elemento, ou quando encontrar uma posição "vazia".

PERGUNTA 3

1. Uma função de mapeamento de strings para inteiros pontua as vogais como: a = 1, e = 3, i = 5, o = 7, u = 9. Todos os outros caracteres são pontuados com 0 (zero). Um inteiro que representa a string é computado com a soma das pontuações dos caracteres. Quantas colisões ocorrem se tivermos as palavras: ulisses, arthur, danielle, christina, paula.

RESPOSTA :    1

 

PERGUNTA 4

1. Duas ideias para tratamento de colisões são o encadeamento separado e o teste linear. Sobre elas, podemos afirmar que:  

O encadeamento separado utiliza uma região de memória adicional a ser implementada possivelmente com uma lista encadeada para tratar colisões. O teste linear utiliza a região de memória da própria tabela para colocar os registros que colidiram.  

 

PERGUNTA 5  

1. Sobre tratamento de colisões, é correto afirmar que:  

 Tratar colisões significa que, no caso de ocorrência de colisões, um dos registros ficará em um segundo endereço de memória, que também será analisado em caso de busca, atualização e remoção do registro.  

 

PERGUNTA 6

1. Sobre Função de Hash, é possível afirmar que:  

Uma boa função de hash é aquela que diminui o número de colisões, o que permite inserções, remoções e atualizações de maneira eficiente.

PERGUNTA 7

1. Sobre o teste linear para tratamento de colisão em uma tabela hash, assinale a alternativa correta sabendo que posições na implementação interna do vetor podem estar "ocupadas", "vazias" ou "disponíveis".  

A função de remoção de uma entrada deverá procurar um elemento com chave igual ao que foi recebido por parâmetro. Encontrado o elemento, marca a posição como "disponível".  

PERGUNTA 8

1. Um código em C++ das funções insertItem e deleteItem de uma implementação de tabela hash é mostrado a seguir.A função insertItem insere o objeto "aluno" que veio por parâmetro e a função deleteItem remove um registro na posição indicada pela função de hash aplicada ao objeto "aluno" que veio por parâmetro.

IMAGEM :

Analisando esse código, assinale a alternativa correta  

Em caso de colisão, a função deleteItem pode apagar um aluno com chave diferente daquele passado por parâmetro.

PERGUNTA 9

1. Uma função de hash para mapeamento de strings em inteiros usa a tabela ascii para mapear cada caractere da string em um número. Seja C = (c0,c2,c3,...,ck-1) os valores numéricos dos caracteres nas posições 0,1, ... k-1, a função é dada por.

(c0ak-1 + c1ak-2 + c2ak-3 + ... + ck-2a1 + ck-1) mod N

Onde a é uma constante qualquer e N é o número máximo de elementos na tabela.

Sobre essa função, é correto afirmar que.  

A função tenta evitar colisões entre strings s1e s2 que são anagramas uma da outra. Isso permite distribuir mais adequadamente as strings na tabela hash se comparada com uma função que não leva em conta as posições dos caracteres

PERGUNTA 10

1. Um código em C++ da função retrieveItem de uma implementação de tabela hash é mostrado a seguir. Este código busca um elemento no vetor "structure" usando uma chave de busca presente na variável "aluno" recebida como parâmetro. Esse mesmo parâmetro "aluno" é usado para retornar o conteúdo da tabela Hash.

IMAGEM:  

Analisando esse código, assinale a alternativa correta.  

A função funcionaria se assumirmos um cenário ideal em que as colisões não existem. Nesse caso, precisa ainda ser adaptada se quisermos que funcione em cenários com colisões.

Espero que tenha ajudado!!