Logo Passei Direto
Buscar

Estrutura de Dados

Instituto Menna Barreto
Com relação a tabela hashing implementada com endereçamento aberto, avalie as seguintes afirmativas. I. Nesse tipo de implementação, a tabela hashing é um vetor de m posições com todas as chaves armazenada em espaços extras ou ponteiros. II. Nesse tipo tabela hashing, as posições que se encontram vazias são utilizadas para minimizar as colisões. III. A ocupação de uma posição vazia não pode ser realizada. IV. Através de tentativa linear, caso a chave inserida gere uma colisão, a função utilizada para obter um novo endereço tem o seguinte perfil: h’ (x) = (h (x) + j) mod m, para 1≤ j≤m-1, sendo h (x)=x mod m. Sobre as afirmativas acima, assinale a alternativa correta. Clique na sua resposta abaixo II e IV. III, II e IV. II e I. II e I. IV e III.
User badge image
Cida

mês passado

Respostas

User badge image

Ed Verified user icon

mês passado

Vamos analisar cada afirmativa sobre tabela hashing com endereçamento aberto: I. "Nesse tipo de implementação, a tabela hashing é um vetor de m posições com todas as chaves armazenadas em espaços extras ou ponteiros." Incorreto. No endereçamento aberto, todas as chaves são armazenadas diretamente no vetor, sem uso de espaços extras ou ponteiros. O vetor tem tamanho m e as colisões são resolvidas procurando outras posições dentro do próprio vetor. II. "Nesse tipo tabela hashing, as posições que se encontram vazias são utilizadas para minimizar as colisões." Correto. No endereçamento aberto, as posições vazias são usadas para armazenar chaves que colidiram, buscando uma nova posição livre. III. "A ocupação de uma posição vazia não pode ser realizada." Incorreto. O objetivo do endereçamento aberto é justamente ocupar posições vazias para resolver colisões. IV. "Através de tentativa linear, caso a chave inserida gere uma colisão, a função utilizada para obter um novo endereço tem o seguinte perfil: h’ (x) = (h (x) + j) mod m, para 1 ≤ j ≤ m-1, sendo h (x) = x mod m." Correto. Essa é a definição clássica da sondagem linear para tratamento de colisões. Portanto, os itens corretos são II e IV. A alternativa correta é: II e IV.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

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

Mais conteúdos dessa disciplina