Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse grafo gastando menos memória?
- A) Matriz de adjacência
- B) Lista de adjacência
- C) Árvore
- D) Pilha
- E) Fila
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado descreve um grafo esparso, ou seja, com milhares de vértices, mas com poucas arestas por vértice. O objetivo é representá-lo gastando o mínimo de memória.
- Uma matriz de adjacência de n vértices ocupa n^2 posições, independentemente de quantas arestas existam. Com milhares de vértices, quase todas as células ficariam vazias (zeros), desperdiçando memória.
- Uma lista de adjacência guarda, para cada vértice, apenas a lista de seus vizinhos. O espaço fica proporcional a n mais m (número de vértices mais número de arestas), o que é muito menor quando o grafo é esparso. Logo, a alternativa correta é a B.
- Por que as outras estão erradas: a matriz de adjacência é justamente a estrutura que desperdiça memória em grafos esparsos; árvore é um tipo especial de grafo (conexo e sem ciclos), não uma forma de representar grafos gerais; pilha é uma estrutura de dados LIFO, sem relação direta com a representação de grafos; fila é uma estrutura FIFO, usada por exemplo na busca em largura, mas não representa a estrutura do grafo.
- Conclusão: concordo com o gabarito oficial, B, pois a lista de adjacência é a representação mais econômica em memória para grafos com muitos vértices e poucas conexões por vértice.
💡 Dica: Compare o espaço ocupado por cada representação quando há poucas arestas em relação ao número de vértices.
Alternativa por alternativa
O aluno acredita que a matriz de adjacência é sempre a melhor forma de representar grafos, por ser a mais simples de construir e consultar, sem considerar o custo de memória de n^2 posições quando o grafo é esparso.
Por que engana: Escolher a matriz de adjacência por associá-la a uma representação mais direta, sem considerar que ela reserva espaço para todos os pares de vértices.
A lista de adjacência guarda só as arestas que existem, então gasta pouca memória quando há poucas ligações.
O aluno confunde o conceito de árvore, um tipo específico de grafo, com uma estrutura de representação de grafos, achando que a palavra 'árvore' se refere a qualquer organização de vértices e conexões.
O aluno associa qualquer estrutura de dados a qualquer problema envolvendo vértices e conexões, sem perceber que a pilha é uma estrutura linear LIFO que não representa conexões entre vértices.
O aluno lembra que a fila aparece em algoritmos de grafos, como a busca em largura, e conclui que ela serve para representar o grafo, quando na verdade é apenas auxiliar no percurso.
Raio-X da questão
Lista de adjacência em grafos
avaliacao
Vértices e arestas de grafos · Representações de estruturas de dados
Revise representações de grafos e o uso de memória em grafos esparsos.
Escolher a matriz de adjacência por associá-la a uma representação mais direta, sem considerar que ela reserva espaço para todos os pares de vértices.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
- Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
- — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
- Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
- — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
- Ontem o mapa do festival me mandou dar uma volta enorme reclamou uma visitante. Para reduzir aglomeracoes, a…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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