Descreva um algoritmo generalizado (inclua assinatura e pseudocódigo) que receba duas coleções de registros e…
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
Descreva um algoritmo generalizado (inclua assinatura e pseudocódigo) que receba duas coleções de registros e um parâmetro 'chave' para combinar registros (join). Explique como tratar registros sem correspondência e estime a complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Assinatura: join(colecaoA: List<Record>, colecaoB: List<Record>, chave: String, includeUnmatched: Bool) -> List<Record> Pseudocódigo (hash-join): mapa <- novo dicionário para cada r em colecaoA: if r[chave] existe then mapa[r[chave]] <- mapa[r[chave]] ? [r] resultado <- lista vazia para cada s em colecaoB: chaveS <- s[chave] se chaveS existe em mapa: para cada r em mapa[chaveS]: resultado.adicionar(combinar(r,s)) senao se includeUnmatched: resultado.adicionar(combinar(null,s)) se includeUnmatched: para cada entradas em mapa sem correspondência: resultado.adicionar(combinar(r,null)) Tratamento de chaves ausentes: optar entre pular registros ou incluir pares com null conforme parâmetro includeUnmatched; registrar erros quando chave obrigatória estiver faltando. Complexidade: com tabela hash, tempo esperado O(n + m) e espaço O(n) (n = |colecaoA|, m = |colecaoB|). Alternativa ingênua (forças brutas) tem custo O(n·m).
Explicação
O algoritmo apresentado utiliza uma abordagem eficiente de hash-join, que permite combinar registros de duas coleções com base em uma chave, garantindo que a busca por correspondências seja rápida. A inclusão do parâmetro 'includeUnmatched' permite flexibilidade no tratamento de registros sem correspondência, permitindo ao usuário decidir se esses registros devem ser incluídos na saída. A análise de complexidade mostra que a abordagem hash é significativamente mais eficiente do que uma abordagem ingênua, especialmente para coleções grandes.
Raio-X da questão
algoritmo de junção
avaliacao
algoritmo de junção · pseudocódigo
Revisar conceitos de algoritmos e complexidade computacional.
O aluno pode descrever um algoritmo que não considera adequadamente os registros sem correspondência, resultando em uma junção incorreta.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um algoritmo generalizado que agrupe registros de uma coleção por uma chave extraída por uma função parâmetro…
- Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para um programa que mescla…
- Projete um algoritmo generalizado que receba uma coleção de registros e uma função parâmetro 'valida(reg)' que indique…
- Projete um algoritmo em pseudocódigo que recebe dois vetores unidimensionais de registros 'estoqueA' e 'estoqueB' (cada…
- Projete um algoritmo generalizado que receba uma coleção heterogênea de registros e um mapa de normalização (que indica…
- Projete a decomposição de alto nível de um algoritmo que integra dois conjuntos de dados escolares (registros de…
🔎 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