Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais…
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
Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para representar as arestas incidentes em cada vértice quando o grafo é esparso?
- A) Listas de adjacência (por exemplo, vetor ou mapa de listas de vizinhos).
- B) Árvore binária, devido à sua capacidade de manter dados ordenados.
- C) Tabelas hash, por serem ótimas para busca de dados.
- D) Matriz de adjacência, pois é mais rápida para acessar arestas específicas.
- E) Lista encadeada, pois permite fácil inserção de novas arestas.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Em um grafo esparso, o número de arestas é muito menor que o máximo possível (V^2). Assim, a estrutura ideal deve gastar memória proporcional ao número de vértices mais o número de arestas, e não ao quadrado de vértices. Passo 2: A lista de adjacência faz exatamente isso: cada vértice guarda apenas a lista (vetor ou mapa de listas) dos seus vizinhos. Por isso a alternativa A está correta, e concordo com o gabarito oficial. Passo 3: A alternativa B está errada, pois a ordenação dos dados em uma árvore binária não é o critério necessário para representar as arestas de um vértice. Passo 4: A alternativa C está errada, pois a tabela hash é ótima para buscar uma aresta específica, mas não é a forma natural de percorrer todos os vizinhos de um vértice. Passo 5: A alternativa D está errada, pois a matriz de adjacência ocupa V^2 posições mesmo quando há poucas arestas, o que desperdiça memória em grafos esparsos. Passo 6: A alternativa E está errada como resposta principal, pois a facilidade de inserção é uma vantagem secundária; listas encadeadas são apenas uma forma de implementar a lista de adjacência, que é o conceito completo da alternativa A.
💡 Dica: Considere as características de grafos esparsos ao escolher a estrutura de dados.
Alternativa por alternativa
Listas de adjacência armazenam apenas arestas existentes, ocupando O(n + m) espaço em grafos esparsos, permitindo iteração eficiente sobre vizinhos sem custo O(n^2) da matriz.
Acredita que, por manter dados ordenados, a árvore binária é a melhor forma de guardar as arestas de cada vértice, ignorando o custo de memória e o objetivo da representação.
Confunde a vantagem da tabela hash para buscar um elemento específico com a necessidade de representar e percorrer todos os vizinhos de um vértice.
Considera apenas o tempo de acesso a uma aresta específica (O(1)) e não percebe que a matriz ocupa V^2 posições, desperdiçando memória em um grafo esparso.
Por que engana: Escolher a matriz de adjacência, acreditando que ela é sempre a melhor opção para qualquer tipo de grafo, sem considerar a esparsidade.
Foca apenas na facilidade de inserir novas arestas e não percebe que a estrutura pedida é o conceito de lista de adjacência, do qual a lista encadeada é apenas uma possível implementação.
Raio-X da questão
grafos esparsos
avaliacao
estruturas de dados · grafos e suas representações
Revisar estruturas de dados adequadas para representação de grafos.
Escolher a matriz de adjacência, acreditando que ela é sempre a melhor opção para qualquer tipo de grafo, sem considerar a esparsidade.
ciencia_tecnologia
pensamento_critico
cientifico
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 das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de…
- Qual estrutura de dados é mais indicada para representar um grafo em um programa?
- Qual a estrutura ideal para armazenar as conexões de um grafo direcionado?
- 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