Para representar uma rede de sensores esparsa com arestas ponderadas (por distância ou latência), qual…
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
Para representar uma rede de sensores esparsa com arestas ponderadas (por distância ou latência), qual estrutura de dados é mais eficiente para armazenar a rede e consultar as ligações de cada sensor, e por quê?
- A) Pilha, empilhando as arestas na ordem em que foram lidas.
- B) Matriz de adjacência, representando todos os pares possíveis.
- C) Array simples, armazenando todas as informações sem estrutura.
- D) Lista de adjacência com registros de aresta (vértice destino, peso).
- E) Matriz de incidência, com uma linha por vértice e uma coluna por aresta.
✅ Resposta correta: alternativa D
Resolução passo a passo
- A questão pede a estrutura mais eficiente para armazenar uma rede esparsa (poucas arestas em relação ao número possível de pares) com pesos, e para consultar as ligações de cada sensor.
- Em um grafo esparso, a maioria dos pares de vértices não é ligada. Uma estrutura que guarde apenas as arestas existentes economiza memória e evita percorrer pares vazios.
- A lista de adjacência faz exatamente isso: para cada sensor (vértice), guarda uma lista apenas com seus vizinhos, e cada registro traz o vértice destino e o peso (distância ou latência). O espaço gasto é proporcional a vértices mais arestas, e consultar as ligações de um sensor é percorrer apenas a sua lista.
- Por que as outras estão erradas. A) Pilha é estrutura de acesso LIFO, não organiza ligações por sensor, e não permite consultar eficientemente os vizinhos de um vértice. B) A matriz de adjacência ocupa espaço proporcional ao quadrado do número de vértices, desperdiçando memória em uma rede esparsa. C) Um array sem estrutura obriga a varrer todas as informações para achar as ligações de um sensor, sendo ineficiente. E) A matriz de incidência também ocupa espaço proporcional a vértices vezes arestas, sendo pouco prática para consultar vizinhos diretamente.
- Conclusão: a lista de adjacência com registros (destino, peso) é a melhor escolha, combinando baixo consumo de memória e consulta rápida das ligações de cada sensor.
💡 Dica: Considere a esparsidade da rede e a eficiência para percorrer as ligações de cada sensor.
Alternativa por alternativa
Acredita que qualquer estrutura sequencial de arestas serve, sem perceber que a pilha só dá acesso ao topo e não organiza as ligações por sensor.
Supõe que a matriz de adjacência é sempre a melhor opção por ser organizada, sem considerar que ela reserva espaço para todos os pares possíveis, inclusive os inexistentes em uma rede esparsa.
Por que engana: Escolher a matriz de adjacência por parecer mais direta, sem considerar que ela armazena também pares de vértices sem ligação e consome mais espaço em grafos esparsos.
Pensa que guardar os dados de forma bruta basta, sem perceber que consultar as ligações de um sensor exigiria varrer todas as informações a cada consulta.
Em uma rede esparsa, a lista de adjacência armazena apenas as ligações existentes e seus pesos, sem reservar espaço para todos os pares de vértices, e dá acesso direto às ligações de cada sensor.
Confunde a matriz de incidência com uma representação eficiente, não notando que ela cresce com vértices vezes arestas e não facilita listar diretamente os vizinhos de cada sensor.
Raio-X da questão
Lista de adjacência ponderada
avaliacao
Representação de grafos em estruturas · Grafos esparsos e ponderados
Revise representações de grafos e compare o espaço usado por matrizes e listas de adjacência.
Escolher a matriz de adjacência por parecer mais direta, sem considerar que ela armazena também pares de vértices sem ligação e consome mais espaço em grafos esparsos.
ciencia_tecnologia
pensamento_critico
cientifico
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