Questão 273352

• Banca: CESPE / CEBRASPE
• Órgão: FUB
• Ano: 2011
• Provas: CESPE - 2011 - FUB - Analista de Tecnologia da Informação - Específicos
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

Julgue os próximos itens em relação às estruturas de dados.

No uso de estruturas de transformação de chave (hashing), a solução de colisões usando encadeamento tem como principal característica o fato de nunca transbordar. Adicionalmente, o tempo de busca na lista ligada pode ser reduzido se uma lista duplamente encadeada for utilizada.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• Uso da posição consecutiva livre:
  • Os elementos que colidem são armazenados em posições da tabela ainda não ocupadas;
  • Uma das estratégias consiste em buscar a próxima posição livre (utilizando incremento circular):
  
  Usa-se somente um a Lsta Encadeada
• Se eu quiser eu posso utilizar uma lista duplamente encadeada no meu hashing. Mas isso significa aumento do gasto de memória para armezenar 1 ponteiro a mais desnecessário. O erro da questão está em dizer que "Adicionalmente, o tempo de busca na lista ligada pode ser reduzido se uma lista duplamente encadeada for utilizada." 
  
  
  A complexidade temporal para a busca de um elemento numa lista encadeada é(em termos assintóticos) a mesma se comparada com uma lista duplamente encadeada. O(n) no tamanho da lista.
• Um método alternativo citado por Wirth é o método de endereçamento aberto. 

• (ERRO EM VERMELHO) No uso de estruturas de transformação de chave (hashing), a solução de colisões usando encadeamento tem como principal característica o fato de nunca transbordar. Adicionalmente, o tempo de busca na lista ligada pode ser reduzido se uma lista duplamente encadeada for utilizada.

   

  ---> Tanto lista encadeada quanto lista duplamente encadeada possuem A MESMA COMPLEXIDADE, portanto o tempo não pode ser reduzido na lista duplamente encadeada.