Estruturas de Dados - COM160 - Semana 4 - Atividade Avaliativa

Prévia do material em texto

A tentativa linear h(x,k) é uma implementação muito simples, em que endereço-base X é h'(x) (k=0), suponhamos que existe outra chave, ocupando mesmo endereço de h'(x). A ideia da tentativa linear é buscar armazenar um novo nó, no endereço próximo, que consiste em h'(x) + 1 (k=1), se por acaso já estiver ocupado, ele irá tentar em h'(x) + 2 (k=2), e assim sucessivamente. Com base nos aspectos que existem no método de tentativa linear, assinale a alternativa que descreve a função da tentativa linear para a (k+1)-ésima tentativa. a. h(x, k) (h'(x) k+1) mod m b.h(x, k) (h'(x) + k) mod m, 0 ≤ m C. h(x, k+1) (h(x, + k) mod m, 0 m d.h(x, k) k+1) mod m 0Uma tabela recebe chaves do tipo string e armazena 05 dados internamente como um vetor. A função de espalhamento da tabela Hash utiliza 0 seguinte procedimento para mapear as strings em inteiros: 1 Mapeamento de caracteres: 05 três primeiros caracteres são mapeados em inteiros da forma: De a até f: mapeado para 1 De g até m: mapeado para 3 De até mapeado para 5 De t até mapeado para 7 2 Os inteiros associados a cada um dos três primeiros caracteres são multiplicados entre si. 3 resto da divisão por 11 è computado, dado que vetor possui tamanho 11. Dadas as seguintes strings: ULISSES, DANIELLE e aplicando a função de espalhamento apresentada, indique a alternativa correta que apresenta a string e a posição obtida. 8 danielle 5 larissa 4 danielle 3 larissa 2 = 1 danielle 2 larissa 6 6 danielle 5 larissa 1 4 danielle 8 larissa 3 Uma tabela hash recebe como chave valores inteiros. Internamente, a tabela hash foi implementada como um vetor de tamanho 13, com elementos indexados de 0 a 12. Para tratamento de colisões, é usado teste linear. Vamos assumir que a seguir temos uma tabela hash obtida após algumas operações de inserção. 52 -1 28 -1 -1 -1 58 98 99 -1 -1 -1 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 Note que "-1" indica uma posição vazia. Dito isso, assinale a alternativa correta. Observando a configuração atual da tabela hash, podemos concluir que apenas uma colisão ocorreu, dado que apenas um elemento está posicionado em lugar diferente daquele indicado pela função de espalhamento. Se removermos 98 e depois inserirmos elemento 15, este último ficará na posição 7. Se tentarmos inserir elemento 24, criaremos uma colisão com 0 elemento 52, sendo que esta colisão será tratada pelo teste linear adicionando 24 na posição 1. Se inserirmos elemento 60, ele será fisicamente colocado exatamente na posição indicada pela função de espalhamento. Se quisermos inserir elemento 20, ele será mapeado pela função de espalhamento para a posição onde está elemento 98. Nesse caso, teste linear tentaria colocar na posição seguinte, que também está ocupada pelo elemento 99, restando então colocar o elemento 20 na posição 9, que está livre.Com chaves diferentes é possível encontrar mesmo endereço-base, esse problema podemos denominar como colisão. Um método para diminuir esse problema de colisões é diminuir fator de carga, e à medida que fator carga aumenta, a possibilidade de dar colisões também aumenta. Com isso, as tabelas de dispersão atendem necessariamente a esse problema, que é a previsão de algum método de tratamento de colisões. Uma ideia simples para resolver a questão de colisões é realizar procedimento para que cada endereço seja um para uma lista encadeada. As colisões acontecem quando são(é) iguais(I), impedindo diretamente a inserção de um novo elemento. Para resolver isso, é possível utilizar um espaço de ou um espaço no próprio vetor. Preencha as lacunas escolhendo a alternativa CORRETA. a. ponteiro; dado; memória adicional b. elemento; dado; locação de espaço ponteiro; duas chaves; memória adicional d. elemento; dado; memória adicional e. elemento; duas chaves; locação de espaço Uma tabela recebe chaves do tipo string e armazena os dados internamente como um vetor. A função de espalhamento da tabela Hash utiliza seguinte procedimento para mapear as strings em inteiros: 1 Mapeamento de caracteres: três primeiros caracteres são mapeados em inteiros da forma: De a até f: mapeado para 1 De g até n: mapeado para 3 De 0 até mapeado para 5 De t até z: mapeado para 7 2 - Os inteiros associados a cada um dos três primeiros caracteres são multiplicados entre si. 3 - - O resto da divisão por 11 é computado, dado que o vetor possui tamanho 11. Dadas as seguintes strings: ULISSES, DANIELLE e aplicando a função de espalhamento apresentada, indique a alternativa correta que apresenta a string e a posição obtida. a. h(ulisses) = 8 h(danielle) = 3 h(larissa) = 4 b.h(ulisses) = 5 h(danielle) = 5 h(larissa) = 4 C. h(ulisses) = 8 h(danielle) = 3 h(larissa) = 5 d.h(ulisses) = 8 h(danielle) 4 h(larissa) 5 e. h(ulisses) = 8 h(danielle) = 5 h(larissa) = 4Tabelas hash são tão importantes em programação que muitas linguagens já oferecem essa estrutura de dados implementadas por padrão na própria linguagem, enquanto outras fornecem a implementação em bibliotecas, as quais você adiciona no seu código usando comandos como "import" ou Diante do apresentado, assinale a alternativa correta que descreve a função da tabela hash. a. Converter qualquer tipo de código em C + +, pois essa linguagem é a única que pode ser utilizada em qualquer programa. b. Mapear a chave de busca para um endereço de memória, usando a função chamada de "função de C. Otimizar buscas ao separar códigos por linhas, facilitando a busca dos comandos do código. d. Separar colunas de códigos, pois assim é possível que 0 programador consiga incluir comandos repetidos no código sem repetir na mesma linha. e. Analisar códigos para que possam ser executados sem erros, baseados nas tabelas hash implementadas. As tabelas hash minimizam a complexidade de tempo para as operações dinâmicas como Inserção, Remoção, Busca e Modificação. Admita as seguintes afirmações: A função hash(chave) deve ser determinística. Para uma determinada chave, a função sempre retorna 0 mesmo valor de hash. II. Por ser utilizada como uma função de indexação, a função de hash deve sempre retornar um valor de hash dentro dos limites da tabela [0,N-1], em que Né tamanho da tabela. III. O método aproveita a possibilidade de acesso randômico à memória para alcançar uma complexidade média por operação de sendo pior caso, entretanto, O(n). Assinalar a alternativa correta: Apenas as alternativas e são verdadeiras. Apenas as alternativas II, III são verdadeiras. Todas as alternativas e são verdadeiras. Apenas as alternativas e III são verdadeiras. Apenas a alternativa II é verdadeira. As tabelas hash podem ser acessadas ao longo do tempo para que possam ser organizadas na memória como arrays. As chaves podem ser de qualquer tipo de dados, mas as pesquisas de matriz exigem uma função que mapeia as chaves para números inteiros. Com base nesses aspectos, assinale a alternativa que descreve a função que mapeia chaves em números inteiros. a. Função de espalhamento b. Função de tempo constante C. Função de encadeamento d. Função de vetorização e. Função de colisão Seja uma tabela hash implementada como um vetor de tamanho 13, com elementos indexados de 0 a 12. Nesse caso, para obter a posição a partir de uma chave, a função de espalhamento computa resto da divisão da chave por 13. Indicar a alternativa correta que apresenta a chave (93,2,24) e o índice resultado da função de espalhamento aplicada a essa chave. a.h(93)=2 h(2)=2 h(24)=2 b.h(93)=2 h(2)=2 h(24)=11 C. h(93)=1 h(2)=2 h(24)=11 d. h(93)=2 h(2)=3 h(24)=11 e. h(93)=1 h(2)=3 h(24)=11