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
- Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
- No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
- O clube de jogos da escola vai usar um programa simples para registrar cada participante. Em cada cadastro, a pessoa…
- Na horta da escola, uma estação simples registra a temperatura informada por um sensor. O programa deve mostrar essa…
- Pesquisadores acompanham o funcionamento de um robô que cuida de seis placas solares em uma estação de pesquisa. O robô…
- Por que alguns tablets de um centro cultural aparecem como disponíveis, embora estejam guardados para conserto? Para…
🔎 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