Avaliação AP - Teoria dos Grafos - UNIP

Prévia do material em texto

Data limite para aplicação 
desta prova: 
IMPORTANTE 
UNIP EAD 
Código da Prova: 
Curso: CIÊNCIA DA COMPUTAÇÃO 
Série: 5 Tipo: Bimestral - AP 
Aluno: 
I - Questões objetivas – valendo 10 pontos 
Gerada em: 
 
Instruções para a realização da prova: 
1. Leia as questões com atenção. 
2. Confira seu nome e RA e verifique se o caderno de questão e folha de respostas correspondem à sua disciplina. 
3. Faça as marcações primeiro no caderno de questões e depois repasse para a folha de respostas. 
4. Serão consideradas somente as marcações feitas na folha de respostas. 
5. Não se esqueça de assinar a folha de respostas. 
6. Utilize caneta preta para preencher a folha de respostas. 
7. Preencha todo o espaço da bolha referente à alternativa escolhida, a caneta, conforme instruções: não rasure, não 
preencha X, não ultrapasse os limites para preenchimento. 
8. Preste atenção para não deixar nenhuma questão sem assinalar. 
9. Só assinale uma alternativa por questão. 
10. Não se esqueça de responder às questões discursivas, quando houver, e de entregar a folha de respostas para o tutor 
do polo presencial, devidamente assinada. 
11. Não é permitido consulta a nenhum material durante a prova, exceto quando indicado o uso do material de apoio. 
12. Lembre-se de confirmar sua presença através da assinatura digital (login e senha). 
Boa prova! 
 
 
Questões de múltipla escolha 
Disciplina: 793930 - TEORIA DOS GRAFOS 
 
Questão 1: (CETRO 2014). Nas estruturas de dados, existem as árvores, que são grafos que não possuem 
ciclos. Assinale a alternativa correta sobre a estrutura em árvore. 
 
A) Uma árvore possui a mesma quantidade de vértices e de arestas. 
B) Um vértice com grau igual a 3 é denominado folha. 
C) Um vértice com grau igual a 1 é denominado vértice interno. 
D) Um grafo é uma árvore quando existem diversos caminhos para cada par de vértice. 
E) Um conjunto de estruturas em árvore é conhecido como floresta. → Resposta Correta 
 
Questão 2: Considere o grafo representado na figura abaixo: 
 
Assinale a alternativa que apresenta a função programa g que lhe corresponde. 
 
A) g(x) = 1-2, g(y)=1-3, g(z)=2-3 → Resposta Correta
B) g(1)=x-y, g(2)=x-z, g(3)=y-z 
C) g(x) = 3, g(y)=2, g(z)=1 
D) g(1)=z, g(2)=y, g(3)=x 
E) g=1x2z3y1 
 
Questão 3: Considere as seguintes afirmativas: 
 
I - O grafo K4, em sua representação planar divide o plano em 4 regiões. 
II - O grafo bipartido completo Km,n é Euleriano desde que m e n sejam ímpares. 
III - Em um grafo o número de vértices de grau ímpar é sempre par. 
 
São verdadeiras: 
 
A) I e II apenas. 
B) I e III apenas. → Resposta Correta 
C) II e III apenas. 
D) I, II e III. 
E) II apenas. 
 
Questão 4: Considere as seguintes asserções e a relação estabelecida entre elas: 
 
I - O problema das quatro cores é um exemplo clássico de um problema de otimização combinatória, que busca 
encontrar a melhor solução para um problema dentro de um conjunto de possibilidades. 
PORQUE 
II - Associado a qualquer mapa existe um grafo, chamado de grafo dual do mapa, onde a cada região do mapa 
corresponde a um vértice no grafo e um arco entre dois nós devem estar associados a cada duas regiões adjacentes. 
 
Pode-se afirmar que: 
 
A) A asserção I é verdadeira, e a II é falsa. 
B) A asserção II é verdadeira, e a I é falsa. 
C) As asserções I e II são verdadeiras, e a II justifica a I. 
D) As asserções I e II são verdadeiras, mas II não justifica I. → Resposta Correta 
E) As asserções I e II são falsas. 
 
Questão 5: A respeito do grafo K3,3, pode-se afirmar que ele é: 
 
A) Planar. 
B) Homeomorfo a K3,2. 
C) Isomorfo a K3,2. 
D) Não planar. → Resposta Correta 
E) Não bipartido. 
 
Questão 6: (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. 
 
A) Bellman-Ford. 
B) Floyd-Warshall. → Resposta Correta 
C) Dijkstra. 
D) Kruskal. 
E) Prim. 
 
Questão 7: Considere a árvore representada na figura abaixo e assinale a alternativa correta. 
 
 
A altura da árvore é: 
 
A) 4 
B) 3 → Resposta Correta 
C) 5 
D) 6 
E) a 
 
Questão 8: Para a árvore representada na figura abaixo, assinale a alternativa que elenca o percurso em pré- 
ordem. 
 
 
A) a, b, d, i, e, f, c, g, j, k, h. → Resposta Correta 
B) i, d, b, e, f, a, j, g, k, c, h. 
C) i, d, e, f, b, j, k, g, h, c, a. 
D) a, c, h, g, k, j, b, f, e, d. 
E) b, a, c, i, d, e, f, h, k, g. 
 
Questão 9: (ENADE 2021, questão 34) O algoritmo de Dijkstra para o problema do caminho mínimo em 
dígrafos com pesos utiliza uma fila de prioridades de vértices, na qual as prioridades são uma estimativa do 
custo final. A cada iteração, um vértice é retirado da fila, 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 “infinito”, ou seja, nenhum caminho até o vértice foi 
até o momento descoberto. 
 
 
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) A: 5 B: 6 C: 10 D: 0 E: 4 F: 1 G: -1 
B) A: 5 B: 9 C: -1 D: 0 E: 5 F: 1 G: -1 
C) A: 5 B: 9 C: -1 D: 0 E: 4 F: 1 G: 2 → Resposta Correta 
D) A: 5 B: 7 C: 8 D: 0 E: 4 F: 1 G: 2 
E) A: 5 B: 6 C: 8 D: 0 E: 3 F: 1 G: 2 
 
Questão 10: Considere as seguintes afirmativas: 
 
I - Formalmente, um fluxo em um grafo direcionado ponderado é uma atribuição de uma quantidade não negativa de 
fluxo a cada aresta, que respeita a capacidade máxima de cada aresta e a conservação do fluxo em cada nó. 
II - A capacidade máxima de uma aresta representa a quantidade máxima de fluxo que pode ser transportada através 
dela. 
III - A conservação do fluxo em cada nó exige que a quantidade de fluxo que entra em um nó deve ser igual à 
quantidade de fluxo que sai dele, exceto em nós especiais, conhecidos como fontes e sumidouros, onde o fluxo pode 
entrar ou sair livremente. 
 
São corretas as afirmativas: 
 
A) I e II apenas. 
B) II e III apenas. 
C) I e III apenas. 
D) I, II e III. → Resposta Correta 
E) III apenas.