EX15

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL 
INSTITUTO DE INFORMÁTICA 
Bacharelado em Ciência da Computação e 
Engenharia da Computação 
INF 01203 – Estruturas de Dados 
Profa. Renata Galante (galante@inf.ufrgs.br ) 
Árvore Geradora 
Nomes:		 ___________________________________________________	
	 ___________________________________________________	
	 ___________________________________________________	
	 ___________________________________________________	
01	–	Qual	é	o	peso	das	árvores	geradoras	máxima	e	mínima,	considerando	a	figura	abaixo?	
O	peso	é	a	soma	dos	valores	de	todas	as	arestas	da	árvore	resultante.	
	
a)	Árvore	Geradora	Mínima		_______________________	
	
b)	Árvore	Geradora	Máxima		_______________________	
	
c)	Desenhe	a	árvore	geradora	mínima	
	
	
	
	
	
	
	
d)	Desenhe	a	árvore	geradora	máxima	
	
	
	
	
	
	
02.	Dado	um	grafo	G	conexo	e	valorado,	se	todos	os	valores	de	G	forem	distintos,	então	
existirá	exatamente	uma	árvore	geradora	mínima	para	o	grafo	G.	Apresente	argumentos	a	
favor	ou	contra	a	afirmação	apresentada.		
	
	
	
	
	
	
03.	Você	recebeu	um	mapa	de	cidades	conectadas	entre	si	por	 linhas	de	cabo	de	forma	
que	 não	 há	 ciclo	 entre	 duas	 cidades.	 Precisamos	 encontrar	 o	 comprimento	máximo	 de	
cabo	 entre	 pares	 de	 cidades	 para	 um	 determinado	 mapa	 da	 cidade.	 Com	 base	 nesse	
problema	e	na	entrada	de	dados	abaixo,	responda:	
Entrada de Dados: 
1 2 3 // o comprimeiro de cabos de 1 até 2 (ou de 2 até 1) é 3 
2 3 4 
2 6 2 
6 4 6 
6 5 5 
1 6 7 
a) Qual	é	o	algoritmo	que	resolve	este	problema:	_____________________________	
b) Qual	é	o	comprimento	total	de	cabos	necessário	para	resolver	o	problema:		______	
c) Qual	é	o	valor	do	comprimento	de	cabo	que	não	fará	parte	da	estrutura	de	dados	
resultante	após	a	execução	do	algoritmo.	Assinale	a	alternativa	correta	com	base	
no	problema	descrito	acima.		
(					)	aresta	com	o	menor	valor	de	comprimento	
(					)	aresta	com	o	maior	valor	de	comprimento	
(					)	aresta	com	o	valor	médio	de	comprimento	
(					)	aresta	que	contem	o	somatório	dos	n	menores	comprimentos	
(					)	aresta	que	contem	o	somatório	dos	n	maiores	comprimentos	
d) Desenhe	abaixo	a	saída	do	algoritmo	após	a	solução	do	problema	apresentado.		
	
 
 
 
 
 
 
 
04.	Dado	um	grafo	não	orientado,	não	valorado	e	conexo.	O	grafo	tem	características	de	
árvore	 (por	 exemplo,	 não	 contem	 ciclos).	 É	 possível	 escolher	 qualquer	 nó	 como	 raiz	 e	
manter	 o	 grafo	 conectado	 com	 as	mesmas	 ligações	 (arestas)?	 Justifique	 sua	 resposta	 e	
apresente	um	exemplo.			
	
	
 
 
 
 
	
05.	 Tendo	em	vista	as	Olimpíadas	de	2016,	o	governador	do	estado	decidiu	 investir	em	
uma	malha	ferroviária	ligando	a	cidade	do	Rio	de	Janeiro	aos	outros	9	maiores	municípios	
do	 interior	do	RJ.	 Para	 cada	par	de	municípios,	poderá	 ser	possível	ou	não	uma	 ligação	
direta	 entre	 eles.	 Existe	 um	 custo	 monetário	 fixo	 por	 quilometro	 de	 trilho	 construído.	
Devido	a	restrições	orçamentárias,	deseja-se	conectar	todos	os	10	municípios	(mesmo	que	
de	forma	indireta)	de	forma	a	que	o	custo	total	de	construção	dessa	malha	ferroviária	seja	
mínimo.	 Qual	 é	 a	 alternativa	 que	 contém	 o	 algoritmo	 correto	 para	 resolver	 este	
problema?	
a)		caminhamento	em	largura		
b)		caminhamento	em	profundidade	
c)			árvore	geradora	mínima		
d)		árvore	geradora	máxima	
e)		árvore	geradora	sem	pesos	
06.	A	NASA	deseja	interligar	n	estações	espalhadas	pelos	Estados	Unidos	usando	canais	de	
transmissão	de	comunicação.	Cada	par	de	estações	tem	uma	capacidade	de	transmissão	
de	mensagens	diferente,	que	são	conhecidas	de	antemão.	A	NASA	deseja	escolher	(n	–	1)	
canais	(o	mínimo	possível)	de	tal	forma	que	todas	as	estações	estejam	ligadas	pelos	canais	
de	transmissão	e	a	capacidade	de	transmissão	total	seja	máxima.		Qual	é	a	alternativa	que	
contém	o	algoritmo	correto	para	resolver	este	problema?	
a)		caminhamento	em	largura		
b)		caminhamento	em	profundidade	
c)			árvore	geradora	mínima		
d)		árvore	geradora	máxima	
e)		árvore	geradora	sem	pesos	
07.	 Considere	 os	 trecho	 de	 código	 a	 seguir.	 Assinale	 a	 alternativa	 que	 explica	
corretamente	o	funcionamento	e	as	características	das	duas	funções.		
	
#define max 7 
void Misterio 
(int g[max+1][max+1],int v,int vis[max+1],int pai[max+1]) 
{ 
 int w; 
 vis[v]= true; 
 for(w = 1; w<=max; w++) 
 if ((g[v][w]== 1) && (vis[w]==false)) 
 { 
 pai[w]=v; 
 Misterio(g, w, vis, pai); }} 
a)	O	que	faz	a	função	Misterio?	
	
	
	
	
b)	Qual	é	a	estrutura	de	dados	utilizada?	Assinale	a	alternativa	correta.	
	
(a)		matriz	de	adjacência		
(b)		matriz	de	incidência	
(c)			lista	de	adjacência	
(e)		lista	de	incidência	
	
c)	Qual	é	o	algoritmo	de	caminhamento	utilizado	pela	função	para	percorrer	a	estrutura	
de	dados	e	resolver	o	problema?	Assinale	a	alternativa	correta.	
	
(a)		profundidade		
(b)	abrangência	
	
d)	A	função	funciona	para	quais	tipos	de	grafos?		Assinale	a(s)	alternativa(s)	correta(s).	
Uma	ou	mais	alternativas	podem	estar	corretas.		
	
(a)	grafo	valorado		
(b)	grafo	não-valorado	
(c)	grafo	orientado		
(d)	grafo	não-orientado	
(e)	grafo	com	ciclos	
(f)	grafo	sem	ciclos	
(g)	grafo	conexo	
(h)	grafo	desconexo	
(i)	grafo	com	laço	
(j)	grafo	sem	laço	
	
	
08.	Considere	o	seguinte	enunciado:		
 
• Existem	8	pequenas	ilhas	em	um	arquipélago	e	o	governo	deseja	construir	7	pontes	
conectando-as	de	forma	que	cada	ilha	possa	ser	alcançada	de	qualquer	outra	ilha	
através	de	uma	ou	mais	pontes;	
• O	custo	de	construção	de	uma	ponte	é	proporcional	ao	seu	comprimento;	
• As	distâncias	entre	os	pares	de	ilhas	são	dados	na	tabela	abaixo	
 
Ache	quais	pontes	devem	ser	construídas	para	que	o	custo	da	construção	seja	mínimo.		
	
_________,	_________,	_________,	_________,	_________,	_________,	________	
	
	
Qual	é	o	somático	do	pesos	de	todas	as	pontes	que	serão	construídas?	____________	
 
 1 2 3 4 5 6 7 8 
1 - 240 210 340 280 200 345 120 
2 - - 265 175 215 180 185 155 
3 - - - 260 115 350 435 195 
4 - - - - 160 330 295 230 
5 - - - - - 360 400 170 
6 - - - - - - 175 205 
7 - - - - - - - 305 
8 - - - - - - - -