Uma biblioteca pública mantém um cadastro digital com 4.096 nomes de usuários, organizados em ordem…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma biblioteca pública mantém um cadastro digital com 4.096 nomes de usuários, organizados em ordem alfabética. O sistema consegue acessar diretamente qualquer posição da lista. Para localizar um nome, o programa pode comparar o nome procurado com o elemento que está no meio do intervalo analisado: se o nome procurado vier antes, a busca continua apenas na metade inicial; se vier depois, continua apenas na metade final. Esse procedimento é repetido até que o nome seja encontrado ou se conclua que ele não está no cadastro. Com base no texto, qual técnica de programação está sendo utilizada para otimizar a busca de um nome no cadastro?
- A) Dividir repetidamente a lista ordenada ao meio.
- B) Examinar os nomes em uma ordem aleatória.
- C) Percorrer a lista inteira, elemento por elemento.
- D) Verificar simultaneamente o primeiro e o último nome.
- E) Comparar os nomes vizinhos e trocar suas posições.
✅ Resposta correta: alternativa A
Resolução passo a passo
- O enunciado descreve um cadastro com 4.096 nomes em ordem alfabética, em que o programa compara o nome procurado com o elemento do meio do intervalo.
- Se o nome procurado vier antes, a busca continua apenas na metade inicial; se vier depois, apenas na metade final. Ou seja, a cada comparação o intervalo de busca é reduzido à metade.
- Esse procedimento de dividir repetidamente o conjunto ordenado ao meio é a busca binária, técnica que aproveita a ordenação da lista para reduzir rapidamente o número de comparações.
- Por isso a alternativa A está correta, e ela coincide com o gabarito oficial.
- A alternativa B está errada, pois examinar nomes em ordem aleatória não aproveita a ordenação nem reduz o espaço de busca.
- A alternativa C está errada, pois percorrer a lista inteira elemento por elemento é a busca linear, que não é a técnica descrita.
- A alternativa D está errada, pois verificar simultaneamente o primeiro e o último nome não corresponde à divisão do intervalo ao meio descrita no texto.
- A alternativa E está errada, pois comparar vizinhos e trocar posições é característica de algoritmos de ordenação, e não de busca.
💡 Dica: Identifique o método que reduz a lista pela metade a cada comparação.
Alternativa por alternativa
A técnica descrita é a busca binária. Como os nomes estão ordenados, cada comparação com o elemento central permite eliminar metade das possibilidades. Assim, a quantidade de elementos examinados diminui rapidamente a cada etapa.
O aluno pode imaginar que, sem uma ordem fixa de exame, a busca fica mais eficiente ou que a aleatoriedade é uma forma de otimização. Ele não percebe que o texto depende justamente da ordenação alfabética para descartar metades.
O aluno pode associar 'otimizar' a percorrer tudo de forma sistemática, achando que verificar todos os elementos é a forma mais segura de encontrar o nome. Não percebe que a busca linear não reduz o intervalo a cada passo.
Por que engana: O aluno pode confundir a busca binária com a busca linear, escolhendo o percurso elemento por elemento sem considerar a divisão sucessiva da lista.
O aluno pode ter lido superficialmente a ideia de comparar com elementos da lista e confundido com uma checagem de extremos. Ele não nota que o texto fala do elemento do meio, e não das pontas da lista.
O aluno pode ter associado a busca a algoritmos de ordenação, como o bubble sort, que comparam vizinhos e trocam posições. Confunde a tarefa de organizar a lista com a tarefa de localizar um elemento nela.
Raio-X da questão
Busca binária em lista ordenada
avaliacao
Listas ordenadas e acesso direto · Estratégias básicas de busca
Revise busca binária, ordenação e divisão sucessiva do intervalo.
O aluno pode confundir a busca binária com a busca linear, escolhendo o percurso elemento por elemento sem considerar a divisão sucessiva da lista.
ciencia_tecnologia
tomada_decisao
cotidiano
Questões parecidas com resolução
- Durante uma campanha de arrecadação, uma escola receberá alimentos e produtos de higiene para montar cestas destinadas a…
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Em ações de fiscalização ambiental no Brasil, imagens de satélite podem ser comparadas em diferentes datas para indicar…
- Uma família criou um programa para organizar as compras do mês. O programa recebe os preços, soma os produtos e…
- — Sem conexão estável no rio, o alerta precisa aparecer no próprio tablet — afirmou a técnica que acompanha sons de aves…
- Falhas em formulários digitais de serviços públicos levaram um setor de tecnologia a testar cinco programas de análise…
🔎 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