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
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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