AVD - ALGORITMOS E COMPLEXIDADE

Prévia do material em texto

1 
 Questão 
Pontos: 1,25 / 1,25 
 
(COMPERVE - UFRN - Engenheiro - Engenharia da Computação - 2019) 
 
O código abaixo pode ser utilizado para atravessar um grafo: 
 
Entrada: um gráfico G e um vértice v de G 
 
Saída: todos os vértices alcançáveis de v marcados 
 
função DFS(G,v): 
 
 marque v 
 
 para todas as arestas adjacentes a v, faça 
 
 se vértice w não estiver marcado, então 
 
 Chame recursivamente DFS(G,w) 
 
 fim se 
 
 fim para 
 
fim função 
 
Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código 
implementa o algoritmo: 
 
 
Busca em largura ou breadth first search. 
 
Busca exaustiva ou brute force search. 
 Busca em profundidade ou depth first search. 
 
Busca pelo caminho mínimo (shortest path). 
 
Busca melhor-primeiro ou best first search. 
 
 
2 
 Questão 
Pontos: 1,25 / 1,25 
 
(FCM - IFN-MG - Ciências da Computação: Teoria da Computação - 2018) 
Considere o grafo abaixo assim como sua representação por lista de adjacência: 
 
 
 
A Árvore em Largura e a Árvore em Profundidade, respectivamente, tendo como raiz o 
vértice 1, são: 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
 Questão 
Pontos: 1,25 / 1,25 
 
(CESPE/CEBRASPE - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da 
Informação - 2016) 
 
A quantidade de grau total do grafo na figura é: 
 
 
16 
 
13 
 
15 
 14 
 
17 
 
 
4 
 Questão 
Pontos: 1,25 / 1,25 
 
(FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de 
Informação - 2017) 
Considere a estrutura abaixo que representa um problema de rotas em pequena escala: 
 
Considere, por hipótese, que se solicitou 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: 
 
 {6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual 
a 1-3-4-6. 
 {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} {4} {6}, caminho mais curto 1-2-4-6. 
 {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6. 
 {1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6. 
 
 
5 
 Questão 
Pontos: 0,00 / 1,25 
 
O grafo G é definido por: 
V = { p | p é uma pessoa da família Azevedo } 
A = { (x,y) | < x é pai/mãe de y > } 
Dados do grafo G: 
V = { Solange, Livia, Roberto, Rodrigo, Ana, Emanoel} 
A = {(Solange, Livia), (Roberto, Livia), (Ana,Rodrigo), (Rodrigo, Emanoel), 
(Roberto,Rodrigo)} 
Considerando os dados acima, avalie as afirmações abaixo: 
I - Temos uma relação simétrica definida por A. 
II - O grafo G é considerado um grafo orientado e as conexões entre os vértices são 
chamadas de arcos. 
III - O grafo possui 05 arestas, caso se decida excluir o vértice Rodrigo, o grafo 
passará a ter apenas 03 arestas 
IV - O grafo G é considerado um grafo digrafo. 
Diante dos dados acima, assinale a alternativa correta: 
 
 
Apenas as alternativas I, II e IV estão corretas. 
 Apenas as alternativas I, III e IV estão corretas. 
 
Apenas as alternativas II e III estão corretas. 
 
Apenas as alternativas I e III estão corretas. 
 Apenas as alternativas II, III e IV estão corretas. 
 
 
6 
 Questão 
Pontos: 0,00 / 1,25 
 
Sobre os tipos de grafos e suas características podemos afirmar: 
I - Um grafo G é nulo ou vazio quando o conjunto de arestas A(G) é vazio, ou seja, 
podemos ter vários vértices mas nenhuma aresta os interligando. 
II - Um grafo é conexo regular quando todos os seus vértices têm o mesmo grau, ou 
seja, possuem a mesma quantidade de arestas. 
III - Um grafo é ciclo quando todos os grafos possuem vértice grau 2, podemos dizer 
que é uma especialização do grafo conexo regular 
IV - A soma dos graus de saída (de entrada) de um grafo direcionado é sempre o 
dobro do número de arestas no grafo. 
considerando as afirmações acima, assinale a alternativa correta: 
 
 Apenas as afirmações II e III estão corretas. 
 
Apenas as afirmações I e II estão corretas. 
 
Apenas as afirmações I e III estão corretas. 
 Apenas as afirmações I, II e III estão corretas. 
 
Apenas as afirmações I, II e IV estão corretas. 
 
 
7 
 Questão 
Pontos: 1,25 / 1,25 
 
Um grafo é uma representação abstrata das relações existentes entre um conjunto de 
objetos. Ele é composto por vértices e arestas, que ligam estes vértices. Sobre o grau 
de um vértice, é correto afirmar: 
 
 
O grau de um vértice é igual à quantidade de vértices mais a quantidade de 
arestas de um grafo. 
 
O grau do vértice é igual à quantidade de vértices de um grafo. 
 
A quantidade de vértices é ímpar quando o grau de um vértice é ímpar. 
 A soma dos graus de um grafo é igual ao dobro da quantidade de arestas. 
 
O grau de um vértice é igual ao número de arestas de um grafo. 
 
 
8 
 Questão 
Pontos: 0,00 / 1,25 
 
Diante dos conceitos e formas de representação dos grafos, seguem as afirmações: 
I - Um grafo é uma estrutura formada basicamente por dois tipos de objetos: vértices 
(nós) e arestas. 
II - Um grafo direcionado é chamado de dígrafo, nesse tipo de grafo as arestas 
possuem flechas como indicativo de direção. 
III - Em um grafo os nós (vértices) são representados por círculos, e as linhas 
representam as arestas, que interligam os nós. 
IV - Um grafo é composto por no mínimo três arestas, cada aresta liga dois nós. 
Diante das afirmações acima, assinale a alternativa correta: 
 
 Apenas as alternativas I, II e III são verdadeiras. 
 Apenas a alternativa II é verdadeira. 
 
Apenas a alternativa I é verdadeira. 
 
Apenas a alternativa III é verdadeira. 
 
Apenas as alternativas I e III são verdadeiras.