Questão 1470832

• Banca: UNIRIO
• Órgão: UNIRIO
• Ano: 2014
• Provas: UNIRIO - 2014 - UNIRIO - Analista Tecnologia da Informação - Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Listas

Seja Lo uma lista ordenada e Lno uma lista não ordenada, ambas com 100 elementos. Os números de comparações, no pior caso, quando aplicando uma busca binária em Lo e uma busca sequencial em Lno são, respectivamente,

• A. 7 e 100.
• B. 50 e 100.
• C. 7 e 1.
• D. 50 e 1.
• E. 50 e 50.

Gabarito: A

Comentários

• Lo (ordenada) 

   

  Comparações:

  1- 100 / 2 = 50

  2- 50 / 2 = 25

  3- 25 / 2 = 13 (não dividimos em números quebrados)

  4- 13 / 2 = 7

  5- 7 / 2 = 4

  6- 4 / 2 = 2

  7- 2 / 2 = 1

   

  Lo: 7 comparações

   

  Lno (não ordenada): O pior caso será percorrer todos os elementos e, ou o elemento desejado estar na última posição, ou não ser encontrado. Ou seja:

   

  Lno: 100 comparações

• Força Guerreiro!!!!!!