QUESTIONÁRIO UNIDADE II

Prévia do material em texto

Revisar envio do teste: QUESTIONÁRIO UNIDADE IITEORIA DOS GRAFOS 7939-30_43701_R_E1_20251 CONTEÚDO
Usuário fernanda.soler @aluno.unip.br
Curso TEORIA DOS GRAFOS
Teste QUESTIONÁRIO UNIDADE II
Iniciado 30/05/25 17:16
Enviado 30/05/25 17:21
Status Completada
Resultado da tentativa 5 em 5 pontos  
Tempo decorrido 5 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 – Verifica-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.
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ífico para qualquer outro nó.
Pergunta 3
CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNO TUTORIAIS LABORATÓRIOS
fernanda.soler @aluno.unip.
UNIP EAD
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
30/05/2025, 17:22 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_113801126_1&course_id=_405567_1&content_id=_4561841_1&retu… 1/5
http://company.blackboard.com/
https://ava.ead.unip.br/webapps/blackboard/execute/courseMain?course_id=_405567_1
https://ava.ead.unip.br/webapps/blackboard/content/listContent.jsp?course_id=_405567_1&content_id=_4560928_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=_64_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
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 afirmaçõ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.
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 afirmar:
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 modificada.
Resposta: d)
Comentário: a afirmação d) é incorreta. O algoritmo faz uso apenas de 3 variáveis para indexar a matriz de adjacência
modificada, 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
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da resposta:
Considere o seguinte grafo e a matriz de adjacência modificada. 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:
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.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
30/05/2025, 17:22 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_113801126_1&course_id=_405567_1&content_id=_4561841_1&retu… 2/5
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 matriz de adjacência modificada 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.
É lexicograficamente 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. 
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 final obtém-se o nó C como aquele que apresenta o menor valor no vetor d.
 
Pode-se afirmar que:
I e II são verdadeiras e II justifica I.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
30/05/2025, 17:22 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_113801126_1&course_id=_405567_1&content_id=_4561841_1&retu… 3/5
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da resposta:
I e II são verdadeiras e II justifica I.
I e II são verdadeiras, mas II não justifica I.
Apenas I é verdadeira.
Apenas II é verdadeira.
I e II são afirmações falsas.
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 afirmações:
I, II e III.
ApenasI.
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
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 é:
0,5 em 0,5 pontos
0,5 em 0,5 pontos
30/05/2025, 17:22 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_113801126_1&course_id=_405567_1&content_id=_4561841_1&retu… 4/5
Sexta-feira, 30 de Maio de 2025 17h21min56s BRT
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
A, B, E, F.
A, B, C, D, F.
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.
Confira-se no vetor s
Logo o caminho mínimo é: A, B, E, F.
← OK
30/05/2025, 17:22 Revisar envio do teste: QUESTIONÁRIO UNIDADE II – TEORIA...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_113801126_1&course_id=_405567_1&content_id=_4561841_1&retu… 5/5