Identifique qual estrutura de dados é mais adequada para representar um grafo que conecta cidades. Considere a…
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
Identifique qual estrutura de dados é mais adequada para representar um grafo que conecta cidades. Considere a relação entre elas.
- A) Lista encadeada
- B) Matriz de adjacência
- C) Registro
- D) Lista estática
- E) Árvore
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado pede a estrutura mais adequada para representar um grafo que conecta cidades, considerando a relação entre elas. Um grafo é formado por vértices (as cidades) e arestas (as ligações entre pares de cidades). Passo 2: Resolvendo sem olhar o gabarito, a estrutura que representa diretamente a relação entre cada par de vértices é a matriz de adjacência. Em uma matriz n x n, a posição (i, j) indica se a cidade i está ligada à cidade j, e pode guardar também o peso ou a distância da ligação. Passo 3: Por que a alternativa B está correta: ela registra explicitamente todas as relações possíveis entre as cidades, permitindo verificar em tempo constante se existe ligação entre duas cidades. Passo 4: Por que A está errada: a lista encadeada guarda elementos em sequência, sem representar naturalmente uma relação arbitrária entre cidades; ela só serviria como base de uma lista de adjacência, que não é a opção pedida. Passo 5: Por que C está errada: o registro agrupa campos de tipos diferentes de um mesmo item, mas não representa conexões entre itens. Passo 6: Por que D está errada: a lista estática é um vetor de tamanho fixo, que armazena elementos em sequência e não expressa relações entre eles. Passo 7: Por que E está errada: a árvore é um caso particular de grafo, sem ciclos e com hierarquia, e cidades ligadas em malha podem formar ciclos, então ela não é a representação geral mais adequada. Passo 8: Conclusão: concordo com o gabarito oficial, B, pois a matriz de adjacência é a representação mais direta da relação entre as cidades.
💡 Dica: Relacione a estrutura escolhida à representação das conexões entre todos os pares de cidades.
Alternativa por alternativa
Acredita que a lista encadeada é a melhor forma de representar conexões porque os nós ficam ligados uns aos outros. Confunde a ligação sequencial de uma lista com uma relação arbitrária entre vértices de um grafo.
Matrizes de adjacência são eficazes para representar grafos, mostrando conexões entre todas as cidades.
Imagina que o registro serve para guardar as cidades e suas ligações porque reúne várias informações em um só item. Não percebe que o registro agrupa campos de um único elemento e não modela relações entre elementos.
Pensa que um vetor de tamanho fixo, como a lista estática, basta para guardar as cidades e suas conexões. Não considera que a estrutura precisa expressar a relação entre pares de cidades, o que um vetor sequencial não faz diretamente.
Supõe que toda rede de cidades é hierárquica, como uma árvore, e que basta representá-la com nós pai e filho. Desconhece que árvores são grafos sem ciclos e que um grafo de cidades pode ter caminhos alternativos entre dois pontos.
Por que engana: Confundir estruturas lineares ou hierárquicas, como listas e árvores, com a matriz de adjacência, que representa diretamente as conexões entre os vértices.
Raio-X da questão
Matriz de adjacência em grafos
fixacao
Conceito de vértices e arestas · Estruturas de dados básicas
Revise como matrizes de adjacência representam vértices e conexões em grafos.
Confundir estruturas lineares ou hierárquicas, como listas e árvores, com a matriz de adjacência, que representa diretamente as conexões entre os vértices.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Durante uma campanha de arrecadação, uma escola receberá alimentos e produtos de higiene para montar cestas destinadas a…
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Em ações de fiscalização ambiental no Brasil, imagens de satélite podem ser comparadas em diferentes datas para indicar…
- Uma família criou um programa para organizar as compras do mês. O programa recebe os preços, soma os produtos e…
- — Sem conexão estável no rio, o alerta precisa aparecer no próprio tablet — afirmou a técnica que acompanha sons de aves…
- Falhas em formulários digitais de serviços públicos levaram um setor de tecnologia a testar cinco programas de análise…
🔎 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