Dado um algoritmo que processa uma matriz esparsa de notas de alunos, qual representação de dados reduz…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Dado um algoritmo que processa uma matriz esparsa de notas de alunos, qual representação de dados reduz significativamente o uso de memória mantendo acesso eficiente por índice?
- A) Compressed Sparse Row (CSR) — armazena apenas entradas não nulas com índices por linha.
- B) Utilizar uma lista encadeada que armazena todos os elementos.
- C) Representar a matriz em um formato tridimensional.
- D) Utilizar tabelas hash para armazenar entrada e índice.
- E) Armazenar a matriz completa em memória, incluindo zeros e nulos.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Uma matriz esparsa é aquela em que a grande maioria das posições tem valor zero ou nulo. Guardar a matriz inteira desperdiça memória com esses zeros, então o objetivo é armazenar apenas as entradas relevantes sem perder a capacidade de acessá-las pelo índice de linha e coluna.
- Analisando as alternativas sem olhar o gabarito, a Compressed Sparse Row (CSR) guarda apenas os valores não nulos, em um vetor contínuo, junto com um vetor de índices de colunas e um vetor de ponteiros indicando onde começa cada linha. Assim o uso de memória cai de forma significativa, e ainda é possível localizar rapidamente os elementos de uma linha, o que mantém o acesso eficiente por índice.
- Por que as demais estão erradas:
- - B: uma lista encadeada que armazena todos os elementos continua guardando os zeros, então não reduz a memória, além de o acesso por índice ser lento (percurso sequencial).
- - C: um formato tridimensional não faz sentido para uma matriz bidimensional de notas e apenas acrescenta uma dimensão, aumentando o custo de memória.
- - D: tabelas hash até armazenam só entradas não nulas, mas não preservam a organização por linha que o CSR oferece e não são a representação clássica para matrizes esparsas com acesso eficiente por índice de linha; além disso, a alternativa não especifica essa estrutura de forma adequada.
- - E: armazenar a matriz completa, com zeros e nulos, é exatamente o oposto do que se deseja, pois gasta memória com posições vazias.
- Conclusão: a alternativa A é a correta e coincide com o gabarito oficial.
💡 Dica: Considere as estruturas de dados que otimizam o armazenamento de matrizes esparsas.
Alternativa por alternativa
CSR guarda apenas valores não nulos e seus índices por linha, evitando alocação da matriz densa inteira; isso reduz memória quando há poucos elementos não nulos e permite acesso por índice com estruturas de índices.
Acredita que uma lista encadeada economiza memória por ser dinâmica, sem perceber que ela ainda guarda todos os elementos, inclusive os zeros.
Por que engana: Escolher a alternativa que sugere armazenar todos os elementos, incluindo zeros, que não é eficiente em termos de memória.
Imagina que mais dimensões organizam melhor os dados, sem perceber que a matriz já é bidimensional e que uma terceira dimensão só aumenta o consumo de memória.
Entende que hash guarda só o que existe e, por isso, seria sempre a melhor solução, ignorando que a alternativa não descreve a organização por linha que garante acesso eficiente e compacto.
Supõe que armazenar a matriz completa facilita o acesso, sem considerar que os zeros ocupam memória desnecessariamente em uma matriz esparsa.
Raio-X da questão
matriz esparsa
avaliacao
representação de dados · matrizes esparsas
Revisar as representações de dados para matrizes esparsas.
Escolher a alternativa que sugere armazenar todos os elementos, incluindo zeros, que não é eficiente em termos de memória.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Para representar uma grande matriz de leituras de sensores em que a maioria dos valores é zero, qual técnica de…
- Qual é a estrutura utilizada para armazenar dados em uma matriz?
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Uma escola brasileira está desenvolvendo um sistema para acompanhar as notas de 30 estudantes em quatro avaliações…
- Em um algoritmo que registra as notas de cada aluno em quatro avaliações distintas (por aluno × por avaliação), qual…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível 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