Uma plataforma brasileira de comunicação pretende representar as relações entre seus usuários. Nessa…

Questão

Uma plataforma brasileira de comunicação pretende representar as relações entre seus usuários. Nessa plataforma, seguir alguém não implica ser seguido por essa pessoa, portanto as relações são direcionadas. Há 10 mil usuários, mas cada usuário segue, em média, apenas 80 pessoas. O sistema precisa consultar com frequência a lista de pessoas seguidas por cada usuário e deve evitar reservar espaço para todas as possíveis combinações entre usuários. Com base nas características dessa plataforma, qual estrutura de dados é mais adequada para representar as relações entre os usuários, considerando que elas são direcionadas, pouco numerosas em comparação com as combinações possíveis e que se deseja consultar os vizinhos de cada usuário?

1. A) Uma árvore binária.
2. B) Uma lista encadeada simples.
3. C) Uma matriz de adjacência.
4. D) Uma lista de adjacência.
5. E) Um registro de dados.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. Identifique as exigências do problema. As relações são direcionadas (seguir não implica ser seguido), há 10 mil usuários, cada um segue em média 80 pessoas, o sistema consulta com frequência os vizinhos de cada usuário e deve evitar reservar espaço para todas as combinações possíveis entre usuários.
2. Calcule a densidade do grafo. Com 10 mil usuários, a matriz completa teria 10.000 x 10.000 = 100 milhões de posições, e a maioria estaria vazia, pois cada usuário segue apenas cerca de 80 pessoas (total aproximado de 800 mil relações). Ou seja, o grafo é esparso.
3. Escolha a estrutura adequada. A lista de adjacência guarda, para cada usuário, apenas a lista das pessoas que ele segue. Assim o espaço ocupado é proporcional ao número de relações existentes (cerca de 800 mil), não ao quadrado do número de usuários, e a consulta dos vizinhos de um usuário é direta e rápida. Além disso, a lista de adjacência representa naturalmente arcos direcionados.
4. Por que as outras estão erradas. A) Uma árvore binária representa hierarquia sem ciclos e não modela bem uma rede social com relações arbitrárias e direcionadas. B) Uma lista encadeada simples é linear e não organiza as relações de cada usuário de forma a representar um grafo. C) A matriz de adjacência funciona, mas reserva espaço para todas as combinações possíveis, exatamente o que o enunciado pede para evitar. E) Um registro de dados agrupa campos de um mesmo item, mas não representa relações entre usuários.
5. Conclusão. Como o grafo é direcionado, esparso e a consulta de vizinhos é frequente, a lista de adjacência é a estrutura mais adequada, alternativa D, que coincide com o gabarito oficial.

💡 Dica: Considere as estruturas de dados mais comuns para relacionamentos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resoluçã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…
• Qual estrutura de dados é mais apropriada para representar uma rede social onde usuários estão conectados?
• 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…
• Considere um projeto em que você precisa modelar a rede de amigos de um usuário em uma rede social. Qual estrutura de…

Todas as questões de Programação - Programação usando grafos e árvores