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
- Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo…
- Descreva sucintamente como verificar se um grafo simples não direcionado é k-regular usando sua lista de adjacência; que…
- Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
- Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um índice…
- Em um autômato orientado por eventos que registra leituras periódicas de um sensor, qual estrutura de dados é mais…
- Projete um autômato baseado em eventos para gerenciar reservas de salas multimídia na escola: descreva estados, eventos…
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