Ao representar um autômato de estados com muitos estados e poucas transições entre eles (grafo esparso) para…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Compreender e utilizar diferentes formas de armazenar, manipular, compactar e recuperar arquivos, documentos e metadados.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Ao representar um autômato de estados com muitos estados e poucas transições entre eles (grafo esparso) para executar um algoritmo de busca de caminho, qual representação de grafo reduz uso de memória?
- A) Grafo bipartido
- B) Matriz de adjacência
- C) Árvore binária
- D) Tabela hash
- E) Lista de adjacência.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Identifique o problema. O autômato tem muitos estados (vértices) e poucas transições (arestas), ou seja, é um grafo esparso. Queremos uma estrutura de dados que armazene o grafo gastando pouca memória.
- Analise a matriz de adjacência. Ela usa uma tabela de tamanho V x V, ocupando memória proporcional ao quadrado do número de estados, mesmo quando quase todas as posições são zero. Logo, desperdiça memória em grafos esparsos.
- Analise a lista de adjacência. Para cada estado guarda-se apenas a lista dos estados alcançáveis por uma transição. A memória fica proporcional a V + E (estados mais transições), que é muito menor quando E é pequeno. Esta é a resposta correta, e o gabarito oficial está certo.
- Por que as outras estão erradas. A) Grafo bipartido é uma propriedade de um grafo (seus vértices se dividem em dois conjuntos), não uma forma de representá-lo na memória. B) A matriz de adjacência, como visto no passo 2, desperdiça memória em grafos esparsos. C) Árvore binária é um tipo de grafo acíclico com restrição de grau, não uma representação geral de grafos com muitas conexões arbitrárias. D) Tabela hash é uma estrutura para busca por chave, que pode ser usada internamente, mas não é a representação padrão de grafo esparso citada nesse contexto.
💡 Dica: Considere as características dos grafos esparsos.
Alternativa por alternativa
Confunde a propriedade estrutural de um grafo bipartido com uma forma de armazenamento; acredita que dividir os vértices em dois conjuntos reduz a memória usada.
Acredita que a matriz de adjacência, por ser a representação mais comum e direta, é também a mais econômica, sem perceber que ela ocupa V x V posições mesmo quando há poucas arestas.
Por que engana: Escolher a matriz de adjacência, que é mais adequada para grafos densos, em vez da lista de adjacência para grafos esparsos.
Associa qualquer estrutura de grafo à árvore binária, pensando que a hierarquia de nós com no máximo dois filhos serve para representar todas as conexões entre estados.
Pensa que a tabela hash, por permitir acesso rápido, resolve sozinha a representação do grafo e economiza memória, sem considerar que ela não descreve a estrutura de vizinhança por si só.
Para grafos esparsos a lista de adjacência armazena apenas arestas existentes, consumindo menos memória que matrizes de adjacência que reservam espaço para todas as possíveis arestas.
Raio-X da questão
representação de grafos
avaliacao
representação de grafos · estruturas de dados
Revisar as representações de grafos e suas aplicações em algoritmos.
Escolher a matriz de adjacência, que é mais adequada para grafos densos, em vez da lista de adjacência para grafos esparsos.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Ao projetar um algoritmo para calcular o caminho mais curto entre salas em um mapa da escola, qual representação de…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse grafo…
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Uma equipe de mobilidade urbana modelou as conexões entre 12.000 pontos de ônibus de uma cidade como um grafo não…
- Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
Todas as questões de Armazenamento e Transmissão de dados - Gestão de dados
🔎 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