lista-4-esd-II

Prévia do material em texto

1- Insira os seguintes nós em uma á
100, 120, 1, 5. 
2- Considere o Grafo a seguir:
Julgue os itens em V ou F. 
a- O Grafo é planar
b- O Grafo é conexo
c- O nó D possui grau 3
d- O Grafo possui um ciclo.
e- O Grafo é isomórfico a um grafo K
f- O Grafo possui um ciclo de Euler
g- O Grafo possui um ciclo Hamiltoniano.
h- O Grafo possui uma ponte
i- O Grafo possui uma articulação.
j- O subgrafo formado pelos vérti
e um ciclo hamiltoniano.
k- O subgrafo F,A,B é um K
l- Um grafo K5 não é planar
 
3- Faça uma busca em largura no grafo anterior
4- Faça uma busca em 
nó a) 
5- Analise a complexidade no pior 
a. 
for(int i=0; i<100; i++)
 { 
 for(int j=0; j<100000; j++)
Prof.Miguel 
Lista de Exercícios – ESD2 
Insira os seguintes nós em uma árvore AVL 42, 30, 20, 10, 50, 70, 80, 
Considere o Grafo a seguir: 
Julgue os itens em V ou F. 
O Grafo é planar. 
O Grafo é conexo. 
O nó D possui grau 3. 
possui um ciclo. 
O Grafo é isomórfico a um grafo K5. 
O Grafo possui um ciclo de Euleriano. 
O Grafo possui um ciclo Hamiltoniano. 
O Grafo possui uma ponte. 
O Grafo possui uma articulação. 
O subgrafo formado pelos vértices D,H,G,E possui um ciclo E
um ciclo hamiltoniano. 
O subgrafo F,A,B é um K3. 
não é planar 
Faça uma busca em largura no grafo anterior(utilize como raiz o nó a)
Faça uma busca em profundidade no grafo anterior(utilize como raiz o 
xidade no pior caso dos seguintes programas
=0; i<100; i++) 
j=0; j<100000; j++) 
 
42, 30, 20, 10, 50, 70, 80, 
 
ces D,H,G,E possui um ciclo Euleriano 
(utilize como raiz o nó a). 
profundidade no grafo anterior(utilize como raiz o 
caso dos seguintes programas 
 { 
 for(int w=0; w<10; w++) 
 { 
 //implementação 
 } 
 } 
 } 
b. 
for(int i=0; i<100; i++) 
 { 
 while(j<10) 
 { 
 for(int w=0; w<10; w++) 
 { 
 //implementação 
 } 
 } 
} 
 
C. 
for(int i=0; i<100; i++) 
 { 
 while(j<10) 
 { 
 if(a==true) 
 { 
 //implementação 
 } 
 } 
} 
6. Verifique e descreva a complexidade dos algoritmos de busca. 
7. Qual é a complexidade de busca no pior caso em uma árvore AVL?