Dada uma matriz grande de registros 'clientes' com campo 'cpf', qual técnica reduz o tempo de busca por um CPF…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Elaborar algoritmos que envolvam instruções sequenciais, de repetição e de seleção usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Dada uma matriz grande de registros 'clientes' com campo 'cpf', qual técnica reduz o tempo de busca por um CPF específico em comparação à varredura linear?
- A) Armazenar CPF como string
- B) Construir um índice (tabela hash/dicionário) que mapeie CPF para posição, evitando varredura linear.
- C) Ordenar a matriz primeiro
- D) Usar busca linear
- E) Dividir a matriz em partes pequenas
✅ Resposta correta: alternativa B
Resolução passo a passo
- A questão pergunta qual técnica reduz o tempo de busca por um CPF específico em uma grande estrutura de registros, em comparação com a varredura linear, que percorre todos os elementos até achar o alvo (custo proporcional ao número de registros, O(n)).
- Resolvendo por conta própria, a técnica que realmente reduz o tempo de busca é construir um índice, como uma tabela hash ou dicionário, que associa cada CPF à sua posição na estrutura. Com um índice, a busca por CPF passa a ter custo médio constante (O(1)), pois se calcula a chave e se acessa diretamente a posição, sem percorrer a lista inteira.
- Comparando com o gabarito oficial, a resposta B está correta e coincide com a minha conclusão.
- Por que as outras estão erradas:
- - A: armazenar o CPF como string muda o tipo de dado, mas não evita a varredura, então não reduz o tempo de busca.
- - C: ordenar a matriz permite usar busca binária (O(log n)), que é mais rápida que a linear, mas a ordenação em si não é a técnica de busca e tem custo próprio; a alternativa não cita a busca binária, e a resposta mais direta à pergunta é o índice.
- - D: busca linear é justamente o método de referência que a questão quer superar, então não reduz o tempo.
- - E: dividir a matriz em partes pequenas não elimina a varredura, apenas a fragmenta; sem uma forma de saber em qual parte está o CPF, continua havendo busca em todos os pedaços.
- Observação: a alternativa C também pode ser defendida como reduzindo o tempo (com busca binária), o que torna a questão ambígua, mas a alternativa B é a que descreve diretamente a técnica de acesso indexado pedida pelo enunciado.
💡 Dica: Considere as técnicas de busca em estruturas de dados.
Alternativa por alternativa
O aluno acredita que mudar o tipo do campo para texto acelera a comparação de CPFs, confundindo representação de dados com estratégia de busca.
Um índice por hash permite localizar a posição do registro em tempo médio O(1), ao passo que a varredura linear tem custo O(n).
O aluno sabe que dados ordenados facilitam a busca, mas esquece que a ordenação em si tem custo e não é a técnica de busca pedida; também pode imaginar que ordenar já basta sem a busca binária.
Por que engana: Confundir a construção de um índice com a simples ordenação da matriz, acreditando que isso já otimiza a busca.
O aluno lê a alternativa como se fosse uma solução, sem perceber que a busca linear é justamente o método que a questão pede para superar.
O aluno pensa que, ao dividir os dados em blocos menores, a busca fica mais rápida automaticamente, sem perceber que ainda precisa varrer todos os blocos.
Raio-X da questão
técnicas de busca
avaliacao
técnicas de busca · estrutura de dados
Revisar as técnicas de busca em estruturas de dados como árvores e tabelas hash.
Confundir a construção de um índice com a simples ordenação da matriz, acreditando que isso já otimiza a busca.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Dada uma matriz não ordenada de registros, qual estratégia é adequada para localizar um dado específico: varredura…
- Em um algoritmo que realiza um join entre duas matrizes de registros 'pedidos' e 'clientes' usando o campo 'cliente_id'…
- Em uma base grande de registros de alunos, qual estrutura (termo técnico) permite buscar um registro por matrícula em…
- Durante uma aula sobre sistemas de informação, o professor apresenta um caso onde um banco precisa organizar dados de…
- Num algoritmo que precisa localizar rapidamente o registro de um aluno a partir da matrícula, qual estrutura de dados é…
- Qual estrutura de dados é mais adequada para armazenar 30 registros 'cliente' (campos: nome, CPF, historicoCompras) de…
🔎 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