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
- Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo…
- Descreva sucintamente como verificar se um grafo simples não direcionado é k-regular usando sua lista de adjacência; que…
- Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
- Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um índice…
- Em um autômato orientado por eventos que registra leituras periódicas de um sensor, qual estrutura de dados é mais…
- Projete um autômato baseado em eventos para gerenciar reservas de salas multimídia na escola: descreva estados, eventos…
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