Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção…
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 algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos e permitir backtracking, qual estrutura de dados é mais adequada para armazenar o caminho e remover rapidamente o último vértice?
- A) Lista ligada para armazenar caminhos com inserção no início.
- B) Pilha (stack) — usar push/pop para adicionar e remover o último vértice em O(1).
- C) Árvore binária para organizar os vértices visitados.
- D) Vetor dinâmico para armazenar o caminho de busca.
- E) Fila (queue) para tratar a ordem dos vértices visitados.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Em uma DFS, o caminho atual é a sequência de vértices pela qual o algoritmo está descendo. Quando um vértice não tem mais vizinhos a explorar, o algoritmo faz backtracking, ou seja, remove o último vértice do caminho e volta ao anterior. Essa remoção segue a ordem inversa da inserção (o último que entrou é o primeiro a sair). Passo 2: Essa regra é exatamente o comportamento LIFO (last in, first out) da pilha. Com push para adicionar e pop para remover o último vértice, ambas as operações são O(1), e o topo da pilha dá acesso imediato ao vértice atual para checar ciclos. Passo 3: Por que as outras estão erradas: A) uma lista ligada com inserção no início funciona, mas a questão pede a estrutura conceitualmente adequada à ordem LIFO, e a alternativa descreve apenas um detalhe de implementação. C) uma árvore binária organiza dados por hierarquia de valores e não é a estrutura natural para registrar a sequência do caminho atual. D) um vetor dinâmico pode ser usado na prática, pois remover do fim é O(1) amortizado, mas ele é justamente a implementação comum da pilha; o conceito pedido pela questão é a pilha. E) uma fila é FIFO, então removeria o vértice mais antigo, o que quebra o backtracking. Passo 4: Conclusão: o gabarito B está correto. A alternativa D é a única que poderia gerar dúvida, porque funciona na prática, mas a resposta mais adequada e conceitual é a pilha.
💡 Dica: Considere as características das estruturas de dados em algoritmos.
Alternativa por alternativa
Acha que a inserção no início de uma lista ligada é a forma natural de controlar a ordem do caminho, sem perceber que o que importa é a política de remoção do último elemento.
Por que engana: Confundir a pilha com a fila, escolhendo a fila como estrutura para armazenar o caminho atual.
A pilha implementa LIFO; durante DFS empilha-se ao entrar e desempilha-se ao voltar, possibilitando backtracking eficiente com operações push/pop em tempo constante.
Associa qualquer organização de vértices a uma árvore binária, confundindo a árvore de busca ou a árvore de DFS com a estrutura que guarda o caminho atual.
Acredita que qualquer estrutura que permita acesso ao último elemento serve, sem reconhecer que a questão pede o tipo abstrato LIFO, que a pilha expressa diretamente.
Acha que fila é a estrutura de ordem de visita, mas a fila remove o elemento mais antigo (FIFO), o que faria o backtracking voltar ao vértice errado.
Raio-X da questão
busca em profundidade
avaliacao
estruturas de dados · algoritmos de busca
Revisar estruturas de dados adequadas para algoritmos de busca.
Confundir a pilha com a fila, escolhendo a fila como estrutura para armazenar o caminho atual.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
- Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
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