Lista de Exercícios Algoritmo e Estrutura de Dados

Primeira Lista de Exercícios Curso: Bacharelado em Sistemas de Informação
Disciplina: Algoritmos e Estruturas de Dados II
Entrega: 1ª Prova	Professor(a): Virgílio Borges de Oliveira

1. Dada a expressão pré-fixa abaixo, desenhe a árvore de expressão e ache as expressões infixa e pós-fixa: (/ (+ 3 9) (* (– 7 4) (+ 6 1)))
   [pic 1]

INFIXA: 3 + 9 / 7 - 4 * 6 + 1

PÓS-FIXA: 3 9 + 7 4 - 6 1 + * /

EM ORDEM: ESQ/IMP/DIR

PRÉ-ORDEM: IMP/ESQ/DIR

PÓS-ORDEM: ESQ/DIR/IMP

1. Ao se percorrer uma árvore binária, temos:

Pré-Ordem: Z C S N X B J T D O M F L P

Em-Ordem: C X J B T N S Z D O L F P M

Desenhe uma árvore binária que satisfaça esses percursos.

[pic 2]

1. Sobre avaliação de expressões em árvore binária, faça o que se pede.

1. Dada a expressão abaixo em notação pós-fixa, desenhe sua respectiva árvore.

((((X (B C +) –) F *) A –) U –) ((Z L +) J +) /

[pic 3] 

1. Apresente a expressão em notação infixa devidamente agrupada com parênteses.

(((((B + C) - X) * F) - A) - U)) / (((Z + L) + J)

1. Apresente a expressão em notação pré-fixa.

/ (- U (- A (* (F - (+ B C)) X))) (+ J (+ Z L))

1. Com relação a Teoria dos Grafos, defina os termos abaixo:

1. Grafo: É um conjunto de vértices conectados por arestas.

1. Dígrafo: São arestas direcionadas.

1. Vértice: É um ponto em que duas ou mais curvas, linhas ou arestas se encontram.

1. Aresta: É um segmento de linha que une dois vértices.

1. Vértice adjacente: Vértice adjacente é um vértice que está ao lado, conectado por uma aresta de um vértice específico.

1. Grau do vértice: Número que determina  quantidade de vértices adjacentes ao vértice avaliado.

1. Grafo completo: É um grafo simples onde cada vértice está conectado aos demais.

1. Caminho: Sequência de dois ou mais vértices conectados por arestas.

1. Ciclo: Caminho que termina no vértice de origem.

1. Faça um comparativo entre Matriz de Adjacência e Lista de Adjacência na representação de Grafos, apresentando os prós e contras de cada estrutura.

Matriz de Adjacência (prós): Pode achar vértices que emanam e que chegam a um determinado vértice, implementação trivial.

Matriz de Adjacência (contras): Se o grafo pe esparso, o uso de memória é excessivo, Procura por vértices adjacentes pode rastrear um conjunto enorme de memória;

Lista de Adjacência (prós): Para grafos esparsos são melhores.

Lista de Adjacência (contras):

1. Todo grafo é uma árvore? Justifique.

Nem todo grafo é uma árvore, pois não possuem ciclos.

1. O que são grafos planares e como podemos identificá-los. Dê exemplos de grafos planares e não planares.

Grafos planares são grafos onde suas arestas não se cruzam e é possível identificá-los caso você consiga desenhá-lo sem cruzar suas arestas.

Grafo planar:                                         Grafo não planar:

                                                        [pic 4][pic 5]

1. O que são grafos eulerianos? Exemplifique.

Grafos Eulerianos são grafos que possuem ciclos eulerianos, ou seja um caminho que passa por todas as arestas sem repetir e termina no vértice de origem, além disso todos os vértices do grafo devem ter grau par.

1. Quais grafos são unicursais? Desenhe um grafo unicursal e destaque o caminho de Euler.

        [pic 6]

Grafos unicursais são aqueles que possuem apenas dois vértices de grau ímpar

1. Determine os valores de n para os quais o grafo completo Kn é euleriano. Para quais valores de n, o Kn é unicursal? Justifique.

1. A figura abaixo ilustra o mapa do Departamento de Matemática de uma importante Universidade. A entrada principal está na parte norte do Departamento. Determine se é possível que uma pessoa possa andar pelo Departamento passando por cada porta exatamente uma vez e terminando onde começou.

[pic 7]

1. Para o grafo abaixo, apresente:[pic 8]

1. A matriz de adjacências do grafo.

	A0	B1	C2	D3	E4	F5	G6
A0	0	5	0	7	8	0	0
B1	5	0	9	11	16	8	0
C2	0	9	0	0	5	13	3
D3	7	11	0	0	4	0	0
E4	8	16	5	4	0	15	0
F5	0	8	13	0	15	0	17
G6	0	0	3	0	0	17	0

...