lista-3-esd-II

Prévia do material em texto

Prof.Miguel 
Lista de Exercícios –ESD2 
1- Construa uma árvore N-Árias e descreva um exemplo prático de 
utilização desse tipo árvore. 
2- Julgue os itens em V ou F 
a. A Busca em largura gera uma árvore de busca. 
b. A Busca em profundidade não gera uma árvore. 
c. Um critério guloso para uma busca gulosa seria buscar o nó de 
maior importância. 
d. Uma heurística bem-formada vai reduzir o número de nós a serem 
testado em uma busca. 
e. A Busca em largura faz expansão “nível a nível” no grafo. 
f. Um grafo é formado por vértices e arestas. 
g. Um grafo possui ciclo de Euler somente se todos os vértices 
possuem grau par. 
h. Uma articulação é vértice que se retirado desconecta o grafo. 
i. Toda aresta de uma árvore é uma ponte. 
j. Em um ciclo nenhuma aresta é ponte. 
k. Uma árvore é um grafo acíclico, conexo e com V = E+1. 
l. Um grafo completo possui todos os vértices e todas as arestas. 
m. Nos computadores um grafo pode ser representado por uma 
matriz de adjacências. 
n. Toda árvore com número de vértices > 0 possui pelo menos uma 
raiz. 
3- Julgue os itens em V ou F 
a. Um grafo planar não possui cruzamento de arestas. 
b. Um grafo completo com 5 arestas K5 é um grafo planar. 
c. Um nó folha não possui filhos. 
d. Em uma árvore binária cada nó possui no máximo 2 filhos. 
e. A altura de uma árvore é igual ao maior nível da árvore. 
f. Árvores AVL são árvores balanceadas. 
g. Em uma árvore com 10 níveis pode existir um vértice no segundo 
nível, sem nenhum filho. 
h. Grafos podem ser utilizados para a representação de diversas 
estrutura de dados. 
i. Grafos podem ser usados na web semântica. 
j. Grafos podem ser usados nas redes sociais. 
k. Em dígrafos um sumidouro é um grafo que somente possui aresta 
de entrada. 
l. Em dígrafos uma fonte é um grafo que somente possui arestas de 
saída. 
m. Para um grafo ser bipartido é necessário que ele não tenha ciclo 
impar. 
n. Todo grafo planar pode ser desenhado em uma esfera. 
4- Descreva a diferença entre busca em largura e busca em profundidade? 
5- Descreva qual é a vantagem de uma busca binária em relação a uma 
busca sequencial? 
6- Insira em uma árvore binária 10,5,13,3,7,2,4,6,8,12,14 
a. Quantos níveis têm essa árvore? 
b. Quais são os nós do nível 2? 
c. Essa árvore é completa? 
d. Essa árvore é cheia? 
e. Quais são os nós folhas dessa árvore? 
f. Quais são os nós de grau 3 nessa árvore? 
g. Qual é a altura dessa árvore? 
h. Qual nó é irmão do nó 10? 
7- Faça uma busca em pós-ordem, em ordem simétrica e em pré-ordem na 
árvore anterior. 
8- Remova os seguintes nós da árvore anterior 3, 10, 13 
9- Descreva exemplos de utilização de grafos em estrutura de dados. 
10- Descreva os conceitos (exemplificando) 
a. nó pai 
b. nó filho 
c. nó irmão 
d. nó primo 
e. ancestral 
f. descendente 
g. grau 
 
 
 
Boa sorte!