Busca em profundidade (DFS)

Prévia do material em texto

Busca em profundidade (DFS) 
O que significa a sigla DFS no contexto de algoritmos de busca?
a) Depth First Search (Busca em Profundidade).
b) Data Flow System (Sistema de Fluxo de Dados).
c) Dynamic File Storage (Armazenamento Dinamico de Arquivos).
d) Digital Frequency Scan (Varredura de Frequencia Digital).
Resposta explicativa: DFS significa Depth First Search, ou Busca em Profundidade, um algoritmo
que percorre um grafo explorando o maximo possivel de cada caminho antes de retroceder.
Qual e o principal conceito por tras da busca em profundidade?
a) Explorar todos os vizinhos de um no antes de seguir para outro.
b) Explorar um caminho ate o fim antes de tentar outros caminhos.
c) Escolher o no de maior grau primeiro.
d) Percorrer os nos de forma aleatoria.
Resposta explicativa: O DFS tenta ir o mais fundo possivel em um caminho antes de voltar
(backtracking) e explorar outros ramos do grafo, o que o diferencia da busca em largura (BFS).
Que estrutura de dados e mais comumente usada para implementar a DFS de forma iterativa?
a) Fila (queue).
b) Pilha (stack).
c) Lista duplamente encadeada.
d) Tabela hash.
Resposta explicativa: A DFS utiliza uma pilha para armazenar os nos que ainda precisam ser
explorados, pois ela segue a logica LIFO (ultimo a entrar, primeiro a sair).
Em uma implementacao recursiva da DFS, o que substitui a pilha explicitamente usada na versao
iterativa?
a) Um vetor auxiliar.
b) A propria pilha de chamadas do sistema.
c) Uma fila interna.
d) Um dicionario de nos.
Resposta explicativa: Na versao recursiva, o controle de profundidade e gerenciado
automaticamente pela pilha de chamadas da linguagem de programacao, eliminando a
necessidade de uma pilha manual.
Em que tipo de problema o algoritmo DFS e mais indicado?
a) Quando se busca o caminho mais curto entre dois nos.
b) Quando e necessario visitar todos os nos e explorar caminhos ate o fim.
c) Quando o grafo e muito grande e precisa de otimizacao de memoria.
d) Quando o grafo e ponderado e direcionado.
Resposta explicativa: O DFS e mais indicado em situacoes em que se deseja percorrer todos os
caminhos possiveis, como em problemas de labirinto, backtracking e deteccao de ciclos.
Qual das seguintes afirmacoes sobre DFS e verdadeira?
a) DFS garante sempre o caminho mais curto.
b) DFS pode ficar preso em ciclos se nao houver controle de visitados.
c) DFS precisa de mais memoria que BFS.
d) DFS so funciona em grafos nao direcionados.
Resposta explicativa: Caso o algoritmo nao marque os nos ja visitados, ele pode entrar em um loop
infinito, visitando os mesmos nos repetidamente.
Qual e a principal diferenca entre DFS e BFS?
a) BFS explora primeiro em profundidade e DFS em largura.
b) DFS utiliza pilha, enquanto BFS usa fila.
c) DFS e sempre mais rapido que BFS.
d) BFS so funciona em arvores.
Resposta explicativa: A diferenca esta na estrutura usada: DFS usa pilha, priorizando profundidade,
enquanto BFS usa fila, explorando a vizinhanca de cada no antes de ir mais fundo.
Qual e a complexidade de tempo do algoritmo DFS em um grafo representado por lista de
adjacencia?
a) O(V + E), onde V e o numero de vertices e E o numero de arestas.
b) O(V2).
c) O(E2).
d) O(log V).
Resposta explicativa: A complexidade de DFS depende do numero de vertices e arestas, pois cada
no e aresta e visitado uma unica vez, resultando em O(V + E).
Como o DFS pode ser util na deteccao de ciclos em um grafo?
a) Ele identifica ciclos ao contar o numero de arestas.
b) Ele verifica se um no ja visitado e alcancado novamente antes de finalizar a recursao.
c) Ele compara as alturas das subarvores.
d) Ele apenas soma os pesos das arestas.
Resposta explicativa: Durante a execucao do DFS, se um no ja visitado for encontrado novamente
enquanto ainda esta na pilha de recursao, significa que existe um ciclo no grafo.
Em qual tipo de problema o DFS costuma ser utilizado para encontrar solucoes possiveis por
tentativa e erro?
a) Ordenacao de vetores.
b) Backtracking (como Sudoku ou labirintos).
c) Compressao de dados.
d) Busca binaria.
Resposta explicativa: O DFS e amplamente usado em algoritmos de backtracking, pois permite
explorar completamente cada opcao ate o final antes de retroceder e testar alternativas.
O que acontece se a busca em profundidade for aplicada em um grafo desconexo?
a) Apenas um componente e percorrido.
b) Todos os componentes sao automaticamente visitados.
c) A busca falha e retorna erro.
d) DFS se transforma em BFS.
Resposta explicativa: O DFS, iniciado de um unico vertice, percorre apenas o componente
conectado a ele. Para visitar todo o grafo, e necessario reiniciar o DFS em cada componente nao
visitado.
Qual e o comportamento do DFS em uma arvore binaria?
a) Ele visita os nos em ordem de nivel.
b) Ele percorre a arvore seguindo um caminho completo antes de retroceder.
c) Ele visita apenas folhas.
d) Ele calcula as alturas dos nos.
Resposta explicativa: Na arvore binaria, o DFS percorre um caminho ate chegar a uma folha, e so
entao retorna para explorar os ramos restantes, seguindo o principio da profundidade.
Como o DFS pode ser adaptado para gerar uma ordenacao topologica em um grafo aciclico
direcionado (DAG)?
a) Registrando a ordem de visita em uma fila.
b) Usando a pilha para armazenar a ordem de termino de cada vertice.
c) Ignorando as arestas direcionadas.
d) Somando os pesos das arestas.
Resposta explicativa: A ordenacao topologica pode ser obtida adicionando cada no a pilha apos
visitar todos os seus vizinhos, o que garante a ordem correta de precedencia.
Qual das opcoes abaixo descreve corretamente o comportamento de backtracking na DFS?
a) O algoritmo ignora caminhos invalidos sem voltar atras.
b) Quando chega a um beco sem saida, ele retorna ao ultimo ponto de decisao para explorar outro
caminho.
c) Ele se repete infinitamente ate encontrar a solucao.
d) Ele escolhe sempre o caminho mais curto disponivel.
Resposta explicativa: No backtracking, quando a DFS atinge um no sem alternativas validas, ela
retrocede ate o ultimo no com opcoes nao exploradas e tenta outra rota.
Qual das seguintes limitacoes pode ocorrer ao usar DFS em grafos muito grandes?
a) Falta de precisao numerica.
b) Estouro da pilha de recursao.
c) Dificuldade em marcar nos visitados.
d) Perda de conexoes entre arestas.
Resposta explicativa: Em grafos muito profundos, a versao recursiva da DFS pode causar stack
overflow, pois o numero de chamadas recursivas ultrapassa o limite da pilha de execucao.