Considere um problema que envolve a otimização de rotas entre várias cidades. Qual estrutura é mais eficiente…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere um problema que envolve a otimização de rotas entre várias cidades. Qual estrutura é mais eficiente para representar essas rotas?
- A) Lista
- B) Árvore
- C) Grafo ponderado
- D) Matriz de adjacência
- E) Tabela
✅ Resposta correta: alternativa C
Resolução passo a passo
- Identifique o problema. As cidades são pontos e as rotas são ligações entre esses pontos, cada uma com um custo (distância, tempo ou preço). Esse é o modelo de um grafo, em que cidades são vértices e rotas são arestas.
- Note que o problema pede otimização, ou seja, encontrar o caminho de menor custo. Por isso cada aresta precisa carregar um peso. Um grafo ponderado guarda exatamente essa informação e permite aplicar algoritmos como Dijkstra ou Floyd-Warshall.
- Avalie as alternativas. A lista é linear e não representa bem conexões de muitos para muitos entre cidades. A árvore é um grafo sem ciclos e não serve para modelar todas as rotas possíveis. A matriz de adjacência também representa um grafo, mas em redes grandes e esparsas desperdiça muito espaço com entradas vazias, sendo uma forma de implementação e não a estrutura conceitual mais adequada. A tabela organiza dados, mas não expressa diretamente a conectividade entre cidades.
- Conclusão. O grafo ponderado é a estrutura mais adequada porque modela cidades, conexões e custos de forma direta e natural, o que está de acordo com o gabarito oficial C.
💡 Dica: Considere as características das estruturas de dados disponíveis.
Alternativa por alternativa
Imagina que todas as cidades podem ser organizadas em sequência, como em uma fila ou lista de pontos, o que não reflete as múltiplas conexões possíveis entre elas.
Associa rotas a uma hierarquia de ramos, achando que a árvore conecta todas as cidades, mas esquece que uma árvore não tem ciclos e não representa alternativas de caminho para otimização.
Grafo com pesos permite otimizar rotas considerando distâncias.
Acredita que a matriz de adjacência é a forma mais eficiente por ser uma estrutura tabular de acesso rápido, sem considerar o desperdício de espaço em redes grandes e pouco conectadas.
Por que engana: Confundir grafos ponderados com outras estruturas, como listas ou matrizes, não entendendo a necessidade de pesos para otimização.
Confunde a representação de dados em tabela, útil para armazenar registros, com a modelagem de conexões entre cidades, que exige uma estrutura de rede.
Raio-X da questão
otimização de rotas
avaliacao
estruturas de dados básicas · conceito de grafos
Revisar estruturas de dados utilizadas em algoritmos de otimização.
Confundir grafos ponderados com outras estruturas, como listas ou matrizes, não entendendo a necessidade de pesos para otimização.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
- Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
- Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
- Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
- Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
- — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…
🔎 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