Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
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
Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual representação (matriz de adjacência ou listas de adjacência) reduz melhor custo e por quê, e qual a ordem de espaço em termos de n e m?
- A) Listas de adjacência; espaço O(n + m) em vez de O(n^2) da matriz.
- B) Estruturas de pilha, que oferecem melhor controle de fluxo.
- C) Matriz de incidência, pois muestra diretamente o relacionamento entre arestas e vértices.
- D) Matriz de adjacência, pois simplifica a visualização do grafo.
- E) Listas duplamente encadeadas, que são adequadas para manipulação de dados.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Analise o problema. Um grafo com n vértices e m arestas precisa ser armazenado de forma que se reduza o custo de espaço (e, em geral, de acesso aos vizinhos). A pergunta pede qual representação reduz melhor o custo e qual a ordem de espaço em função de n e m.
- Resolva por conta própria. Na matriz de adjacência, usamos uma tabela n por n, que ocupa sempre O(n^2) de espaço, independentemente de quantas arestas existam. Na lista de adjacência, cada vértice guarda apenas a lista de seus vizinhos; cada aresta aparece uma vez (grafo direcionado) ou duas vezes (não direcionado) e há n listas, o que totaliza O(n + m) de espaço.
- Conclua. Para grafos esparsos (m muito menor que n^2), as listas de adjacência reduzem bastante o custo de espaço, pois O(n + m) cresce muito mais devagar que O(n^2). Portanto, a alternativa A está correta, e o gabarito oficial está correto.
- Por que as outras estão erradas. B: pilha é uma estrutura de dados de controle de acesso LIFO, não uma representação de grafo. C: a matriz de incidência tem dimensão n por m, ocupando O(n*m) de espaço, o que não é a menor opção. D: a matriz de adjacência tem custo O(n^2), que é maior que o das listas em grafos esparsos. E: listas duplamente encadeadas são uma variante de lista, mas não reduzem a ordem de espaço em relação às listas de adjacência simples e não respondem à pergunta sobre o custo ótimo.
💡 Dica: Analise as características de cada representação de grafo.
Alternativa por alternativa
Listas armazenam apenas arestas existentes, portanto em grafos esparsos (m << n^2) consumirão muito menos memória; matriz sempre reserva espaço para todas as possíveis arestas.
O aluno confunde a noção de representação de dados com estruturas de controle de fluxo, achando que pilha seria uma forma de armazenar as conexões do grafo.
O aluno acredita que a matriz de incidência é a representação mais direta e, por isso, a mais econômica, sem perceber que ela tem dimensão n por m e custo O(n*m).
O aluno valoriza a facilidade de visualizar o grafo como tabela e assume que isso também é o mais eficiente em espaço, ignorando que a matriz sempre ocupa O(n^2) mesmo com poucas arestas.
Por que engana: Confundir a complexidade de espaço da matriz de adjacência com a das listas de adjacência, acreditando que ambas têm o mesmo custo.
O aluno associa 'adequada para manipulação' a menor custo e não percebe que listas duplamente encadeadas gastam ponteiros extras e não reduzem a ordem de espaço frente às listas de adjacência.
Raio-X da questão
representação de grafos
avaliacao
representação de grafos · complexidade de algoritmos
Revisar as diferenças entre matriz de adjacência e listas de adjacência.
Confundir a complexidade de espaço da matriz de adjacência com a das listas de adjacência, acreditando que ambas têm o mesmo custo.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- 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…
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