Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Classificar informações, agrupando-as em coleções (conjuntos) e associando cada coleção a um ‘tipo de dados’
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de adjacência?
- A) Árvore
- B) Listas encadeadas
- C) Matriz de Adjacência
- D) Registro
- E) Vetores
✅ Resposta correta: alternativa B
Resolução passo a passo
- Lista de adjacência é uma forma de representar um grafo em que cada vértice guarda apenas a lista dos vértices vizinhos (aqueles ligados a ele por uma aresta). Passo 2: Como o número de vizinhos de cada vértice varia e pode mudar durante a execução, a estrutura precisa crescer e diminuir sem desperdício de memória. Passo 3: Isso é exatamente o que as listas encadeadas oferecem, pois cada nó aponta para o próximo e a inserção de uma nova aresta é simples. Passo 4: Por isso, a resposta é a alternativa B, que coincide com o gabarito oficial. Passo 5: A alternativa A está errada, pois árvore é um tipo especial de grafo, não a estrutura usada para guardar a lista de vizinhos. Passo 6: A alternativa C está errada, pois a matriz de adjacência é outra forma de representar o grafo, e não a estrutura que implementa a lista. Passo 7: A alternativa D está errada, pois registro agrupa campos de tipos diferentes e não representa uma sequência de vizinhos. Passo 8: A alternativa E é tecnicamente possível, pois é possível usar um vetor de listas, mas vetores têm tamanho fixo e não são a estrutura mais adequada para a lista encadeada de vizinhos que a questão pede.
💡 Dica: Considere as estruturas de dados mais comuns para grafos.
Alternativa por alternativa
O aluno associa a representação de grafos a árvores, por ambas terem vértices e conexões, e conclui que a lista de adjacência seria uma árvore.
Listas encadeadas são ideais para armazenar adjacências devido à sua flexibilidade.
O aluno confunde as duas formas clássicas de representar grafos e acredita que a matriz de adjacência é a própria lista de adjacência.
Por que engana: Confundir matriz de adjacência com listas de adjacência, escolhendo matriz por parecer mais direta.
O aluno interpreta registro como qualquer estrutura que armazena dados relacionados e não percebe que ele não forma uma sequência de vizinhos.
O aluno pensa que vetores são sempre a estrutura natural para armazenar coleções, ignorando que o tamanho fixo do vetor não se adapta bem ao número variável de vizinhos de cada vértice.
Raio-X da questão
listas de adjacência
avaliacao
estruturas de dados básicas · conceito de grafos
Revisar estruturas de dados utilizadas em grafos.
Confundir matriz de adjacência com listas de adjacência, escolhendo matriz por parecer mais direta.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual estrutura de dados é mais indicada para representar um grafo em um programa?
- 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?
- Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Qual das seguintes estruturas de dados é mais eficiente para adicionar um novo nó em um grafo?
🔎 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