PERGUNTA 1
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) Se uma string s for um palíndromo (mesma leitura da direita para esquerda e da esquerda para direita), então teremos uma colisão entre s e outra string que possui os mesmos caracteres de s.
(B) Se duas strings s1e s2 possuem os mesmos caracteres, então teremos uma colisão.
(C) A função é isenta de colisões no que diz respeito a strings que possuem os mesmos caracteres em qualquer ordem, independente de quem são as strings e do valor de N.
(D) 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.
(E) As palavras adriana e ariadna serão mapeadas para posições diferentes, mas orlando e odnalro serão mapeados para a mesma posição.
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) 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".
(B) A função de remoção remove o elemento que está na posição indicada pela função de hash. Isso ocorre porque as colisões são um problema a ser tratado apenas nas buscas e inserções.
(C) A função de remoção, após encontrar o elemento a ser removido, marca a posição onde ele está como "vazia".
(D) A função de remoção de uma entrada deverá procurar um elemento com chave igual ao que foi recebido por parâmetro. A busca deve ser feita usando a busca binária, iniciando na posição indicada pela função de hash.
(E) A função de remoção deve ser chamada com elementos que realmente existem na tabela, senão entrará em looping infinito.
Soluções para a tarefa
Resposta:
(D) 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.
Explicação:
10/10
Resposta: 9/10
PERGUNTA 1 *ERREI ESTA*
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.
Se internamente implementamos uma Tabela Hash como um vetor, precisaremos de uma função de mapeamentoque mapeie as chaves para inteiros, dentro dos limites estabelecidos pelo vetor.