QUESTIONÁRIO UNIDADE 2 - Teoria dos Grafos

Prévia do material em texto

6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 1/7
 
Revisar envio do teste: QUESTIONÁRIO UNIDADE II
TEORIA DOS GRAFOS 7939-30_43701_R_E1_20231 CONTEÚDO
Usuário
Curso TEORIA DOS GRAFOS
Teste QUESTIONÁRIO UNIDADE II
Iniciado 02/06/23 19:09
Enviado 02/06/23 19:20
Status Completada
Resultado da
tentativa
5 em 5 pontos  
Tempo decorrido 11 minutos
Resultados exibidos Todas as respostas, Respostas enviadas, Respostas corretas, Comentários, Perguntas
respondidas incorretamente
Pergunta 1
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere as seguintes asserções sobre o algoritmo de Kruskal:
 
I – Todas as arestas são ordenadas por peso.
II – Veri�ca-se cada aresta da sequência ordenada para ver se pode ser considerada parte
da árvore em construção.
III – Uma aresta é adicionada à arvore se não aparece nenhum ciclo depois de sua
inclusão.
 
São asserções verdadeiras:
I, II e III.
I, II e III.
Apenas I e II.
Apenas I e III.
Apenas II e III.
Apenas III.
Resposta: a)
Comentário: as três asserções, na ordem I, II e III, apresentam o
algoritmo popular idealizado por Joseph Kruskal.
CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNO TUTORIAISUNIP EAD
0,5 em 0,5 pontos
http://company.blackboard.com/
https://ava.ead.unip.br/webapps/blackboard/execute/courseMain?course_id=_290757_1
https://ava.ead.unip.br/webapps/blackboard/content/listContent.jsp?course_id=_290757_1&content_id=_3419860_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=_29_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_10_1
https://ava.ead.unip.br/webapps/login/?action=logout
6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 2/7
Pergunta 2
Resposta Selecionada: e. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário
da resposta:
O algoritmo que calcula o caminho mínimo de um nó particular a qualquer outro nó:
Bellman-Ford.
Kruskal.
Dijkstra.
Warshall.
Floyd.
Bellman-Ford.
Resposta: e)
Comentário: o algoritmo de Bellman-Ford executa uma série de cálculos,
procurando encontrar caminhos mínimos, sucessivamente, de
comprimento 1, depois de comprimento 2, e assim por diante, até o
comprimento máximo n-1. Desta forma, o algoritmo de Bellman-Ford
calcula o caminho mínimo de um nó especí�co para qualquer outro nó.
Pergunta 3
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere as seguintes asserções:
 
I – As arestas de um grafo podem estar associadas a certos pesos que representam, por
exemplo, distâncias entre cidades.
II – As arestas de um grafo podem estar associadas a certos pesos que representam, por
exemplo, tempos que separam a execução de certas tarefas.
III – As arestas de um grafo podem estar associadas a certos pesos que representam, por
exemplo, custos de se transmitir informação entre localidades.
 
São corretas as a�rmações:
I, II e III.
Apenas I.
Apenas II.
Apenas III.
I, II e III.
Apenas I e II.
Resposta: d)
Comentário: quando está se determinando o caminho mais curto de
um vértice v para o vértice u, a informação sobre as distâncias entre
vértices intermediários w tem que ser registrada.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 3/7
Pergunta 4
Resposta
Selecionada:
d. 
Respostas: a.
b. 
c. 
d. 
e. 
Comentário da
resposta:
A respeito do algoritmo concebido por Stephen Warshal e implementado por Robert Floyd,
é incorreto a�rmar:
Seu desempenho em consumo de memória é combinatório.
Encontra todos os menores caminhos a partir de um vértice
qualquer para qualquer outro.
O grafo pode incluir pesos negativos.
Trata-se de um algoritmo O(n3).
Seu desempenho em consumo de memória é combinatório.
Faz uso de matriz de adjacência modi�cada.
Resposta: d)
Comentário: a a�rmação d) é incorreta. O algoritmo faz uso apenas de 3
variáveis para indexar a matriz de adjacência modi�cada, de dimensão n
x n, em três laços aninhados. Assim sendo, não apresenta desempenho
combinatório em consumo de memória.
Pergunta 5
Considere o seguinte grafo e a matriz de adjacência modi�cada. Deseja-se o caminho
mínimo entre os nós A e F, empregando-se o algoritmo de Dijkstra.
Em uma etapa inicial, o algoritmo inicializa o conjunto de nós IN com:
0,5 em 0,5 pontos
0,5 em 0,5 pontos
6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 4/7
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
O nó A.
O nó A.
O nó B.
O nó F.
O nó C.
Conjunto vazio.
Resposta: a)
Comentário: como o caminho mínimo estabelecido é entre o nó A e
F, inicializa-se o conjunto de nós In com o nó A.
Pergunta 6
Resposta Selecionada:
a. 
Respostas:
a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Na etapa inicial do algoritmo de Dijkstra, mencionado na questão 5, os vetores distância d
e nó anterior s, podem ser representados pela tabela:
Resposta: a)
Comentário: na etapa inicial, os vetores d e s, são obtidos a partir da
0,5 em 0,5 pontos
6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 5/7
matriz de adjacência modi�cada do grafo.
Pergunta 7
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Na segunda iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F, o
nó selecionado para o conjunto IN é B, porque:
É o de menor distância.
É adjacente a A.
É lexicogra�camente sucessor de A.
É selecionado empiricamente.
É o de menor distância.
O nó B não é o selecionado.
Resposta: d)
Comentário: o algoritmo seleciona para o conjunto de nós IN
aquele de menor distância. 
Pergunta 8
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Na terceira iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F:
 
I – O nó C é selecionado.
 
PORQUE
 
II – Comparam-se as distâncias entre o nó A e os demais C, D, E e F, passando-se por B, ou
não. Os valores do vetor d e o vetor s podem ser reescritos segundo o menor valor
resultante da comparação. Ao �nal obtém-se o nó C como aquele que apresenta o menor
valor no vetor d.
 
Pode-se a�rmar que:
I e II são verdadeiras e II justi�ca I.
I e II são verdadeiras e II justi�ca I.
I e II são verdadeiras, mas II não justi�ca I.
Apenas I é verdadeira.
Apenas II é verdadeira.
I e II são a�rmações falsas.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 6/7
Comentário da
resposta:
Resposta: a)
Comentário: Na terceira iteração, são realizados os seguintes
cálculos:
d[C] = min(4, 2 +A[B, C]) = min(4,3) = 3
d[D] = min(∞, 2 +A[B, D]) = min(∞,2+4) = 6
d[E] = min(∞, 2 +A[B, E]) = min(∞,2+2) = 4
d[F] = min(∞, 2 +A[B, F]) = min(∞,2+ ∞) = ∞
Os vetores d e C são sobrescritos, conforme se segue:
Seguidamente o nó C é selecionado para o conjunto IN.
Pergunta 9
Resposta Selecionada: e. 
Respostas: a. 
b. 
c. 
d. 
e.Comentário da
resposta:
Na quarta iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F:
 
I – São realizados os seguintes cálculos. d[D]= min(6, 3 +A[C, D]) =min(6,3+4)=6
d[E]= min(4, 3 +A[C, E]) =min(4,3+3)=4. d[F]= min(∞, 3 +A[C, F]) =min(∞,3+ ∞)=
II –  Os vetores d e s são reescritos.
III – O nó E é selecionado.
São corretas as a�rmações:
I, II e III.
Apenas I.
Apenas I e II.
Apenas I e III.
Apenas II e III.
I, II e III.
Resposta: e)
Comentário: a partir dos cálculos efetuados, os vetores d e s resultam
iguais ao da iteração anterior e por isto o nó E é selecionado.
Pergunta 10
Resposta Selecionada: d. 
Respostas: a. 
Na quinta iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F, o nó
F é selecionado. O caminho mínimo obtido é:
A, B, E, F.
A, B, C, D, F.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
6/2/23, 7:21 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95149814_1&course_id=_290757_1&content_id=_… 7/7
Sexta-feira, 2 de Junho de 2023 19h21min05s BRT
b. 
c. 
d. 
e. 
Comentário da
resposta:
A, B, C, E, F.
B, A, C, F.
A, B, E, F.
F, E, B, C, A.
Resposta: d)
Comentário: na quinta iteração os seguintes cálculos foram efetuados:
d[D] = min(6, 4 +A[E, D]) = min(6,4+3)=6, d[F] = min(∞, 4 +A[E, F]) =
min(∞,4+ 2)= 6
Os vetores d e s, são reescritos.
O nó F é selecionado. Tem-se que o antecessor de F é E, que por sua
vez é antecedido por B, e este, antecedido por A. Con�ra-se no vetor s
Logo o caminho mínimo é: A, B, E, F.
← OK