PERGUNTA 3
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.
Analisando esse código, assinale a alternativa correta.
(A) A função trata todas as colisões, exceto aquelas formadas por strings s1 e s2 que são anagramas uma da outra.
(B) A função assume um cenário em que as colisões são tratadas com teste linear. Nesse caso, funcionaria sem erros na presença de colisões, apesar de ainda ser possível fazer algumas melhorias.
(C) A função assume que as chaves são números reais que podem ser mapeados em números inteiros.
(D) A função assume que strings não são palíndromos, dado que deixaria de funcionar nesses casos.
(E) 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.
PERGUNTA 4
1. Duas ideias para tratamento de colisões são o encadeamento separado e o teste linear. Sobre elas, podemos afirmar que:
(A) O teste linear é melhor que o encadeamento separado por não exigir que a função de mapeamento distribua muito bem os dados. Será possível fazer buscas em tempo constante mesmo que a função mapeie todos os registros para o mesmo endereço.
(B) O encadeamento separado é melhor que o teste linear por não exigir que a função de mapeamento distribua muito bem os dados. Será possível fazer buscas em tempo constante mesmo quea função mapeie todos os registros para o mesmo endereço.
(C) O teste linear utiliza uma região de memória adicional a ser implementada possivelmente com uma lista encadeada para tratar colisões. O encadeamento separado utiliza a região de memória da própria tabela para colocar os registros que colidiram.
(D) 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.
(E) O teste linear tende a aumentar a complexidade assintótica do algoritmo no pior caso para O(log n). Isso ocorre mesmo quando a função de hash distribui os dados uniformemente.
Soluções para a tarefa
Resposta:
(E) 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.
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.