Questão 163975

• Banca: FCC
• Órgão: TJ-PI
• Ano: 2009
• Provas: FCC - 2009 - TJ-PI - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Listas

Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,

• A. para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o novo nó referencie no, campo next, o nó que anteriormente era referenciado pelo nó original, desde que esse campo não tenha o valor nulo.
• B. a existência de um ponteiro apontando para o 1º elemento e outro para o fim da lista permite que a inserção ou deleção de dados de um nó que esteja no meio da lista seja rapidamente executada.
• C. enquanto a entrada que determina o topo da lista é mantida em um nó descritor dessa lista, a entrada que marca o fim da lista é mantida fora do descritor.
• D. o armazenamento de uma lista requer uma área contígua de memória para permitir a otimização no processamento de criação e remoção de nós da lista.
• E. o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.

Gabarito: E

Comentários

• Essa questão é um pouco capciosa, visto que em sua última frase comenta "Nessa estrutura," temos:

  a) confusa a inserção de um nó que não ocorre desta maneira

  b) ter um ponteiro no início e no fim não altera a velocidade de busca de um elemento no meio da lista

  c) topo está relacionado com pilhas

  d) questão correta se tratando de listas, porém a questão é sobre listas ligadas

  e) é exatamente assim que ocorre o armazenamento das lista ligadas

   

• Pessoal, achei o livro de onde a FCC copiou e colou a questão(segue link abaixo). Só não concordo com uma coisa da alternativa E: listas podem ser implementadas tanto dinâmicamente como estaticamente. Dizer que uma lista é uma estrutura dinâmica está errado(lista pode ser dinâmica seria o correto). Mesmo que a questão se refira a listas ligadas em seu enunciado, acredito que uma maneira melhor de redigir o item C seria:
  
  C: o armazenamento de uma lista não requer uma área contígua de memória. Como listas ligadas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.
  
  
  Trecho do livro:
  
  Uma lista ligada é uma estrutura que corresponde a uma seqüência lógica de
  entradas ou nós. Tipicamente, em uma lista ligada há um ou dois pontos conhecidos
  de acesso — normalmente o topo da lista (seu primeiro elemento) e eventualmente
  o fim da lista (seu último elemento). Cada nó armazena também a localização do
  próximo elemento na seqüência, ou seja, de seu nó sucessor. Desse modo, o arma-
  zenamento de uma lista não requer uma área contígua de memória.
  
  Toda a informação em um nó pode ser abstraída para dois campos de interesse: info, o conteúdo do nó, e next, uma referência
  para o próximo nó da lista. A entrada que determina o topo da lista deve ser regis-
  trada à parte da lista. Essa informação é tipicamente mantida em um nó descritor
  da lista. A entrada que marca o fim da lista não precisa de indicação especial —
  tipicamente, o ponteiro nulo como valor de next marca o final da lista.
  
  Link:
  
  
  http://www.google.com.br/url?sa=t&source=web&cd=7&ved=0CEUQFjAG&url=http%3A%2F%2Fcalhau.dca.fee.unicamp.br%2Fwiki%2Fimages%2F5%2F5b%2FCap2.pdf&rct=j&q=enquanto%20a%20entrada%20que%20determina%20o%20topo%20da%20lista%20%C3%A9%20mantida%20em%20um%20n%C3%B3%20descritor%20dessa%20lista%2C%20a%20entrada%20que%20marca%20o%20fim%20da%20lista%20%C3%A9%20mantida%20fora%20do%20descritor.&ei=keOUTdHWArS80QGaqaXqCw&usg=AFQjCNGbXSConTh0PM5xLOn82YZkVejSqw&sig2=CIk0WGDiiWEhXNJgN4Hj4A&cad=rja
  
  
• De acordo com esse trecho a letra c tb não estaria correta?  Temos a entrada que determina o topo da lista e é mantida em um no descritor (ate ai correto) e a entrada que marca o fim da lista é mantida fora do descritor (aqui tb acho que está correto já que o fim da lista não precisa de indicacao especial, conforme o trecho do livro diz, logo o fim da lista está fora do descritor)