Para detectar duplicatas em uma matriz de registros 'dados' onde cada registro tem uma chave 'id', qual…
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
Para detectar duplicatas em uma matriz de registros 'dados' onde cada registro tem uma chave 'id', qual estrutura de dados e operação permitem identificar duplicatas em tempo médio linear?
- A) Usar um dicionário com chave duplicada
- B) Usar um vetor e ordem de inserções
- C) Usar uma lista ordenada e pesquisa binária
- D) Usar uma matriz de booleanos para cada possível id
- E) Usar um conjunto (hash set) das chaves: para cada registro, se id estiver no conjunto então é duplicata; senão inserir id no conjunto.
✅ Resposta correta: alternativa E
Resolução passo a passo
- A questão pede uma estrutura e uma operação que permitam identificar duplicatas com tempo médio linear, ou seja, o custo total deve crescer proporcionalmente ao número de registros n.
- Ao percorrer a lista de registros uma única vez, precisamos checar, para cada id, se ele já apareceu antes. Essa checagem precisa ser rápida, em tempo médio constante.
- Um conjunto implementado com tabela hash oferece inserção e pesquisa em tempo médio constante. Assim, para cada registro, verificamos se o id está no conjunto: se estiver, é duplicata; se não estiver, inserimos o id. Como são n registros, cada um com custo médio constante, o total é linear no tempo médio.
- Por que as outras estão erradas: A) um dicionário não admite chaves duplicadas, então essa ideia não serve para detectar repetições dessa forma. B) um vetor com busca sequencial exige percorrer os elementos já inseridos a cada registro, resultando em tempo quadrático. C) ordenar a lista custa tempo n log n e a pesquisa binária é logarítmica por registro, então o total não é linear. D) a matriz de booleanos tem acesso constante, mas exige que os ids sejam inteiros pequenos e de faixa conhecida, o que não é garantido por um registro com chave genérica.
- Conclusão: a alternativa correta é a E, que coincide com o gabarito oficial.
💡 Dica: Considere as estruturas de dados que permitem operações eficientes de busca.
Alternativa por alternativa
Acredita que um dicionário pode armazenar chaves repetidas e assim revelar duplicatas diretamente. Na verdade, dicionários não admitem chaves duplicadas e a repetição simplesmente sobrescreve o valor anterior.
Imagina que basta guardar os registros em um vetor na ordem de inserção e conferir, a cada novo registro, todos os anteriores. Essa busca sequencial percorre até n elementos por registro, o que leva a tempo quadrático e não linear.
Considera que a pesquisa binária é sempre rápida e esquece o custo de manter a lista ordenada. Ordenar exige tempo n log n e a pesquisa binária é logarítmica por registro, então o total não é linear.
Por que engana: Escolher uma estrutura de dados que não permite inserção e verificação em tempo linear, como listas ou matrizes.
Entende que o acesso direto a uma matriz de booleanos é suficiente para qualquer caso, sem considerar o universo de valores possíveis. Essa solução só funciona se os ids forem inteiros pequenos e de faixa conhecida, o que o enunciado não garante.
Um hash set oferece operações de inserção e consulta em tempo médio O(1), permitindo detectar duplicatas em O(n) no total.
Raio-X da questão
detecção de duplicatas
avaliacao
estruturas de dados · complexidade de algoritmos
Revisar estruturas de dados e suas operações de busca.
Escolher uma estrutura de dados que não permite inserção e verificação em tempo linear, como listas ou matrizes.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
- Em um algoritmo que processa uma lista de alunos como dados e precisa evitar registros duplicados, qual estrutura de…
- Para detectar duplicatas em uma lista de n dados, qual abordagem tem melhor complexidade média: comparar cada par…
- Projete um algoritmo em pseudocódigo que detecte e remova registros duplicados em uma matriz de dados escolares (cada…
- Em um algoritmo que deve verificar rapidamente se um código de estudante já existe em uma grande coleção de dados, qual…
- Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
🔎 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