Você tem uma rede social da escola com muitos usuários (nós) e poucas conexões entre eles (arestas). Entre…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Compreender e utilizar diferentes formas de armazenar, manipular, compactar e recuperar arquivos, documentos e metadados.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Você tem uma rede social da escola com muitos usuários (nós) e poucas conexões entre eles (arestas). Entre matriz de adjacência e lista de adjacência, qual estrutura para grafo economiza mais memória?
- A) Matriz de adjacência.
- B) Lista ligada.
- C) Matriz esparsa (sparse matrix).
- D) Lista de adjacência.
- E) Árvore binária.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Identifique o cenário. A rede tem muitos usuários (nós) e poucas conexões (arestas), ou seja, é um grafo esparso, em que E é muito menor que V^2. Passo 2: Calcule o custo de memória de cada estrutura. A matriz de adjacência usa V^2 posições, mesmo que quase todas valham zero. Com, por exemplo, 10.000 usuários, são 100 milhões de células, a maioria vazia. Passo 3: A lista de adjacência guarda, para cada nó, apenas seus vizinhos existentes. O custo é da ordem de V + E, bem menor que V^2 quando o grafo é esparso. Passo 4: Conclusão: entre as duas estruturas citadas no enunciado, a lista de adjacência é a que mais economiza memória. Por que as outras estão erradas: A) a matriz de adjacência é justamente a estrutura que desperdiça memória com zeros em grafos esparsos; B) a lista ligada é uma estrutura de dados genérica, e a representação de grafo correspondente é a lista de adjacência; C) a matriz esparsa também economiza memória, mas o enunciado pede a comparação entre matriz de adjacência e lista de adjacência, e a alternativa C não é uma delas; E) a árvore binária é um tipo de grafo acíclico com estrutura hierárquica, não uma forma de representar uma rede de conexões arbitrárias. Observação: a alternativa C é uma dúvida razoável, pois matrizes esparsas também armazenam só os valores não nulos, mas o gabarito D é coerente com a pergunta.
💡 Dica: Considere as características de cada estrutura de grafo.
Alternativa por alternativa
O aluno pode achar que a matriz, por ser uma estrutura organizada e direta, é a mais econômica, sem considerar que ela reserva espaço para todos os pares possíveis de nós, mesmo quando não há aresta.
Por que engana: Confundir a eficiência de memória entre matriz de adjacência e lista de adjacência, escolhendo a matriz por não considerar a esparsidade das conexões.
O aluno pode confundir lista ligada, que é uma estrutura genérica de armazenamento sequencial por ponteiros, com a representação de grafo por lista de adjacência, sem perceber que a lista ligada não é o modelo específico de grafo.
O aluno pode entender que matriz esparsa é a resposta correta por guardar apenas os valores não nulos, mas desconsiderar que a pergunta compara especificamente matriz de adjacência e lista de adjacência.
Para grafos esparsos a lista requer O(V+E) memória; matriz de adjacência usa O(V^2), desperdiçando espaço quando E é muito menor que V^2.
O aluno pode associar grafos a árvores e supor que a árvore binária é a estrutura ideal para representar uma rede de conexões, sem notar que árvores binárias não representam relações arbitrárias entre muitos nós.
Raio-X da questão
estruturas de grafo
avaliacao
estruturas de grafo · matrizes e listas
Revisar as diferenças entre matriz de adjacência e lista de adjacência.
Confundir a eficiência de memória entre matriz de adjacência e lista de adjacência, escolhendo a matriz por não considerar a esparsidade das conexões.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual representação…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
Todas as questões de Armazenamento e Transmissão de dados - Gestão de dados
🔎 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