Um grafo esparso (muitos vértices e poucas arestas) passa por inserções e remoções frequentes de arestas…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um grafo esparso (muitos vértices e poucas arestas) passa por inserções e remoções frequentes de arestas. Comparando matriz de adjacência e lista de adjacência, qual afirmação está correta?
- A) A lista usa menos memória; a matriz insere ou remove arestas em tempo constante.
- B) A matriz é sempre mais eficiente, tanto em memória quanto em atualizações.
- C) A matriz usa menos memória; a lista guarda uma posição para cada par de vértices.
- D) A lista não permite remover arestas depois que o grafo é criado.
- E) Ambas usam a mesma memória e atualizam arestas no mesmo tempo.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Um grafo esparso tem muitos vértices (V) e poucas arestas (E). Passo 2: A matriz de adjacência é uma tabela V x V, então ocupa sempre cerca de V^2 posições, mesmo que quase todas valham zero. Passo 3: A lista de adjacência guarda apenas as arestas existentes, ocupando cerca de V+E posições, o que é muito menor quando E é pequeno. Passo 4: Para inserir ou remover uma aresta na matriz, basta acessar a célula (i,j) e alterar o valor, operação de tempo constante. Passo 5: Na lista, é preciso percorrer a lista de vizinhos do vértice para achar ou remover a aresta, o que pode levar tempo proporcional ao grau do vértice. Passo 6: Logo, a alternativa A está correta: a lista usa menos memória e a matriz atualiza arestas em tempo constante. Passo 7: A alternativa B está errada, pois a matriz gasta muita memória em grafos esparsos. Passo 8: A alternativa C está errada, pois inverte os fatos: a matriz é que usa mais memória, e a lista não guarda uma posição para cada par de vértices. Passo 9: A alternativa D está errada, pois a lista permite remover arestas normalmente, apenas com custo de busca. Passo 10: A alternativa E está errada, pois as duas estruturas gastam memórias diferentes e têm custos de atualização diferentes. Gabarito oficial confirmado.
💡 Dica: Compare o custo de armazenamento e de atualização das duas representações.
Alternativa por alternativa
A lista guarda apenas as arestas existentes e, por isso, usa menos memória em grafos esparsos. Na matriz, inserir ou remover uma aresta exige alterar uma única posição, o que leva tempo constante.
O aluno acredita que a matriz é sempre superior por ser uma estrutura simples de acessar, sem considerar que ela ocupa V^2 posições mesmo quando há poucas arestas.
Por que engana: Confundir o custo de memória da matriz, que cresce com todos os pares de vértices, com o da lista, que depende principalmente das arestas existentes.
O aluno inverte a análise de memória, achando que a matriz é mais econômica e que a lista guarda uma entrada para cada par de vértices, quando é justamente o contrário.
O aluno acredita que a lista de adjacência é estática e não suporta remoções, confundindo a dificuldade de busca na lista com a impossibilidade de remover arestas.
O aluno supõe que as duas representações são equivalentes em memória e tempo, ignorando que a matriz exige V^2 posições independentemente de E.
Raio-X da questão
Representação de grafos
avaliacao
Estruturas de dados em grafos · Complexidade de operações básicas
Revise o espaço usado e o custo de operações em matrizes e listas de adjacência.
Confundir o custo de memória da matriz, que cresce com todos os pares de vértices, com o da lista, que depende principalmente das arestas existentes.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo…
🔎 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