Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo constante se existe uma aresta entre dois vértices?
- A) Conjunto (set)
- B) Árvore binária
- C) Matriz de incidência
- D) Lista encadeada
- E) Matriz de adjacência — verificação em O(1).
✅ Resposta correta: alternativa E
Resolução passo a passo
- A questão pede a representação de grafo que, sendo denso, permite saber em tempo constante se existe aresta entre dois vértices. Passo 2: Na matriz de adjacência, cada posição (i, j) guarda diretamente se há aresta entre os vértices i e j. Basta acessar a célula, uma operação de tempo constante, O(1). Passo 3: A lista de adjacência exige percorrer a lista de vizinhos de um dos vértices, o que custa até O(grau), e em grafo denso esse grau tende a ser grande. Passo 4: Por isso a matriz é a resposta esperada para grafos densos. Passo 5: Alternativa A (conjunto) está errada no contexto da questão, pois não é a representação clássica de grafo, embora uma tabela hash possa dar busca média rápida. Passo 6: Alternativa B (árvore binária) está errada porque árvore é um grafo acíclico e conexo com estrutura hierárquica, sem a função de representar arestas arbitrárias. Passo 7: Alternativa C (matriz de incidência) está errada porque relaciona vértices e arestas em uma matriz vértices por arestas, e verificar se dois vértices são vizinhos exige varrer colunas. Passo 8: Alternativa D (lista encadeada) está errada porque a busca em lista encadeada é linear no pior caso. Passo 9: Gabarito E confere com a análise feita.
💡 Dica: Considere as características das representações de grafos.
Alternativa por alternativa
Supõe que qualquer estrutura com busca rápida serve como representação de grafo, confundindo a propriedade de busca de um conjunto com a estrutura específica pedida pela questão.
Confunde grafo com árvore, achando que a estrutura hierárquica de árvore binária representa conexões arbitrárias entre vértices.
Acredita que matriz de incidência e matriz de adjacência são equivalentes, sem perceber que a incidência relaciona vértices a arestas e não diretamente vértice a vértice.
Aplica a ideia de acesso direto a uma estrutura sequencial e supõe que a lista permite verificar a aresta sem percorrê-la, quando na verdade a busca é linear.
Por que engana: Confundir a eficiência de verificação de arestas entre a matriz de adjacência e a lista de adjacência, escolhendo a lista por achar que é mais eficiente.
Na matriz de adjacência, a existência de aresta (u,v) é verificada por acesso direto ao elemento [u][v], operação de tempo constante; listas exigem busca nos vizinhos.
Raio-X da questão
representação de grafos
avaliacao
representação de grafos · complexidade de algoritmos
Revisar as propriedades da matriz e lista de adjacência em grafos.
Confundir a eficiência de verificação de arestas entre a matriz de adjacência e a lista de adjacência, escolhendo a lista por achar que é mais eficiente.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Um grafo esparso (muitos vértices e poucas arestas) passa por inserções e remoções frequentes de arestas. Comparando…
Todas as questões de Organização e representação da informação
🔎 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