Uma plataforma brasileira de jogos on-line possui 10.000 usuários. Cada usuário mantém conexão, em média, com…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Analisar e utilizar as diferentes formas de representação e consulta a dados em formato digital para pesquisas científicas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma plataforma brasileira de jogos on-line possui 10.000 usuários. Cada usuário mantém conexão, em média, com apenas 50 outros usuários. O sistema precisa consultar rapidamente os amigos de um usuário e permitir a inclusão ou a remoção de conexões. Como a rede é esparsa, guardar uma posição para cada possível par de usuários desperdiçaria grande quantidade de memória. Com base no texto, qual estrutura de dados é mais adequada para representar essa rede de amizades, considerando o baixo número de conexões por usuário e a necessidade de consultar, incluir e remover amizades?
- A) Representação por vetor de usuários.
- B) Representação por fila de usuários.
- C) Representação por lista de vizinhos.
- D) Representação por pilha de usuários.
- E) Representação por tabela de conexões.
✅ Resposta correta: alternativa C
Resolução passo a passo
- O enunciado descreve uma rede de amizades (grafo) com 10.000 usuários, cada um ligado a cerca de 50 outros, ou seja, uma rede esparsa. Os requisitos são: consultar rapidamente os amigos de um usuário e incluir ou remover conexões, e evitar desperdício de memória.
- A matriz de adjacência guarda uma posição para cada par possível de usuários, o que daria cerca de 10.000 x 10.000 = 100 milhões de posições, a maioria vazia. O texto justamente rejeita essa solução.
- Na representação por lista de vizinhos, cada usuário tem uma lista apenas com seus amigos (cerca de 50). A memória usada cresce com o número de conexões, não com o quadrado do número de usuários. Consultar os amigos de alguém é percorrer sua lista, e incluir ou remover uma amizade é uma operação simples sobre essas listas. Por isso ela atende a todos os requisitos.
- Por que as outras estão erradas: a representação por vetor de usuários guarda apenas os usuários, sem registrar as conexões entre eles; a fila e a pilha são estruturas de acesso sequencial que não representam relações entre pares; a tabela de conexões, se for a matriz de pares, reproduz exatamente o desperdício de memória que o texto condena.
- Conclusão: a alternativa correta é a C, lista de vizinhos, que é a estrutura adequada para grafos esparsos.
💡 Dica: Relacione a esparsidade da rede à estrutura que armazena apenas os vizinhos existentes.
Alternativa por alternativa
O aluno pensa que basta guardar os usuários em um vetor para representar a rede, sem perceber que o vetor não registra quem é amigo de quem.
O aluno imagina que a rede pode ser percorrida em ordem de chegada, como uma fila de atendimento, e não percebe que a fila não guarda as relações entre os pares de usuários.
A lista de vizinhos, também chamada de lista de adjacência, armazena para cada usuário apenas os usuários com quem ele possui conexão. Por isso, é adequada para redes esparsas e permite consultar, incluir e remover conexões sem reservar espaço para todos os pares possíveis.
O aluno associa a pilha ao empilhar e desempilhar objetos e acha que ela serve para guardar amigos, sem perceber que a pilha só dá acesso ao último elemento e não permite consultar rapidamente as conexões de um usuário específico.
O aluno entende 'tabela de conexões' como uma tabela completa de pares, o que lembra a matriz de adjacência, e não percebe que ela ocuparia memória para todos os pares possíveis, contrariando o texto.
Por que engana: Escolher uma estrutura linear, como fila ou pilha, por reconhecer apenas a necessidade de armazenar usuários, sem considerar as conexões entre eles.
Raio-X da questão
Lista de vizinhos em grafos
avaliacao
Conceito de grafos e vértices · Operações em estruturas de dados
Revise representações de grafos esparsos e operações de consulta, inserção e remoção de arestas.
Escolher uma estrutura linear, como fila ou pilha, por reconhecer apenas a necessidade de armazenar usuários, sem considerar as conexões entre eles.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Uma plataforma brasileira de comunicação pretende representar as relações entre seus usuários. Nessa plataforma, seguir…
- Qual estrutura de dados é mais apropriada para representar uma rede social onde usuários estão conectados?
- Em um grafo que representa amizades em uma turma (cada aluno é um vértice e cada amizade é uma aresta), cada aluno tem…
- Identifique a estrutura de dados mais adequada para representar uma rede social, onde cada usuário é um nó e as conexões…
- Identifique a estrutura de dados mais adequada para representar as relações entre amigos em uma rede social.
- Em um algoritmo que recomenda amizades entre estudantes com base em conexões mútuas, que estrutura de dados representa…
🔎 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