Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada para empilhar vértices a visitar durante a exploração?
- A) Lista encadeada
- B) Árvore binária
- C) Pilha (stack).
- D) Fila (queue)
- E) Tabela hash
✅ Resposta correta: alternativa C
Resolução passo a passo
- A busca em profundidade (DFS) explora o grafo indo o mais fundo possível por um caminho antes de retroceder. Na versão iterativa, isso é feito com uma estrutura que segue a regra LIFO (último a entrar, primeiro a sair).
- Essa estrutura é a pilha (stack). A cada vértice descoberto, ele é empilhado; o próximo vértice a ser visitado é o do topo da pilha, o que faz a exploração seguir sempre o caminho mais recente.
- Por que as outras estão erradas: a lista encadeada é apenas uma forma de armazenar dados, não define a ordem de remoção exigida pela DFS; a árvore binária é um tipo de grafo/estrutura de dados que o algoritmo percorre, não a estrutura auxiliar de controle; a fila (queue) segue a regra FIFO e produz a busca em largura (BFS), não a DFS; a tabela hash serve para busca rápida por chave e não define ordem de exploração.
- Conclusão: a alternativa C está correta e coincide com o gabarito oficial.
💡 Dica: Lembre-se da estrutura de dados utilizada na DFS.
Alternativa por alternativa
O aluno confunde a estrutura de armazenamento com a disciplina de acesso; acredita que qualquer lista encadeada basta para controlar a exploração.
O aluno associa DFS a árvores, pois a busca em profundidade é frequentemente ilustrada em árvores binárias, e não percebe que a estrutura auxiliar é outra.
A DFS explora caminhos em profundidade; a versão iterativa simula a recursão com uma pilha LIFO que armazena vértices a serem processados e permite retornar ao vértice anterior.
O aluno lembra que a busca em grafos usa filas, confundindo a BFS (busca em largura, FIFO) com a DFS (busca em profundidade, LIFO).
Por que engana: Confundir a pilha com a fila, escolhendo a fila como estrutura de dados para a busca em profundidade.
O aluno pensa que, por a hash permitir marcar rapidamente os vértices já visitados, ela é a estrutura central da exploração, confundindo controle de visitados com ordem de visita.
Raio-X da questão
busca em profundidade
avaliacao
estruturas de dados · algoritmos de busca
Revisar o funcionamento do algoritmo DFS e suas estruturas de dados.
Confundir a pilha com a fila, escolhendo a fila como estrutura de dados para a busca em profundidade.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
- Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
- — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
- Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
- — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
- Ontem o mapa do festival me mandou dar uma volta enorme reclamou uma visitante. Para reduzir aglomeracoes, a…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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