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.

Question

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.

Answer 1

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.Dicas: A função de hash mencionada na questão, pelo uso da representação numérica de cada caractere da string em uma posição específica, evita que strings sejam mapeadas para o mesmo valor hash mesmo quando contêm os mesmos caracteres em diferentes ordens. Esta é uma estratégia para minimizar a colisão de hash, que é uma situação em que diferentes entradas produzem o mesmo valor hash.Descrição: Nesta função, cada caractere da string é mapeado para um valor numérico baseado na tabela ASCII usando uma constante 'a' e um valor 'N', que é o número máximo de elementos na tabela. O valor do hash é calculado com a soma dos produtos dos valores ASCII de cada caractere e 'a' elevado à potência correspondente à posição do caractere na string, tudo modulado pelo valor 'N'. Isto garante que a ordem dos caracteres na string afeta o valor do hash, permitindo a discriminação de anagramas.Resposta: Portanto, a afirmação que está correta é: (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.

Question

Solution

Resposta