Questão 769252

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

Julgue os próximos itens, relativos a tipos básicos de estruturas de dados.


O tempo de busca de um elemento em uma lista duplamente encadeada é igual à metade do tempo da busca de um elemento em uma lista simplesmente encadeada.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• A questão não pode afirmar isto, visto que, se o elemento solicitado for o primeiro, tanto em uma lista simplesmente encadeada quanto numa duplamente encadeada, o tempo será o mesmo.
• Uma lista duplamente encadeada significa que, além da informação ela possui dois ponteiros: um para o nó predecessor e outro para o sucessor. Uma lista encadeada possui apenas ponteiro para o próximo elemento. Esta característica não garante que na média, a busca em uma lista duplamente encadeada caia pela metade do tempo. Na notação big O, ambas listas possuem complexidade O(n) para buscas.

• Listas encadeadas não são otimizadas para buscar um elemento especifico. A comparação que a questão faz teria mais sentido em relação ao array

• Não! Apesar de permitir que se percorra a lista em ambas as direções, em média
  ambas possuem o mesmo tempo de busca de um elemento.
  Gabarito: E

   

  Estratégia Concursos

• ERRADO.

   

  A lista encadeada simples é percorrida em um sentido
  A lista duplamente encadeada é percorrida em ambos os sentidos. 

   

  Em relação a busca, possuem a mesma complexidade de tempo O(n), em ambas estruturas tem que se percorrer os elementos a partir do elemento incial para localizar o elemento desejado.

• Força Guerreiro!!!!!!