Questão 163681

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2010
• Provas: CESGRANRIO - 2010 - Petrobrás - Analista de Sistemas Júnior - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Conceitos Básicos e Algoritmos; Estrutura de Dados; Listas

Uma lista simplesmente encadeada pode ser transformada em uma lista duplamente encadeada em tempo O(1)

PORQUE

Para transformar uma lista simplesmente encadeada em duplamente encadeada basta fazer uma cópia invertida de cada ponteiro (o destino do novo ponteiro passa a ser a origem do ponteiro original e vice-versa) e existe um número constante e limitado de cópias a fazer.

Analisando as afirmações acima, conclui-se que

• A. as duas afirmações são verdadeiras e a segunda justifica a primeira.
  
• B. as duas afirmações são verdadeiras e a segunda não justifica a primeira.
  
• C. a primeira afirmação é verdadeira e a segunda é falsa.
  
• D. a primeira afirmação é falsa e a segunda é verdadeira.
  
• E. as duas afirmações são falsas.

Gabarito: E

Comentários

• A primeira afirmativa é falsa, pois o correto seria O(n)
  A segunda afirmativa deveria ser correta! Eu sei que minha lista tem tamanha N. Então o número de cópias seria limitado a N-1. Alguém sabe se foi anulado?
• Se a lista tem tamanho N (um parâmetro de entrada) então não é constante.

• Concordo que a segunda afirmativa parece correta.

• Eu acredito que não seja possível transformar uma lista simplesmente encadeada em duplamente encadeada através de um procedimento seria necessário mudar a estrutura de dados então um procedimento em si não conseguiria fazer isso sozinho. Já a segunda afirmativa é um pouco duvidosa, pois não fica bem claro qual é esse ponteiro original. Na minha opinião não se poderia dizer que o ponteiro original é o ponteiro do elemento anterior vizinho que aponto para o próximo.

• Uma lista encadeada pode ser transformada em uma lista duplamente encadeada. Assim, o tempo de inserção e retirada que um item no início e no final da lista ficam constantes, O(1). Porém, para tranformar cada item simplesmente encadeado em um duplamente encadeado, a lista deve ser percorrida do iníco ao fim, sendo tranformada nessa corrida. Por isso, não é de tempo ou complexidade constante, que é o que significa O(1), mas sim de complexidade variável, O(n).
  
  Com relação a segunda, não existe um número constante de cópias a se fazer. Limitado sim, 'n'. Se fosse constante, uma lista de 10 elementos levaria o mesmo tempo de uma lista de 20 para ser transformada de simplesmente para duplamente encadeada.
  
  Espero ter ajudado!
• Na primeira, preciso percorrer toda a lista realizando as alterações necessárias, logo é O(n) (onde n é o tamanho da lista)
  
  Na segunda... gente... se preciso percorrer n elementos então não é uma constante limitada e sim uma variável, essa lista pode ter 1 elemento ou 1 milhão ou sejá lá quanto for preciso, logo o procedimento é O(n). Quando se fala em "constante", todo número constande de operações sequenciais terá complexidade O(1) pois sempre será aquele mesmo número de operações, independente do tamanho da lista passada.