Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar permite remover todas as duplicatas em tempo O(n) esperado, e qual a complexidade de espaço adicional?
- A) Usar um conjunto (hash set) para rastrear valores vistos; percorrer a lista removendo nós duplicados: tempo O(n) esperado e espaço adicional O(n).
- B) Ordenar a lista e então eliminar duplicatas: tempo O(n), espaço O(1).
- C) Usar um bitset com espaço O(1) e tempo O(n) para quaisquer valores.
- D) Remover duplicatas sem estrutura auxiliar em O(n) tempo e O(1) espaço.
- E) Construir uma árvore balanceada e deduplicar em O(n) tempo, O(n) espaço.
✅ Resposta correta: alternativa A
Resolução passo a passo
- A questão pergunta qual estratégia com estrutura auxiliar remove todas as duplicatas em tempo O(n) esperado, e qual o espaço adicional necessário.
- Resolvendo por conta própria, percorremos a lista uma única vez. Para cada nó, consultamos um conjunto (hash set) que guarda os valores já vistos. Se o valor já estiver no conjunto, o nó é duplicado e é removido ajustando um ponteiro; caso contrário, o valor é inserido no conjunto.
- Cada operação de inserção e consulta em hash set custa O(1) em média, então o tempo total é O(n) esperado. O conjunto pode conter até n valores distintos, logo o espaço adicional é O(n).
- Assim, a alternativa A descreve exatamente a estratégia e a complexidade pedidas, coincidindo com o gabarito oficial.
- A alternativa B está errada, pois ordenar uma lista ligada custa mais que O(n) (em geral O(n log n)), e o espaço não é O(1) no caso geral considerado.
- A alternativa C está errada, pois um bitset só funciona para valores inteiros pequenos e limitados, não para quaisquer valores.
- A alternativa D está errada, pois a questão exige justamente uma estrutura auxiliar; sem ela, remover duplicatas de uma lista não ordenada exige tempo quadrático.
- A alternativa E está errada, pois construir uma árvore balanceada leva O(n log n) e não há benefício de tempo O(n) para deduplicar dessa forma.
💡 Dica: Considere a utilização de uma tabela hash para armazenar elementos únicos.
Alternativa por alternativa
Ao verificar cada valor no hash set antes de manter o nó, cada elemento é processado uma vez; operações de hash são amortizadas O(1), resultando em tempo linear e necessidade de armazenar até n valores no conjunto.
Acredita que ordenar a lista é uma etapa barata e que, depois de ordenada, a remoção de duplicatas é linear e sem custo de espaço. Ignora que ordenar uma lista ligada custa O(n log n).
Por que engana: Confundir a complexidade de tempo e espaço ao usar uma abordagem ineficiente para remover duplicatas, como ordenar a lista.
Supõe que um bitset funciona para qualquer tipo de valor com espaço O(1), esquecendo que bitsets exigem valores inteiros pequenos e limitados, cujo espaço cresce com o intervalo de valores.
Acha que é possível remover duplicatas de uma lista não ordenada em O(n) sem estrutura auxiliar, pois não percebe que comparar cada nó com os anteriores exige percorrimentos repetidos, resultando em tempo quadrático.
Imagina que construir uma árvore balanceada permite deduplicar em O(n), ignorando que a construção e as inserções custam O(n log n) e que a alternativa não corresponde à estratégia de hash set pedida.
Raio-X da questão
listas ligadas e duplicatas
avaliacao
estruturas de dados · complexidade de algoritmos
Revisar conceitos de listas ligadas e estruturas auxiliares como tabelas hash.
Confundir a complexidade de tempo e espaço ao usar uma abordagem ineficiente para remover duplicatas, como ordenar a lista.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- 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 remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
- Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e remova todos os nós cujos…
- Para eliminar duplicatas de um vetor de n registros usando uma estrutura de busca baseada em hashing (conjunto), qual…
- Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de cada elemento em…
- Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
🔎 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