Computação6º anoBNCC EF06CO02Difícil⏱ longo

Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF06CO02

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

Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a estrutura de dados, operações principais e a complexidade temporal e espacial.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Estrutura: tabela hash (conjunto) para chaves únicas; lista para resultado. Pseudocódigo: result ? []; seen ? HashSet(); para cada registro r em lista: chave ? extrair_chave(r) // campo(s) que identificam r; se not seen.contains(chave): seen.add(chave); result.append(r); fim se; fim para; retornar result. Operações: lookup e insert em seen (O(1) médio). Complexidade: tempo médio O(n), espaço O(n) para o conjunto e lista de saída. Observação: escolher chave que represente campos relevantes; colisões tratadas internamente pela tabela (encadeamento ou open addressing), o que pode degradar para O(n^2) no pior caso se o hash for ruim.

Explicação

A solução utiliza uma tabela hash para garantir que apenas chaves únicas sejam armazenadas, permitindo a remoção eficiente de duplicatas. A complexidade temporal média é O(n) devido à eficiência das operações de inserção e busca na tabela hash, enquanto o espaço utilizado é O(n) para armazenar tanto as chaves únicas quanto a lista de resultados. O tratamento de colisões é mencionado, o que é crucial para manter a eficiência do algoritmo em cenários adversos.

Raio-X da questão

Dificuldade Difícil

Bloom Criar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

algoritmo de remoção de duplicatas

📌 Objetivo

avaliacao

🧱 Pré-requisitos

estrutura de dados · tabela hash

📚 Reveja

Revisar conceitos de tabelas hash e complexidade de algoritmos.

⚠️ Erro mais comum

O aluno pode confundir a implementação de uma tabela hash com outras estruturas de dados, como listas ou arrays, não aplicando corretamente as operações de inserção e busca.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

abstrato

Questões parecidas com resolução

Todas as questões de Programação - Linguagem de programação

🔎 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