Algoritmos clássicos

• a)Olhamos o primeiro elemento
• b)Comparamos com o elemento do meio e descartamos metade da lista
• c)Olhamos todos os elementos
• d)Embaralhamos a lista

Resposta: b) Por isso a busca binária é muito rápida, mas exige lista ordenada.

• a)100 comparações
• b)10 comparações
• c)500 comparações
• d)1 000 comparações

Resposta: b) 2¹⁰ = 1024: dividindo pela metade cerca de 10 vezes chegamos a um único nome.

• a)Não compara elementos
• b)Embaralha até ficar ordenado
• c)Troca só o primeiro e o último
• d)Encontra o menor elemento e o coloca na primeira posição, depois repete com o restante

Resposta: d) A cada passada, seleciona o menor dos que faltam.

• a)[5, 3, 1, 8]
• b)[1, 3, 8, 5]
• c)[3, 5, 8, 1]
• d)[1, 3, 5, 8]

Resposta: b) O menor (1) troca de lugar com o primeiro (5).

• V F A busca sequencial funciona em listas não ordenadas.
• V F A busca binária funciona em qualquer lista, ordenada ou não.
• V F Organizar cartas na mão, encaixando cada carta no lugar certo, lembra a ordenação por inserção.
• V F Algoritmos diferentes podem resolver o mesmo problema com quantidades diferentes de passos.

Resposta: V, F, V, V. Sem ordenação, descartar metade da lista não é possível.

Resposta esperada: Passadas: [1, 2, 9, 4, 7] → [1, 2, 9, 4, 7] → [1, 2, 4, 9, 7] → [1, 2, 4, 7, 9]. Ordenar permite usar a busca binária, que é muito mais rápida quando se fazem muitas buscas.