Em uma atividade prática, duas estratégias de busca em listas de nomes foram registradas: busca linear…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma atividade prática, duas estratégias de busca em listas de nomes foram registradas: busca linear (desordenada) e busca binária (lista ordenada). Os números de comparações para tamanhos de lista N de 8, 16 e 32 são, respectivamente, 7/3; 15/4; 31/5. Com base nesses números, qual afirmação é correta?
- A) A busca linear é mais eficiente para N=8.
- B) Para N>=16, a busca binária é a mais eficiente.
- C) Para N=32, a busca binária usa mais comparações que linear.
- D) Se a lista não estiver ordenada, a busca binária continua funcionando com a mesma eficiência.
- E) A contagem de comparações não depende do tamanho da lista.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Interprete os pares como (busca linear / busca binária), pois essa é a leitura que faz sentido com a teoria: na busca linear, no pior caso, são feitas N-1 comparações (7, 15 e 31 para N = 8, 16 e 32), enquanto na busca binária o número de comparações cresce com o logaritmo de base 2 de N (3, 4 e 5 comparações).
- Verifique a alternativa A. Para N = 8, a linear faz 7 comparações e a binária faz 3, logo a binária é mais eficiente. A alternativa está errada.
- Verifique a alternativa B. Para N = 16, a linear faz 15 e a binária faz 4; para N = 32, a linear faz 31 e a binária faz 5. A binária é a mais eficiente nesses casos, e a diferença só aumenta com N, pois a binária cresce de forma logarítmica enquanto a linear cresce de forma linear. A alternativa está correta.
- Verifique a alternativa C. Para N = 32, a binária faz 5 comparações e a linear faz 31. A binária usa menos comparações, não mais. A alternativa está errada.
- Verifique a alternativa D. A busca binária exige lista ordenada, pois ela descarta metade dos elementos comparando com o valor do meio. Em uma lista desordenada, esse critério não se sustenta e o método deixa de funcionar. A alternativa está errada.
- Verifique a alternativa E. Os dados mostram que o número de comparações cresce com N (de 7 para 15 e 31 na linear, e de 3 para 4 e 5 na binária). Logo a contagem depende do tamanho da lista. A alternativa está errada.
- Conclusão: a alternativa correta é a B, o que coincide com o gabarito oficial.
💡 Dica: Analise as comparações e identifique a estratégia mais eficiente.
Alternativa por alternativa
O aluno provavelmente inverte a leitura dos pares, atribuindo o menor número à busca linear, ou acredita que, para listas pequenas, a varredura simples compensa a binária. Não compara os números 7 e 3 com o significado de cada método.
Por que engana: Confundir a necessidade de lista ordenada para busca binaria e interpretar erroneamente o numero de comparacoes para diferentes tamanhos.
Verdadeiro: em todos os tamanhos apresentados, binária tem menos comparações que linear.
O aluno provavelmente troca a ordem dos valores do par (31/5), lendo 31 como comparações da binária e 5 como da linear, ou entende que a binária, por exigir cálculo do meio, gasta mais comparações. Assim, conclui que a binária é pior em N = 32.
O aluno acredita que a busca binária funciona em qualquer lista, como se a ordenação fosse apenas um detalhe. Ele não percebe que o descarte de metade da lista depende da ordem dos elementos.
O aluno acredita que o número de comparações é fixo ou independente do tamanho, talvez por não perceber que os valores crescem com N. Ele não relaciona os três pares de dados entre si.
Raio-X da questão
busca linear e binária
avaliacao
busca linear e binaria · analise de eficiencia algoritmica
Revisar as diferenças entre busca linear e busca binária.
Confundir a necessidade de lista ordenada para busca binaria e interpretar erroneamente o numero de comparacoes para diferentes tamanhos.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Interpretando dados de desempenho, suponha que você está avaliando o tempo médio de busca para uma lista de 1000 nomes…
- Uma escola pública brasileira criou dois algoritmos para verificar se determinado estudante está matriculado. A lista de…
- Em um teste, uma equipe executou o mesmo algoritmo de busca em listas de nomes com diferentes quantidades de itens. Para…
- Uma biblioteca pública mantém um cadastro digital com 4.096 nomes de usuários, organizados em ordem alfabética. O…
- Um professor propõe um experimento simples para comparar estruturas de dados. Ele gera 100 registros de estudantes, cada…
- Qual é a principal vantagem de usar algoritmos de busca binária sobre busca linear em listas ordenadas?
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog