Qual das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio da reutilização de partes de soluções existentes.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- A) Lista simplesmente ligada.
- B) Matriz de adjacência.
- C) Array dinâmico.
- D) Lista de encadeamento.
- E) Tabela hash.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Um grafo não direcionado é formado por vértices e arestas sem sentido de percurso, então a aresta entre u e v também é a aresta entre v e u. Passo 2: Ao resolver por conta própria, o critério é representar com eficiência a existência de arestas entre pares de vértices e manter a simetria do grafo. Passo 3: A matriz de adjacência é uma matriz n por n, em que a posição (i, j) indica se existe aresta entre os vértices i e j. Como o grafo não é direcionado, a matriz é simétrica, o que torna a representação natural e direta, com consulta de aresta em tempo constante. Passo 4: Por que as outras estão erradas: a lista simplesmente ligada é uma estrutura linear genérica que não representa relações entre vértices por si só; o array dinâmico é um vetor redimensionável que guarda elementos em sequência, sem relação de adjacência; a lista de encadeamento é um termo genérico para estruturas ligadas, não uma representação específica de grafos; a tabela hash serve para busca associativa de chaves e não modela diretamente as arestas. Passo 5: Observação de dúvida: na prática, para grafos esparsos, a lista de adjacência costuma ser mais econômica em memória, mas essa opção não aparece nas alternativas. Entre as opções apresentadas, a matriz de adjacência é a resposta que melhor se encaixa, e o gabarito oficial está coerente com essa análise.
💡 Dica: Compare como cada estrutura representa as conexões entre vértices.
Alternativa por alternativa
Acredita que qualquer lista ligada basta para representar um grafo, sem perceber que a lista simplesmente ligada não guarda naturalmente as conexões entre vértices de forma organizada e simétrica.
Uma matriz de adjacência representa a conexão entre vértices em um grafo não direcionado.
Confunde a necessidade de armazenar vértices e arestas com a capacidade de crescer dinamicamente, achando que o redimensionamento automático do array resolve a modelagem de relações.
Interpreta 'lista de encadeamento' como sinônimo de lista de adjacência, sem reconhecer que o termo é genérico e não designa a representação específica de grafos.
Associa a tabela hash à busca rápida de vértices e supõe que ela modela naturalmente as arestas, esquecendo que a hash apenas indexa chaves e não guarda a estrutura de conexões.
Por que engana: Escolher uma estrutura genérica, como array ou tabela hash, sem considerar que a matriz de adjacência representa diretamente as conexões entre pares de vértices.
Raio-X da questão
Representação de grafo não direcionado
avaliacao
Conceito de vértices e arestas · Estruturas de dados básicas
Revise matrizes de adjacência e outras formas de representação de grafos.
Escolher uma estrutura genérica, como array ou tabela hash, sem considerar que a matriz de adjacência representa diretamente as conexões entre pares de vértices.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?
- 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…
- Considere um grafo não direcionado representando amigos. Qual a representação mais adequada para armazená-lo?
- Qual das seguintes estruturas de dados é mais eficiente para adicionar um novo nó em um grafo?
- Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
🔎 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