Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível…
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
Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para representar as arestas quando o grafo é esparso: matriz de adjacência ou lista de adjacência?
- A) Árvore binária para representar amigos.
- B) Lista de adjacência.
- C) Lista encadeada apenas com vértices.
- D) Tabela hash para arestas.
- E) Matriz de adjacência sempre.
✅ Resposta correta: alternativa B
Resolução passo a passo
- A questão pergunta qual estrutura é preferível para representar as arestas de um grafo esparso, ou seja, um grafo em que o número de arestas é muito menor que o máximo possível (V^2).
- A matriz de adjacência ocupa sempre V^2 posições, mesmo quando há poucas arestas, o que gera desperdício de memória e torna percorrer os vizinhos de um vértice custoso (é preciso varrer uma linha inteira).
- A lista de adjacência armazena, para cada vértice, apenas seus vizinhos reais. O espaço ocupado é proporcional a V + E, o que é muito melhor quando E é pequeno. Além disso, percorrer os amigos de um estudante custa apenas o grau dele.
- Portanto, a alternativa B é a correta e coincide com o gabarito oficial.
- Por que as outras estão erradas: A) árvore binária não é uma estrutura de representação geral de grafos, pois um grafo pode conter ciclos e múltiplas conexões; C) uma lista apenas de vértices não guarda as arestas, então não representa a amizade; D) tabela hash para arestas até funciona, mas não é a representação padrão e não traz a vantagem direta de acessar os vizinhos de cada vértice; E) a matriz de adjacência é ineficiente para grafos esparsos, justamente o caso da questão, portanto não é 'sempre' preferível.
💡 Dica: Considere qual estrutura economiza espaço quando há poucas arestas em relação ao total de vértices.
Alternativa por alternativa
O aluno associa a representação de relações entre pessoas a árvores, imaginando que a hierarquia de uma árvore binária modela qualquer rede de amizades.
Para grafos esparsos a lista de adjacência usa menos memória (O(V+E)) e permite iterar eficientemente os vizinhos de um vértice; a matriz de adjacência é mais adequada quando o grafo é denso.
O aluno entende que representar o grafo basta listar os estudantes (vértices), esquecendo que as amizades (arestas) também precisam ser armazenadas.
O aluno acredita que a tabela hash é a estrutura padrão para arestas, ignorando que a lista de adjacência é a representação usual e mais direta para acessar os vizinhos em grafos esparsos.
O aluno acha que a matriz de adjacência é sempre a melhor opção por ser simples de consultar (verificar se duas pessoas são amigas em tempo constante), sem considerar o desperdício de memória em grafos esparsos.
Por que engana: Escolher a matriz de adjacência por considerá-la sempre mais eficiente, sem levar em conta que um grafo esparso tem poucas arestas e pode desperdiçar espaço.
Raio-X da questão
Representação de grafos esparsos
avaliacao
Grafos e suas arestas · Estruturas de dados básicas
Revise as diferenças de espaço e consulta entre matrizes e listas de adjacência.
Escolher a matriz de adjacência por considerá-la sempre mais eficiente, sem levar em conta que um grafo esparso tem poucas arestas e pode desperdiçar espaço.
ciencia_tecnologia
tomada_decisao
cotidiano
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 otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Você tem uma rede social da escola com muitos usuários (nós) e poucas conexões entre eles (arestas). Entre matriz de…
- 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…
- Em um grafo que representa amizades em uma turma (cada aluno é um vértice e cada amizade é uma aresta), cada aluno tem…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
🔎 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