— O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No…

Questão

— O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador, os títulos recebidos por doação foram registrados em uma lista com 128 autores, organizada em ordem alfabética pelo sobrenome. A atendente precisa localizar rapidamente o registro de Souza para verificar se há exemplar acessível em áudio. Ela não pode reorganizar a lista durante o atendimento, pois outros funcionários a consultam ao mesmo tempo. O programa deverá usar a posição dos sobrenomes na ordem alfabética para reduzir a quantidade de registros examinados, comparando o nome procurado com nomes já presentes na lista. Analise a organização da lista descrita e identifique o procedimento que permite ao programa localizar o sobrenome procurado com menos comparações.

1. A) Comparar o nome a itens escolhidos ao acaso até encontrar um sobrenome semelhante ao procurado.
2. B) Comparar o nome ao primeiro item e avançar um registro por vez até encontrá-lo ou chegar ao fim.
3. C) Comparar o nome ao item central e descartar a metade que não pode contê-lo, repetindo o processo.
4. D) Comparar o nome a todos os itens e copiar os sobrenomes anteriores para uma nova lista de consulta.
5. E) Comparar o nome aos últimos itens e trocar suas posições até que o sobrenome apareça no final.

✅ Resposta correta: alternativa C

Resolução passo a passo

1. A lista está ordenada alfabeticamente pelo sobrenome e não pode ser reorganizada. Isso significa que a posição de cada nome traz informação: se o item do meio vem antes do sobrenome procurado na ordem alfabética, todos os itens anteriores a ele também vêm antes, e a metade inicial pode ser descartada.
2. O procedimento que aproveita essa ordem é a busca binária. Compara-se o nome procurado (Souza) com o item central da lista. Se o item central for igual, a busca termina. Se Souza vier depois do item central na ordem alfabética, descarta-se a metade inicial; se vier antes, descarta-se a metade final.
3. Repete-se o processo na metade que restou, sempre dividindo o intervalo ao meio. Com 128 registros, cada comparação reduz o conjunto pela metade, de modo que em no máximo 7 comparações (2^7 = 128) o sobrenome é encontrado ou se conclui que não existe.
4. Por que as outras estão erradas: A) escolher itens ao acaso não aproveita a ordenação e pode exigir muitas comparações; B) avançar um registro por vez é a busca sequencial, que pode examinar até todos os 128 itens; D) copiar sobrenomes para outra lista gasta tempo e não reduz comparações na consulta; E) trocar posições altera a lista, o que é proibido pelo enunciado, e não localiza o nome por si só.
5. Portanto, a alternativa correta é a C, que coincide com o gabarito oficial.

💡 Dica: Pense em métodos eficientes de busca em listas ordenadas.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• — Meu protocolo de atendimento sumiu do painel! — reclamou um morador ao chegar ao posto de vacinação. A atendente…
• Uma biblioteca pública mantém um cadastro digital com 4.096 nomes de usuários, organizados em ordem alfabética. O…
• Durante a organização das inscrições para uma oficina de programação, uma escola recebeu a lista de participantes na…
• Uma cooperativa de entregas está desenvolvendo um aplicativo para conferir os itens de cada pedido. Os produtos sã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…
• Para resolver um problema de busca em uma lista ordenada, qual é a opção mais eficiente?

Todas as questões de Programação - Algoritmos clássicos