Text Material Preview
Caminho mínimo O que e o conceito de "caminho minimo" em grafos? a) O caminho mais longo entre dois vertices b) O caminho que percorre todos os vertices do grafo c) O caminho mais curto entre dois vertices em um grafo ponderado d) O caminho com o maior numero de arestas entre dois vertices Resposta correta: c) O caminho mais curto entre dois vertices em um grafo ponderado Explicacao: O caminho minimo em um grafo e aquele que tem o menor custo total, levando em consideracao os pesos das arestas. Qual algoritmo e amplamente utilizado para encontrar o caminho minimo em um grafo ponderado com arestas de peso nao negativo? a) Algoritmo de Dijkstra b) Algoritmo de Prim c) Algoritmo de Kruskal d) Algoritmo de Bellman-Ford Resposta correta: a) Algoritmo de Dijkstra Explicacao: O algoritmo de Dijkstra e eficiente para encontrar o caminho minimo em grafos ponderados, desde que nao haja arestas de peso negativo. O algoritmo de Bellman-Ford pode ser utilizado para encontrar o caminho minimo em grafos com: a) Apenas arestas de peso positivo b) Arestas de peso negativo c) Grafos nao conectados d) Apenas grafos direcionados Resposta correta: b) Arestas de peso negativo Explicacao: O algoritmo de Bellman-Ford e capaz de lidar com grafos que possuem arestas de peso negativo, ao contrario de Dijkstra. Qual e a principal diferenca entre o algoritmo de Dijkstra e o de Bellman-Ford? a) O algoritmo de Dijkstra e mais eficiente, mas so funciona com arestas de peso negativo b) O algoritmo de Bellman-Ford e mais eficiente e resolve todos os casos c) O algoritmo de Dijkstra e mais eficiente, mas funciona apenas para arestas de peso positivo d) O algoritmo de Bellman-Ford e mais simples e mais rapido Resposta correta: c) O algoritmo de Dijkstra e mais eficiente, mas funciona apenas para arestas de peso positivo Explicacao: O algoritmo de Dijkstra e mais eficiente em termos de tempo de execucao, mas so funciona com grafos que nao possuem arestas com pesos negativos, enquanto o Bellman-Ford e mais flexivel e pode lidar com pesos negativos. Em um grafo nao ponderado, qual e o algoritmo mais adequado para encontrar o caminho minimo entre dois vertices? a) Algoritmo de Dijkstra b) Algoritmo de Bellman-Ford c) Algoritmo de Busca em Largura (BFS) d) Algoritmo de A* Resposta correta: c) Algoritmo de Busca em Largura (BFS) Explicacao: Em grafos nao ponderados, a Busca em Largura (BFS) encontra o caminho minimo, pois explora os vertices em camadas, garantindo que o primeiro caminho encontrado seja o mais curto. Em um grafo com ciclos negativos, qual algoritmo pode ser usado para detectar ciclos negativos? a) Algoritmo de Dijkstra b) Algoritmo de Bellman-Ford c) Algoritmo de Prim d) Algoritmo de Floyd-Warshall Resposta correta: b) Algoritmo de Bellman-Ford Explicacao: O algoritmo de Bellman-Ford pode ser usado para detectar ciclos negativos, verificando se e possivel relaxar uma aresta mais de |V|-1 vezes (onde |V| e o numero de vertices). No algoritmo de Dijkstra, o que acontece quando o vertice de menor distancia e selecionado para ser processado? a) Ele e removido do grafo permanentemente b) Ele e marcado como visitado e nao sera processado novamente c) Ele e adicionado a uma fila de espera para ser reprocessado mais tarde d) Ele e reavaliado com base em novos caminhos possiveis Resposta correta: b) Ele e marcado como visitado e nao sera processado novamente Explicacao: Quando o vertice de menor distancia e processado no algoritmo de Dijkstra, ele e marcado como visitado, garantindo que nao seja reprocessado. O que e um grafo ponderado? a) Um grafo onde todos os vertices tem o mesmo grau b) Um grafo onde todas as arestas tem o mesmo peso c) Um grafo onde as arestas tem pesos diferentes d) Um grafo sem ciclos Resposta correta: c) Um grafo onde as arestas tem pesos diferentes Explicacao: Em um grafo ponderado, cada aresta possui um peso ou custo associado, que pode representar, por exemplo, a distancia, o tempo ou qualquer outro tipo de custo. O que o algoritmo de Floyd-Warshall resolve? a) Caminho minimo entre dois vertices apenas b) Caminho minimo entre todos os pares de vertices c) Caminho minimo em grafos nao ponderados d) Caminho minimo apenas em grafos direcionados Resposta correta: b) Caminho minimo entre todos os pares de vertices Explicacao: O algoritmo de Floyd-Warshall e utilizado para encontrar o caminho minimo entre todos os pares de vertices em um grafo. O que e a "relaxacao" no contexto de algoritmos para caminho minimo? a) Processar um vertice varias vezes b) Atualizar a distancia de um vertice quando uma rota mais curta e encontrada c) Atrasar a execucao de um algoritmo para evitar sobrecarga d) Descartar arestas que nao podem ser usadas Resposta correta: b) Atualizar a distancia de um vertice quando uma rota mais curta e encontrada Explicacao: Relaxacao e o processo de atualizar a distancia de um vertice, caso um caminho mais curto seja encontrado para alcanca-lo. Em um grafo com n vertices e m arestas, qual e a complexidade temporal do algoritmo de Dijkstra utilizando uma fila de prioridade implementada com um heap binario? a) O(n + m) b) O(n2) c) O((n + m) log n) d) O(n log n) Resposta correta: c) O((n + m) log n) Explicacao: A complexidade temporal do algoritmo de Dijkstra com uma fila de prioridade implementada por um heap binario e O((n + m) log n), onde n e o numero de vertices e m o numero de arestas. Quando o algoritmo de Dijkstra encontra o caminho minimo de um vertice de origem para todos os outros vertices em um grafo, qual e o estado final dos vertices processados? a) Todos os vertices tem o mesmo valor de distancia b) Todos os vertices tem o valor de distancia mais curto possivel da origem c) Somente o vertice de origem tem a distancia minima d) Somente os vertices conectados diretamente ao vertice de origem sao processados Resposta correta: b) Todos os vertices tem o valor de distancia mais curto possivel da origem Explicacao: Ao final do algoritmo de Dijkstra, todos os vertices terao a menor distancia possivel da origem, considerando as arestas do grafo. Em um grafo direcionado, qual e a principal caracteristica do caminho minimo entre dois vertices? a) Ele sempre passara pelo vertice de maior grau b) Ele pode ou nao ser unico, dependendo das arestas c) Ele e sempre o caminho com o maior numero de arestas d) Ele nunca inclui arestas com peso negativo Resposta correta: b) Ele pode ou nao ser unico, dependendo das arestas Explicacao: O caminho minimo pode ser unico ou ter multiplas solucoes, dependendo das arestas e dos pesos no grafo. Qual e a principal limitacao do algoritmo de Dijkstra? a) Nao pode ser usado para grafos direcionados b) Nao encontra caminhos entre todos os pares de vertices c) Nao funciona com grafos ponderados com arestas de peso negativo d) Nao encontra o caminho minimo em grafos nao ponderados Resposta correta: c) Nao funciona com grafos ponderados com arestas de peso negativo Explicacao: O algoritmo de Dijkstra assume que todas as arestas tem peso nao negativo. Caso contrario, ele pode nao produzir o resultado correto. O que e um grafo completo? a) Um grafo em que ha uma aresta entre cada par de vertices b) Um grafo em que todos os vertices tem o mesmo grau c) Um grafo em que todas as arestas tem o mesmo peso d) Um grafo que contem pelo menos um ciclo Resposta correta: a) Um grafo em que ha uma aresta entre cada par de vertices Explicacao: Em um grafo completo, qualquer par de vertices esta diretamente conectado por uma aresta. Como o algoritmo de A* melhora o algoritmo de Dijkstra? a) Ele usa uma heuristica para guiar a busca,
