Recebe-se uma matriz M (m×n) de registros de alunos (nome, nota). Descreva um algoritmo em pseudocódigo para…

Questão

Recebe-se uma matriz M (m×n) de registros de alunos (nome, nota). Descreva um algoritmo em pseudocódigo para detectar e remover linhas com registros inválidos (nome vazio ou nota <0 ou >10) e discuta por que escolher lista encadeada ou matriz conforme a frequência de remoções. Indique complexidade do processo.

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

Resposta esperada

Percorrer M linha a linha: para cada registro verificar if nome = "" ou nota <0 ou nota>10; marcar índice inválido. Se número de remoções pequeno, remover diretamente da matriz (shift de linhas) com custo O(m·n) no pior caso; pseudocódigo: para i de 1 a m se inválido então removerLinha(i). Se remoções frequentes, converter M em lista ligada de registros e ao detectar inválido executar remoção O(1) ajustando ponteiros, depois opcionalmente reconstruir matriz. Complexidade: verificação O(m·n); remoções em matriz podem exigir O(m·n) por remoção por deslocamento; em lista, remoções O(1) cada, total O(m·n) pela verificação mais O(k) pelas remoções, onde k é número de registros removidos.

Explicação

A solução proposta aborda a verificação de cada registro de forma sistemática, garantindo que todas as condições de validade sejam checadas. A escolha entre matriz e lista encadeada é fundamentada na frequência de remoções, onde a lista encadeada oferece eficiência em remoções frequentes, enquanto a matriz pode ser mais prática para um número reduzido de remoções. A análise de complexidade é clara, diferenciando os custos de operações em cada estrutura de dados, o que é essencial para entender a eficiência do algoritmo.

Raio-X da questão

Questões parecidas com resolução

• — Se dois voluntários entregarem o mesmo aparelho, como saberemos onde ele está? — perguntou uma visitante ao chegar à…
• Monitores de um centro esportivo estão testando um placar digital para partidas de futsal, vôlei e basquete. Antes de…
• Por que duas pessoas que leem uma história na tela podem chegar a trechos diferentes? Para uma mostra comunitária…
• Caminhões recolhem livros em uma campanha fictícia para renovar bibliotecas de bairro. Em cada ponto de coleta…
• — Se chegarem novos tipos de objetos, vou precisar copiar tudo outra vez? — perguntou Joana, que ajuda no ponto de…
• — Se enviarmos as caixas sem organização, um abrigo poderá receber itens que não pediu e outro ficará sem produtos…

Todas as questões de Estratégias de solução de problemas - Decomposição