Questão 598453

• Banca: CESPE / CEBRASPE
• Órgão: EBC
• Ano: 2011
• Provas: CESPE - 2011 - EBC - Analista - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Listas

Acerca das estruturas de dados estáticas e homogêneas (vetores e matrizes) e das estruturas de dados dinâmicas (listas, pilhas, filas), utilizadas para armazenar conjuntos de valores, julgue os itens a seguir.

Uma lista é uma coleção de elementos do mesmo tipo dispostos linearmente, que podem ou não seguir determinada organização. As listas podem ser dos seguintes tipos: de encadeamento simples, duplamente encadeadas e ordenadas.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• Quando as listas estão ordenadas, eles estão em espaços contínuos de memória. Então pode-se utilizar algoritmos de busca como o busca binária, que consegue encontrar qualquer elemento na lista em tempo O(log2(n))
  
  Porém quando se trata de listas encadeadas, os elementos estãos dispersos na memória aleatoriamente. Quando você usa um malloc( ) em C ele procura um espaço de memória livre o suficientemente grande para alocar sua estrutura, por exemplo.
  
  Nesse caso a busca é linear e pode tomar O(n).
• Existem várias classificações em listas. A primeira é que uma lista pode ser um arranjo (array) ou uma lista encadeada. Já as listas encadeadaspodem ser dos tipos: - Simplesmente encadeadas - Duplamente encadeadas  - Circulares (simples ou dupla)  - Ordenadas. Portanto, a questão está correta em todos os conceitos apresentados. Bons estudos!

• Não seria errada por falar "do mesmo tipo"?