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
- A turma de Lucas guardou no mesmo lugar os arquivos de um trabalho sobre alimentação: pesquisas, imagens, rascunhos e a…
- — A conexão desta base rural cai várias vezes por dia — explicou a coordenadora da brigada de incêndio. Durante uma…
- — A página fica toda branca no meu celular — disse Rafael, na biblioteca pública, ao procurar o calendário de vacinação…
- — O pacote não abre mais no computador da biblioteca, e os vídeos do celular já foram apagados — avisou Renato…
- — O material chegou, mas só aparece um arquivo chamado sons.zip — disse Caio, ao receber gravações da biblioteca do…
- Como contar a trajetória de uma comunidade sem que o público apenas leia um cartaz? Para uma mostra cultural, estudantes…
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