Questão 464167

• Banca: CESGRANRIO
• Órgão: Transpetro
• Ano: 2011
• Provas: CESGRANRIO - 2011 - Transpetro - Analista de Sistemas Júnior
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca; Estrutura de Dados; Listas

Uma lista linear ou uma tabela é um conjunto não vazio de nós, tais que suas propriedades estruturais decorrem unicamente da posição relativa dos nós dentro da sequência linear. Considerando-se as diferentes listas lineares, tem-se que

• A. a complexidade de pior caso do algoritmo de busca em uma lista sequencial ordenada é menor do que em uma lista sequencial não ordenada.
• B. a alocação sequencial de listas é menos eficiente em tempo do que a alocação encadeada quando se deseja o acesso ao k-ésimo elemento da lista.
• C. se os nós consecutivos da lista estão em posição relativa sempre contígua, a lista usa alocação encadeada.
• D. na alocação dinâmica, os nós de uma lista estão aleatoriamente dispostos na memória.
• E. numa busca binária em uma tabela ordenada, o número máximo de iterações é onde n é o tamanho da lista.

Gabarito: D

Comentários

• A letra 'e' está errada pois a questão afirma que o número máximo de iterações é log₂n  sendo que na verdade esse é sua complexidade algoritmica que é O( log₂n ) o que não implica que o algorítmo executa  log₂n  passos é sim que seu trabalho cresse nessa ordem de grandesa. que é um número aproximado.
• a) a complexidade de pior caso do algoritmo de busca em uma lista sequencial ordenada é menor do a mesma que em uma lista sequencial não ordenada.
  
  b) a alocação sequencial de listas é menos mais eficiente em tempo do que a alocação encadeada quando se deseja o acesso ao k-ésimo elemento da lista.
  
  c) se os nós consecutivos da lista estão em posição relativa sempre contígua, a lista usa alocação encadeada sequencial.
  
  d) na alocação dinâmica, os nós de uma lista estão aleatoriamente dispostos na memória.
• Apesar da explicação no primeiro comentário. Ainda não ficou claro para mim a razão da "E" está errada. Agradeço muito se alguém comentar.
• para o erro da letra, basta pensar no caso de n =4.
  
  O log2 de 4 é 2. Ou seja, esse deveria ser o maximo de iterações para achar um elemento.
  
  Considere o vetor [1,2,3,4].
  
  Na primeira iteração, ele deveria bucar o elemento 2,5. Como nao existe elemento quebra, ele trunca e busca o segundo elemento. E nao acha o elemento.
  Na segunda iteração, ele pega o vetor direito restante [3,4] e tenta pegar o elemento 1,5 dele, como nao tem, ele busca o primeiro elemento deste subvetor(3)
  Na terceita iteração, só resta o subvetor [4], ele busca e acha o elemento.
  
  Logo foram feita 3 iterações e não 2.
  
  
• Hein? Alguém consegue apontar UM caso onde a busca em uma lista ordenada tem complexidade igual ou pior do que a busca em uma lista não ordenada (como diz a letra A)?
  
  Não entendi.

• 3No item (e), "lista linear" ou "tabela" é um conceito abstrato de estrutura de dados que independe da sua implementação. A afirmativa seria verdadeira apenas para implementações que fazem uso de alocação contígua de memória (como arrays ou vetores). Para implementações de "tabelas" ou "listas sequenciais" que façam uso de alocação encadeada (como listas encadeadas), a afirmativa seria falsa.
  

• (a) a complexidade de pior caso do algoritmo de busca em uma lista sequencial ordenada é menor ou igual do que em uma lista sequencial não ordenada.

  Erro do item: a complexidade será O(n) para ambas as listas se a busca for sequencial.

  
  

• A letra E tá errada pq o número de iterações é aproximadamente lg (n)