QUESTIONÁRIO UNIDADE II TEORIA DOS GRAFOS

Prévia do material em texto

25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 1/7
 
Revisar envio do teste: QUESTIONÁRIO UNIDADE II
TEORIA DOS GRAFOS D66B_15801_R_20231 CONTEÚDO
Usuário VITORIA APARECIDA S SANTOS
Curso TEORIA DOS GRAFOS
Teste QUESTIONÁRIO UNIDADE II
Iniciado 24/03/23 11:51
Enviado 24/03/23 11:54
Status Completada
Resultado da tentativa 5 em 5 pontos  
Tempo decorrido 2 minutos
Resultados exibidos Respostas enviadas, Perguntas respondidas incorretamente
Pergunta 1
Veja a �gura 1.
  
 
Considere as asserções:
I – O grafo apresenta um caminho de Euler
CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNOUNIP
0,5 em 0,5 pontos
http://company.blackboard.com/
https://ava.ead.unip.br/webapps/blackboard/execute/courseMain?course_id=_263625_1
https://ava.ead.unip.br/webapps/blackboard/content/listContent.jsp?course_id=_263625_1&content_id=_3115168_1&mode=reset
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_25_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_27_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_47_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_49_1
https://ava.ead.unip.br/webapps/login/?action=logout
25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 2/7
Resposta Selecionada: a. 
PORQUE
II – O grafo é conexo e apresenta 2 nós ímpares.
I e II são verdadeiras e II justi�ca I.
Pergunta 2
Resposta Selecionada: c. 
Considere as seguintes a�rmações:
 
I – O número de nós ímpares em qualquer grafo é par.
II – Existe um critério simples para determinar se existem caminhos de Euler em um
grafo.
III – Existe um caminho de Euler em qualquer grafo com um número par de nós
ímpares.
 
São corretas as asserções:
Apenas I e II.
Pergunta 3
(Enade 2021, questão 34). O algoritmo de Dijkstra para o problema do caminho
mínimo em dígrafos com pesos utiliza uma �la de prioridades de vértices, na qual as
prioridades são uma estimativa do custo �nal. A cada iteração, um vértice é retirado
da �la e os arcos que começam nesse vértice são analisados. Considere o seguinte
grafo, no qual deseja-se conhecer o custo de um caminho mínimo para cada vértice,
a partir do vértice D. Considere que -1 representa um custo “in�nito”, ou seja,
nenhum caminho até o vértice foi até o momento descoberto.
 
0,5 em 0,5 pontos
0,5 em 0,5 pontos
25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 3/7
Resposta Selecionada:
c. 
 
 
Com base nas informações e no grafo apresentados, assinale a alternativa que
representa a estimativa de custo após duas iterações do algoritmo.
A: 5 B: 9 C: -1 D: 0 E: 4 F: 1 G: 2
Pergunta 4
(Fundamentada na questão 35 POSCOMP 2012). Concernente aos algoritmos em
grafos, relacione a coluna 1 com a coluna 2.
 
Coluna 1:
I – Árvore Geradora Mínima (Prim)
II – Caminho Mais Curto (Dijkstra)
III – Árvore Geradora Mínima (Kruskal)
 
Coluna 2:
(A)Toma como entrada um grafo não orientado com pesos nas arestas, ordena as
arestas por peso e escolhe as arestas de forma a não fechar ciclos para resolver o
problema.
(B) Toma como entrada um grafo não orientado com pesos nas arestas, utiliza
basicamente busca em largura escolhendo arestas de menor peso para resolver o
problema.
0,5 em 0,5 pontos
25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 4/7
Resposta Selecionada: a. 
(C)Toma como entrada um grafo não orientado com pesos nas arestas, utiliza
basicamente busca em largura escolhendo distâncias acumuladas de menor peso
para resolver o problema.
I-B; II-C; III-A.
Pergunta 5
Resposta Selecionada: b. 
(POSCOMP 2014, questão 37). Assinale a alternativa que apresenta, corretamente, o
algoritmo utilizado para determinar o caminho mínimo entre todos os pares de
vértices de um grafo.
Floyd-Warshall.
Pergunta 6
Resposta Selecionada: e. 
Em 1957, Prim apresenta o algoritmo da árvore geradora mínima em um artigo
intitulado “Shortest Connections Networks and Some Generalizations”. Para ilustrar a
computação do algoritmo faz uso de um grafo cuja matriz de adjacência modi�cada
é como se segue:
 
 
 
 
 
Considerando que o primeiro nó da árvore geradora mínima selecionado seja o nó
1, assinale a alternativa que representa a sequência em que os nós da árvore são
selecionados:
(1, 4, 3, 6, 2, 5)
0,5 em 0,5 pontos
0,5 em 0,5 pontos
25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 5/7
Pergunta 7
Resposta Selecionada: b. 
Considere o grafo apresentado na �gura 3 que se segue:
 
 
Ao se aplicar o Algoritmo de Kruskal para encontrar uma árvore geradora de peso
mínimo, a soma dos pesos vale:
15
Pergunta 8
(POSCOMP, 2009, questão 30 [FUN]). Considere o algoritmo de busca em largura em
grafos. Dado o grafo a seguir e o vértice A como ponto de partida, a ordem em que
os vértices são descobertos é dada por:
 
0,5 em 0,5 pontos
0,5 em 0,5 pontos
25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 6/7
Resposta Selecionada: a. 
 
A B C D E F
Pergunta 9
O seguinte exercício foi fundamentado em Gersting, J. L. exercício 11, capítulo 7.3, 7.
ed). Considere o grafo representado na �gura 6. Deseja-se usar o algoritmo de
Bellman-Ford para encontrar o caminho da origem nó 2 para qualquer outro nó.
Assinale a alternativa que apresenta os valores de d (distância) e s (origem) após 2
iterações do algoritmo sobre a matriz de adjacência modi�cada.
 
0,5 em 0,5 pontos
25/03/2023, 11:40 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_91940911_1&course_id=_263625_1&content_id=_3132216_1&outc… 7/7
Sábado, 25 de Março de 2023 11h40min32s GMT-03:00
Resposta
Selecionada:
c.
  1 2 3 4 5 6 7 8
d 3 0 2 3 3 4 1 2
s 2 - 2 3 8 1 2 7
Pergunta 10
Resposta Selecionada: e. 
Considere as seguintes a�rmações:
I – O algoritmo de Dijkstra, também denominado Caminho Mínimo, encontra o
caminho da distância mínima entre dois nós dados: x e y.
II – O Algoritmo de Floyd calcula caminho mínimo entre todos os pares para
encontrar as distâncias correspondentes a todos os caminhos mínimos.
III – O algoritmo de Floyd é de complexidade computacional O(n3).
 
São corretas as a�rmações:
Apenas I, II e III.
← OK
0,5 em 0,5 pontos