Qual das seguintes estruturas de dados é mais eficiente para adicionar um novo nó em um grafo?
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
Qual das seguintes estruturas de dados é mais eficiente para adicionar um novo nó em um grafo?
- A) Matriz de Adjacência
- B) Lista de Adjacência
- C) Árvore Geral
- D) Vetor
- E) Tabela Hash
✅ Resposta correta: alternativa B
Resolução passo a passo
- Pergunta-se qual estrutura é mais eficiente para adicionar um novo nó (vértice) em um grafo. Resolvi a questão analisando o custo de inserir um vértice em cada estrutura. Passo 2: Na Lista de Adjacência, o grafo é guardado como um conjunto de listas, uma para cada vértice. Para criar um novo nó, basta acrescentar mais uma entrada vazia ao conjunto, com custo constante, O(1) (ou O(1) amortizado, se a estrutura crescer dinamicamente). Passo 3: Na Matriz de Adjacência, cada novo vértice exige uma nova linha e uma nova coluna, ou seja, é preciso criar uma matriz maior e copiar os dados, o que custa O(V^2) no caso geral. Passo 4: Portanto, a Lista de Adjacência é a mais eficiente para adicionar nós, e o gabarito oficial B está correto. Passo 5: A Matriz de Adjacência está errada porque o redimensionamento quadrático torna a inserção cara. A Árvore Geral está errada porque é um caso particular de grafo sem ciclos e não é a estrutura usual para representar grafos gerais. O Vetor está errado porque não armazena as conexões entre vértices e, ao crescer, também exige realocação e cópia. A Tabela Hash está errada porque armazena pares chave-valor e não representa as arestas do grafo sem uma estrutura adicional.
💡 Dica: Considere as características das estruturas de dados.
Alternativa por alternativa
Acredita que, como a matriz permite acesso direto por índice, qualquer operação nela é rápida. Não percebe que adicionar um nó exige criar uma matriz n por n maior e copiar todos os dados.
Por que engana: Confundir a estrutura que facilita a insercao direta de nos com aquelas que sao mais eficientes para outras operacoes, como busca ou armazenamento.
Adições são simples e rápidas, mantendo a eficiência.
Confunde grafo com árvore, supondo que a árvore geral seja a estrutura padrão para representar grafos. Não percebe que a árvore é um grafo sem ciclos e não serve para representar grafos gerais.
Imagina que inserir no fim de um vetor é sempre rápido e que isso basta para um grafo. Ignora que um vetor de tamanho fixo precisa ser realocado e que não guarda as conexões entre vértices.
Associa a inserção rápida da tabela hash à adição de nós no grafo. Não percebe que a tabela hash guarda pares chave-valor e não representa as arestas sem uma estrutura adicional.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados básicas · representacao de grafos
Revisar as operações em grafos e suas estruturas de dados.
Confundir a estrutura que facilita a insercao direta de nos com aquelas que sao mais eficientes para outras operacoes, como busca ou armazenamento.
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?
- Qual das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- Qual estrutura de dados é mais indicada para representar um grafo em um programa?
- Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- Em qual estrutura de dados os elementos são conectados por arestas?
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