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
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
algoritmo de remoção de duplicatas
avaliacao
estrutura de dados · tabela hash
Revisar conceitos de tabelas hash e complexidade de algoritmos.
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.
ciencia_tecnologia
pensamento_critico
abstrato
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