Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de adjacência ou matriz de adjacência? Explique em termos de ordem de grandeza.
- A) A matriz de adjacência é melhor em grafos com poucos vértices e muitas arestas.
- B) Uma lista encadeada, pois consome sempre menos memória.
- C) A matriz de adjacência, pois é mais fácil de implementar e entender.
- D) Lista de adjacência — usa O(V+E) memória, enquanto a matriz usa O(V^2).
- E) A lista de adjacência não é usada em nenhum tipo de grafo.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Um grafo esparso é aquele em que o número de arestas E é muito menor que o máximo possível de V^2 (V é o número de vértices). Uma rede de ônibus costuma ter muitos pontos ligados a poucos vizinhos diretos, portanto é esparso.
- A matriz de adjacência guarda uma célula para cada par de vértices, ou seja, V x V células, independentemente de quantas arestas existam. Por isso sua memória é O(V^2). Em um grafo esparso, quase todas essas células valem zero, o que desperdiça memória.
- A lista de adjacência guarda, para cada vértice, apenas a lista dos seus vizinhos. Há um registro por vértice (V) e um registro por aresta (E, contando as duas direções em grafos não direcionados). Assim a memória é O(V+E), que em grafos esparsos é próxima de O(V).
- Comparando a ordem de grandeza: para V = 10000 e E = 30000, a matriz exige cerca de 100 milhões de células, enquanto a lista exige cerca de 40000 registros. A lista é ordens de grandeza menor.
- Por que as outras estão erradas: A) inverte a situação, pois a matriz é vantajosa em grafos densos, não com poucos vértices e muitas arestas. B) a lista encadeada é apenas uma forma de implementar a lista de adjacência, e 'sempre menos memória' é falso, pois depende do número de arestas. C) facilidade de implementação não é critério de uso de memória, e a matriz é justamente a opção mais custosa em espaço para grafos esparsos. E) a lista de adjacência é amplamente usada, especialmente em grafos esparsos.
- Resposta: a alternativa D está correta, pois traz a comparação correta de complexidade de memória.
💡 Dica: Compare as duas representações em termos de eficiência de memória.
Alternativa por alternativa
O aluno acredita que a matriz é eficiente quando há poucos vértices, esquecendo que seu custo depende de V^2 e não do número de arestas.
O aluno associa lista encadeada a sempre ocupar menos memória, sem considerar que a lista de adjacência pode ter muitas arestas e que o critério é a ordem de grandeza.
O aluno confunde facilidade de implementação ou compreensão com eficiência de memória, usando a intuição de que a estrutura mais simples é também a mais econômica.
Por que engana: Confundir a eficiência de memória entre lista de adjacência e matriz de adjacência, escolhendo a matriz como a melhor opção em todos os casos.
Em grafos esparsos E << V^2; a lista armazena apenas arestas existentes (V+E), já a matriz reserva espaço para todas as possíveis pares de vértices (V^2).
O aluno acredita que a lista de adjacência é uma estrutura pouco útil ou inexistente na prática, sem reconhecer seu uso amplo em grafos esparsos.
Raio-X da questão
representação de grafos
avaliacao
representação de grafos · complexidade de algoritmos
Revisar as diferenças entre lista de adjacência e matriz de adjacência.
Confundir a eficiência de memória entre lista de adjacência e matriz de adjacência, escolhendo a matriz como a melhor opção em todos os casos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- 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…
- Você tem uma rede social da escola com muitos usuários (nós) e poucas conexões entre eles (arestas). Entre matriz de…
Todas as questões de Organização e representação da informação
🔎 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