Defina, em termos de grafo, o que é uma lista de adjacência e que informação ela armazena para cada vértice…
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
Defina, em termos de grafo, o que é uma lista de adjacência e que informação ela armazena para cada vértice (use os termos vértice e aresta).
- A) É uma lista que contém todos os vértices do gráfico sem suas arestas.
- B) Representa um vértice como uma matriz onde cada célula indica uma aresta.
- C) É uma estrutura que associa a cada vértice uma lista (ou vetor) com os vértices vizinhos conectados por arestas.
- D) Guarda um único vértice e suas arestas em um formato de árvore.
- E) Armazena apenas os números de identificação dos vértices, sem relação entre eles.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Em teoria dos grafos, uma lista de adjacência é uma forma de representar um grafo em que cada vértice é associado a uma coleção (lista, vetor ou conjunto) dos vértices que são seus vizinhos, ou seja, aqueles ligados a ele por uma aresta. Assim, para cada vértice v, a estrutura armazena as arestas incidentes a v, representadas pelos vértices adjacentes a v.
- Comparando com as alternativas, a C descreve exatamente essa ideia: associa a cada vértice uma lista com os vizinhos conectados por arestas. Logo, a alternativa C é a correta, coincidindo com o gabarito oficial.
- A alternativa A está errada porque a lista de adjacência não guarda apenas os vértices; ela justamente registra as arestas, por meio das conexões entre cada vértice e seus vizinhos.
- A alternativa B está errada porque descreve uma matriz de adjacência, que é outra forma de representação, e não uma lista; além disso, não se representa um vértice como matriz.
- A alternativa D está errada porque a lista de adjacência não guarda um único vértice nem tem formato de árvore; ela representa o grafo inteiro.
- A alternativa E está errada porque os números de identificação não ficam sem relação entre si; a função da estrutura é justamente registrar as ligações (arestas) entre os vértices.
💡 Dica: Defina os conceitos de vértice e aresta antes de explicar a lista de adjacência.
Alternativa por alternativa
O aluno entende que a lista de adjacência é apenas uma relação de todos os vértices, ignorando que a estrutura precisa registrar as arestas entre eles.
O aluno confunde a lista de adjacência com a matriz de adjacência, imaginando que cada vértice é representado por uma matriz em que as células indicam arestas.
Por que engana: Confundir a lista de adjacência com a representação de um grafo em matriz, que não associa diretamente os vértices aos seus vizinhos.
A lista de adjacência guarda, para cada vértice, os seus vizinhos (arestas incidentes), permitindo percorrer apenas arestas existentes e economizando espaço em grafos esparsos.
O aluno associa a estrutura a uma árvore e a um único vértice, perdendo a ideia de que a lista representa todos os vértices do grafo e suas conexões.
O aluno acredita que, por guardar apenas identificadores, a estrutura não registra relações entre os vértices, quando na verdade são justamente as arestas que ela armazena.
Raio-X da questão
lista de adjacência
fixacao
estrutura de dados · grafos e suas representações
Revisar a definição de grafos e suas representações.
Confundir a lista de adjacência com a representação de um grafo em matriz, que não associa diretamente os vértices aos seus vizinhos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- A professora fez uma tabela: os grupos ficam nas linhas, os dias da semana ficam nas colunas e cada espaço mostra a…
- Um aplicativo percebe quais fotos mostram animais. O que ele pode fazer para achar essas fotos mais rápido? O que o…
- Em Manaus, a escola testa um programa que separa mensagens em urgente e comum. Aplique a ideia de classificacao e…
- Desenhe um grafo que represente uma rota de entregas entre três escolas (E1, E2, E3) e dois pontos de apoio (P1, P2)…
- Um mapa de estações de metrô em que as estações estão ligadas por linhas pode ser representado como um grafo? Escreva a…
- Escolha um exemplo do cotidiano (por exemplo: contatos em um aplicativo da escola ou paradas de ônibus) e descreva como…
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