Grátis: Um procedimento natural para resolver problemas de colisões consiste em guardar as chaves sinônimas em listas encadeadas. Existem duas opções: as l... – Questões Respondidas

Estrutura de Dados

Outros

Um procedimento natural para resolver problemas de colisões consiste em guardar as chaves sinônimas em listas encadeadas. Existem duas opções: as listas podem se localizar no exterior da tabela ou compartilhar mesmo espaço da tabela.
Preencha as lacunas escolhendo a alternativa CORRETA:
a. listas encadeadas; endereços; chave
b. listas encadeadas; endereços; cadeia
C. ponteiros; nós; chave
d. listas encadeadas; nós; cadeia
e. ponteiros; endereços; chave

Questões para o Sucesso

há 2 meses

Questões para o Sucesso

há 2 meses

Estruturas de Dados - COM160 - Semana 4 - Atividade Avaliativa

Estruturas de Dados - COM160 - Semana 4 - Atividade Avaliativa

UNIVESP

Respostas

Ed

há 2 meses

Para resolver problemas de colisões em tabelas hash, uma abordagem comum é usar listas encadeadas. Vamos analisar as opções: a. listas encadeadas; endereços; chave - A primeira parte está correta, mas "endereços" e "chave" não se encaixam bem no contexto. b. listas encadeadas; endereços; cadeia - Novamente, a primeira parte está correta, mas "endereços" e "cadeia" não são os termos mais apropriados. c. ponteiros; nós; chave - "Ponteiros" e "nós" são termos que se referem a estruturas de dados, mas "chave" não se encaixa bem aqui. d. listas encadeadas; nós; cadeia - Esta opção faz sentido, pois "listas encadeadas" se referem à estrutura utilizada, "nós" são os elementos da lista, e "cadeia" pode se referir à sequência de nós. e. ponteiros; endereços; chave - Embora "ponteiros" e "endereços" sejam termos relacionados, "chave" não se encaixa bem. A alternativa que melhor preenche as lacunas de forma coerente é: d. listas encadeadas; nós; cadeia.

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Estruturas de Dados - COM160 - Semana 4 - Atividade Avaliativa

Estruturas de Dados - COM160 - Semana 4 - Atividade Avaliativa

UNIVESP

Mais perguntas desse material

Dada as propriedades de estruturas de dados a seguir: Estrutura 1: estrutura que mapeia a chave de busca diretamente para um endereço de memória (endereço base). Estrutura 2: estrutura linear em que primeiro elemento a entrar tem que ser primeiro a sair. Estrutura 3: estrutura linear em que as inserções e remoções ocorrem na mesma posição.
Assinale a alternativa que apresenta, em ordem, as estruturas para as quais se referem as definições.
a. tabela hash, tabela hash, pilha, respectivamente.
b. tabela fila, pilha, respectivamente.
C. fila, tabela hash, pilha, respectivamente.
d. tabela hash, pilha, fila, respectivamente.
e. tabela hash, fila, pilha, respectivamente.

Dada as propriedades de estruturas de dados a seguir: Estrutura 1: estrutura linear em que 0 primeiro elemento a entrar tem que ser 0 primeiro a sair. Estrutura 2: estrutura que mapeia a chave de busca diretamente para um endereço de memória (endereço base). Estrutura 3: estrutura linear em que as inserções e remoções ocorrem na mesma posição.
Assinale a alternativa que apresenta, em ordem, as estruturas para as quais se referem as definições.
árvore, tabela hash, fila.
fila, tabela hash, pilha.
grafo, fila, tabela hash.
pilha, grafo, fila.
pilha, vetor ordenado, fila.

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.
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

Tabelas 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 afirmacoes: 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