Prova1 - Algoritmos em Grafos

Prévia do material em texto

27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 1/7
1_Primeira Avaliação RRC
Entrega 20 de abr de 2021 em 22:30 Pontos 30 Perguntas 8 
Disponível 20 de abr de 2021 em 20:50 - 20 de abr de 2021 em 22:30 aproximadamente 2
horas
 Limite de tempo 100 Minutos
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 71 minutos 28,67 de 30
 As respostas corretas estão ocultas.
Pontuação deste teste: 28,67 de 30
Enviado 20 de abr de 2021 em 22:06
Esta tentativa levou 71 minutos.
INSTRUÇÕES DA AVALIAÇÃO NO RRC:
• A Avaliação tem a duração de 100 minutos e se realizará das 20:50 às 22:30 horas, horário de
Brasília. 
• Ao clicar em "1_Primeira Avaliação RCC" no dia 20/04/2021 no menu “testes” você iniciará a
prova. A partir daí não será possível desistir de realizá-la.
• A prova é composta de 08 questões objetivas, a pontuação desta descrita na mesma.
• Ao final do teste não se esqueça de enviá-lo clicando no botão “ENVIAR TESTE”. Só utilize esse
botão quando tiver finalizado a avaliação
 
ATENÇÃO: Todas as provas iniciadas e que não houverem sido submetidas, serão automaticamen
encerradas pelo sistema transcorridos os 100 minutos de duração, ou às 22:30 horas – horário em
que se encerra a aplicação.
 
BOA SORTE!!
3,5 / 3,5 ptsPergunta 1
https://pucminas.instructure.com/courses/53940/quizzes/181089/history?version=1
27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 2/7
 
Com relação aos grafos ilustrados nas figuras I e II acima e no que se
refere à teoria dos grafos, assinale a opção correta.
 Ambos os grafos são isomórficos. 
 Os dois grafos são completos. 
 Ambos os grafos são regulares. 
 As matrizes de adjacências dos dois grafos são distintas. 
 Os dois grafos são circuitos. 
3,5 / 3,5 ptsPergunta 2
Considere a estrutura abaixo que representa um problema de rotas em
pequena escala.
 
 
Considere, por hipótese, que solicitou-se a um Agente de Fiscalização
à Regulação de Transporte da ARTESP utilizar alguma estratégia
lógica para, partindo do ponto 1, chegar ao ponto 6 usando a menor
rota. De um mesmo ponto pode haver mais de uma rota, com
distâncias diferentes. A lógica correta utilizada pelo Agente, em função
dos pontos a serem percorridos, foi
 
27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 3/7
 
{6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-
5-3-4-6.
 
 {1} {2,3} {2,4} {5,6}{6}, caminho mais curto 1-2-5-6. 
 
{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6. 
 {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6. 
 {1} {2} {4} {6}, caminho mais curto 1-2-4-6. 
3,5 / 3,5 ptsPergunta 3
Um grafo G=(V,E) é completo se para cada par de vértices vi e vj
existe uma aresta entre vi e vj. Em um grafo completo quaisquer dois
vértices distintos são adjacentes (Kn).
 Falso 
 Verdadeiro 
3,5 / 3,5 ptsPergunta 4
Para grafos conexos, se é possível encontrar um caminho fechado que
passe por todas as arestas uma única vez, dizemos que G é um grafo
euleriano
 Verdadeiro 
 Falso 
4 / 4 ptsPergunta 5
27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 4/7
O vídeo a seguir, um agente de combate à dengue visita casas para
procurar focos de reprodução do mosquito da dengue, e orientar a
população sobre as formas de evitar que isso ocorra. Para definir o
caminho que ela deve seguir para percorrer as casas do dia seguinte,
ela se depara com um problema que envolve grafos.
 
Marque as alternativas corretas:
 
O que Lu deseja é percorrer um trajeto a partir de um ponto, passar por
todas as casas, sem precisar repetir nenhuma rua, e voltar ao ponto de
partida.
 
Podemos dizer que um grafo é um conjunto de pontos, chamados
vértices, conectados por um conjunto de linhas, chamadas arestas.
 O que Lu deseja realizar um passeio aberto.
 
O grafo a seguir não representa o mapa apresentando.
 
 
2,67 / 4 ptsPergunta 6ParcialParcial
Seja G = (V, E) um grafo qualquer. Um grafo g = (v,e) é subgrafo de
G se v V e se e E. Quais grafos a seguir são subgrafos de
G?
27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 5/7
 
 
 
 
 
 
27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 6/7
4 / 4 ptsPergunta 7
Considerando o grafo apresentado a seguir, marque as alternativas
corretas:
 
 
Uma aresta simples de G (com suas extremidades) é subgrafo de G 
 Um vértice simples de G é subgrafo de G 
 Todo grafo é subgrafo de si próprio 
 
O grafo apresentado a seguir é subgrafo.
 
4 / 4 ptsPergunta 8
Os grafos apresentados na figura a seguir são:
27/02/2022 06:50 1_Primeira Avaliação RRC: ALGORITMOS EM GRAFOS - Sistemas de Informação - UNID. EDUC. BARREIRO - PBR - NOI…
https://pucminas.instructure.com/courses/53940/quizzes/181089 7/7
 Grafos Completos 
 Grafos Isomorfos 
 Grafos Complementares 
 Grafos Desconexos 
Pontuação do teste: 28,67 de 30