Uma equipe de uma biblioteca digital precisa reunir os resultados de K consultas já ordenadas. Cada consulta…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Reconhecer o conceito de metaprogramação como uma forma de generalização na construção de programas, permitindo que algoritmos sejam entrada ou saída para outros algoritmos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma equipe de uma biblioteca digital precisa reunir os resultados de K consultas já ordenadas. Cada consulta fornece uma lista de registros do tipo Registro, e as listas podem ter tamanhos diferentes. Para manter o programa reutilizável, a função deve receber um parâmetro comparador. Esse comparador recebe dois registros e retorna um número inteiro: valor negativo quando o primeiro deve aparecer antes do segundo, zero quando são equivalentes quanto à ordenação e valor positivo quando o segundo deve aparecer antes do primeiro. A função deve preservar essa ordem e produzir uma única lista com todos os registros. Com base no contrato descrito, qual assinatura representa corretamente uma função genérica que recebe K listas ordenadas de Registro e um comparador, mescla os elementos e devolve uma única lista ordenada?
- A) mergeK(listas: List<List<Registro>>, comparador: (Registro, Registro)->int) -> List<Registro>
- B) mergeK(listas: List<List<Registro>>, comparador: (Registro, Registro)->int) -> List<List<Registro>>
- C) mergeK(listas: List<List<Registro>>, comparador: (Registro)->int) -> List<Registro>
- D) mergeK(listas: List<List<Registro>>, comparador: int) -> List<Registro>
- E) mergeK(listas: List<Registro>, comparador: (Registro, Registro)->int) -> List<Registro>
✅ Resposta correta: alternativa A
Resolução passo a passo
- Identifique os requisitos do contrato: a função recebe K listas ordenadas de Registro (ou seja, uma lista de listas de Registro), recebe um comparador que compara dois registros e retorna um inteiro, e deve devolver uma única lista com todos os registros, ordenada.
- Verifique a entrada. O primeiro parâmetro precisa ser List<List<Registro>>, pois representa as K listas. A alternativa A declara exatamente isso.
- Verifique o comparador. Ele recebe dois registros e retorna int, o que corresponde à assinatura (Registro, Registro)->int. A alternativa A também está correta nesse ponto.
- Verifique o retorno. A função deve produzir uma única lista de registros, ou seja, List<Registro>. A alternativa A devolve List<Registro>, o que atende ao contrato.
- Conclusão. A alternativa A é a única que combina os três elementos corretamente. Por que as outras estão erradas: a B retorna uma lista de listas, quando o contrato pede uma única lista; a C define o comparador com um só parâmetro, enquanto a comparação exige dois registros; a D recebe um int no lugar do comparador; a E recebe uma lista de registros em vez de uma lista de listas, de modo que não representa K listas.
💡 Dica: Considere a estrutura de dados e a lógica de mesclagem.
Alternativa por alternativa
A entrada listas deve ser uma coleção de listas de Registro, pois a função mescla K listas. O comparador deve receber dois registros para decidir a ordem entre eles e retornar um inteiro com os três resultados previstos no contrato: negativo, zero ou positivo. A saída deve ser uma única List<Registro>, contendo os elementos das listas de entrada em ordem.
O aluno acredita que, por a entrada ser uma lista de listas, a saída também deve manter essa estrutura, sem perceber que o enunciado pede uma única lista com todos os registros.
Por que engana: Confundir o tipo de retorno da função, escolhendo uma alternativa que não devolve uma lista ordenada.
O aluno entende que o comparador precisa de apenas um parâmetro, talvez pensando em uma chave de ordenação, e não na comparação entre dois registros descrita no enunciado.
O aluno confunde o comparador, que é uma função que compara dois registros, com um valor inteiro, possivelmente imaginando que basta passar um número de referência para a ordenação.
O aluno lê K listas como uma única lista de registros, esquecendo que cada consulta fornece sua própria lista, o que exige um tipo de dois níveis.
Raio-X da questão
mesclagem de listas ordenadas
avaliacao
funções e parâmetros em programação · listas e estruturas de dados
Revisar algoritmos de mesclagem e estruturas de dados.
Confundir o tipo de retorno da função, escolhendo uma alternativa que não devolve uma lista ordenada.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete a assinatura de um algoritmo de ordenação generalizado que permita reutilizar o mesmo código para diferentes…
- Descreva um algoritmo generalizado (inclua assinatura e pseudocódigo) que receba duas coleções de registros e um…
- Qual é a complexidade assintótica de mesclar k listas ordenadas que juntas contêm n elementos, usando um min-heap (heap…
- Uma equipe de uma biblioteca digital precisa ordenar 50 mil registros pelo título das obras. A lista já está quase…
- Dadas duas listas ordenadas de números, qual algoritmo e estrutura de dados usar para produzir uma única lista ordenada…
- Projete em pseudocódigo uma função recursiva merge_sorted(L1,L2) que recebe duas listas ordenadas não decrescentes 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