Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?
- A) Matriz de Adjacência
- B) Lista de Adjacência
- C) Lista Dupla
- D) Árvore
- E) Vetores
✅ Resposta correta: alternativa B
Resolução passo a passo
- Em um grafo com muitos vértices e poucas arestas, a maioria das combinações possíveis de pares de vértices não tem aresta. Assim, a representação deve gastar espaço proporcional ao número de arestas, não ao quadrado do número de vértices. Passo 2: A Lista de Adjacência guarda, para cada vértice, apenas a lista dos seus vizinhos. O espaço usado é da ordem de V + E (vértices mais arestas), o que é muito econômico quando E é pequeno. Passo 3: Consultar se existe aresta entre dois vértices fica mais lento que na matriz, mas percorrer os vizinhos de um vértice é rápido, e isso costuma ser a operação mais frequente em algoritmos sobre grafos esparsos. Passo 4: Por que as outras estão erradas: a Matriz de Adjacência ocupa V^2 posições mesmo quando há poucas arestas, o que desperdiça memória; a Lista Dupla não é uma forma padrão de representar grafos, sendo apenas uma estrutura linear com ponteiros para frente e para trás; a Árvore é um caso particular de grafo, conectado e sem ciclos, com apenas V-1 arestas, e não serve como estrutura geral para representar qualquer grafo; Vetores, sozinhos, não indicam quais vértices são conectados, e só ganham sentido quando usados para montar listas de adjacência. Passo 5: Conclusão: a alternativa correta é a B, Lista de Adjacência, que é a estrutura mais adequada para grafos esparsos, com gabarito concordando com a resolução.
💡 Dica: Considere as características dos grafos ao escolher a estrutura.
Alternativa por alternativa
O aluno associa a matriz de adjacência à representação de grafos em geral e não percebe que ela reserva V^2 posições, mesmo quando quase todas estão vazias.
Por que engana: Confundir matriz de adjacência com lista de adjacência, escolhendo matriz para grafos esparsos, o que gera desperdício de memória.
Essa é a estrutura ideal para grafos esparsos com muitos vértices.
O aluno confunde a lista dupla, uma estrutura linear com ponteiros nos dois sentidos, com a lista de adjacência, achando que o termo duplo indica uma representação de grafo mais completa.
O aluno acredita que, por a árvore ser um tipo de grafo com estrutura simples, ela serve como representação geral para qualquer grafo com muitos vértices, ignorando que árvores têm no máximo V-1 arestas e não são uma estrutura genérica.
O aluno pensa que vetores, por armazenarem muitos dados de forma compacta, bastam para representar um grafo, sem perceber que não há registro das conexões entre os vértices.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados grafos · representacao de grafos
Revisar as estruturas de dados adequadas para grafos.
Confundir matriz de adjacência com lista de adjacência, escolhendo matriz para grafos esparsos, o que gera desperdício de memória.
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- Qual estrutura de dados é mais indicada para representar um grafo em um programa?
- Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de…
- Qual das seguintes estruturas de dados é mais eficiente para adicionar um novo nó em um grafo?
- Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse grafo…
- Identifique a estrutura de dados mais adequada para representar uma rede social, onde cada usuário é um nó e as conexões…
🔎 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