Teste - Teoria dos Grafos

[bernardino]

2. Em um hospital de grande porte, um sistema de navegação interna é implementado para guiar pacientes e funcionários até os setores desejados. O hospital é representado como um grafo não ponderado, onde os nós representam salas e as arestas representam corredores conectando as salas.

a) Para encontrar o menor caminho entre a recepção e um determinado setor, qual algoritmo de busca deve ser utilizado?
b) DFS, pois percorre o grafo explorando cada caminho completamente antes de retroceder.
c) BFS, pois percorre os nós camada por camada, garantindo o menor número de passos.
d) DFS, pois encontra caminhos mais rapidamente ao seguir um ramo do grafo sem explorar outras opções.
e) BFS e DFS sempre encontram o menor caminho com a mesma eficiência.
f) Nenhum dos dois, pois apenas o algoritmo de Dijkstra pode resolver o problema.

=====

Pergunta 3
Uma empresa de segurança cibernética está analisando a propagação de um vírus em uma rede de computadores. Cada computador é um nó, e as conexões entre eles representam possíveis transmissões do vírus. A equipe deseja identificar todos os computadores infectados partindo de um único computador infectado inicialmente.

Qual estratégia de busca deve ser utilizada para garantir que todos os computadores sejam examinados?

a) Apenas BFS pode garantir que todos os computadores serão examinados.
b) Apenas DFS pode garantir que todos os computadores serão examinados.
c) BFS e DFS podem ser usados para esse propósito, pois ambos exploram o grafo inteiro.
d) Nenhuma das duas é adequada; um algoritmo especializado deve ser usado.
e) Somente algoritmos de Inteligência Artificial podem resolver esse problema.

=====

Pergunta 4
1
Ponto
Pergunta 4
Um engenheiro de software está desenvolvendo um algoritmo para buscar informações em uma árvore de diretórios de um sistema operacional. O objetivo é encontrar um arquivo específico, e a busca pode ser interrompida assim que o arquivo for encontrado.

Qual algoritmo é mais adequado para essa tarefa?


BFS, pois garante que o menor número de diretórios será explorado antes de encontrar o arquivo.


DFS, pois segue cada caminho até o final antes de retroceder, o que pode ser mais eficiente caso o arquivo esteja em um caminho profundo.


BFS e DFS são igualmente eficientes para essa tarefa.


Nenhum dos dois é adequado, pois somente um algoritmo de força bruta pode resolver esse problema.


DFS só pode ser usado se a estrutura for um grafo não cíclico.

=====

Pergunta 5
1
Ponto
Pergunta 5
Em um jogo de tabuleiro, um jogador precisa encontrar a melhor sequência de movimentos para resolver um quebra-cabeça no menor número de passos. Considerando que cada movimento possível pode ser representado como um nó em um grafo, qual estratégia de busca é a mais adequada para encontrar a solução ótima em termos de menor número de movimentos?


BFS, pois explora todas as possibilidades de menor profundidade primeiro, garantindo a solução ótima.


DFS, pois segue um caminho profundamente antes de testar outras opções.


DFS é melhor do que BFS para qualquer problema de busca.


BFS e DFS sempre retornam a melhor solução com a mesma eficiência.


Nenhuma das opções, pois apenas aprendizado de máquina pode resolver problemas desse tipo.

=====

Pergunta 6
1
Ponto
Pergunta 6
Uma empresa de logística deseja desenvolver um software para otimizar a entrega de encomendas em uma grande cidade. O sistema representa a cidade como um grafo, onde os nós são bairros e as arestas representam ruas conectando os bairros.

Se todas as ruas tiverem o mesmo peso (distância igual), qual estratégia de busca deve ser usada para encontrar o menor número de ruas percorridas entre o armazém e o destino final?


DFS, pois busca rapidamente um caminho e pode ser interrompida assim que encontrar uma solução.


BFS, pois explora todas as possibilidades de menor profundidade primeiro, garantindo o menor caminho.


DFS e BFS sempre encontram o menor caminho com a mesma eficiência.


Nenhum dos dois


DFS é a única opção válida, pois explora um caminho por completo antes de testar outro.

=====

Pergunta 7
1
Ponto
Pergunta 7
Um cientista de dados está analisando um grafo de interações sociais em uma rede de mensagens instantâneas. O objetivo é encontrar grupos de usuários fortemente conectados, ou seja, subconjuntos de usuários que se comunicam mais entre si do que com outros usuários.

Qual estratégia de busca é mais adequada para descobrir componentes conexas nesse grafo?


Apenas BFS pode ser utilizada para encontrar componentes conexas.


Apenas DFS pode ser utilizada para encontrar componentes conexas.


Tanto BFS quanto DFS podem ser usados para encontrar componentes conexas.


Nenhuma das duas é útil para esse problema; apenas Redes Neurais podem encontrar componentes conexas.


DFS é a única opção válida, pois explora caminhos até o final antes de retroceder.

=====

Pergunta 8
1
Ponto
Pergunta 8
Em um sistema de roteamento de tráfego, cada cidade é representada como um nó e cada estrada é uma aresta com um peso que representa o tempo médio de viagem.

Se o objetivo é encontrar o caminho mais rápido entre duas cidades, qual abordagem de busca deve ser usada?


BFS, pois encontra sempre o menor caminho primeiro.


DFS, pois explora os caminhos completamente antes de retroceder.


Nenhuma das duas, pois BFS e DFS não levam em conta o peso das arestas.


DFS é melhor, pois pode explorar atalhos mais rapidamente.


BFS pode ser usada desde que a estrutura do grafo seja acíclica.

=====

Pergunta 9
1
Ponto
Pergunta 9
Nos programas em C, qual estrutura de dados é utilizada para implementar a BFS?


Pilha (Stack)


Lista encadeada (Linked List)


Fila (Queue)


Heap


Árvore binária

=====

Pergunta 10
1
Ponto
Pergunta 10
No código, a matriz de adjacência é usada para representar um grafo. Como podemos determinar se há uma aresta entre dois vértices u e v?


Verificando se matriz_adj[v] == 1


Percorrendo toda a matriz e contando conexões


Verificando a saída da BFS


Checando a quantidade de vértices adjacentes


BFS não pode verificar conexões entre vértices

=====