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
- Uma escola guarda os números de matrícula em um vetor ordenado. Para encontrar uma matrícula, o programa pode comparar o…
- Em uma lista ordenada com muitos nomes, a busca olha o nome do meio e elimina metade da lista a cada passo. Qual é o…
- — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
- Uma cooperativa de entregas está desenvolvendo um aplicativo para conferir os itens de cada pedido. Os produtos são…
- Para resolver um problema de busca em uma lista ordenada, qual é a opção mais eficiente?
- Uma equipe de uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está quase…
🔎 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