Avaliação Discursiva Online (A1C) FAEL

 

Questão A

O grafo é uma estrutura de dados na qual os nós são dispostos em uma malha em que cada nó pode apontar para zero, um ou mais nós do grafo, bem como receber apontamento de qualquer outro nó, ou nenhum apontamento. Desta forma, este tipo de estrutura permite a implementação dos complexos sistemas de mapas e rotas, tão utilizados atualmente em sistemas de orientação por satélite, os GPS. Seja o grafo a seguir:

 

 

O que deve ser apresentado na questão:

a) Listar os vértices do grafo

b) Listar as arestas do grafo

c) Mostrar as listas de adjacências de cada vértice do grafo

 

Questão B

Considere uma árvore binária cujos nós têm um campo chave de um tipo linearmente ordenado, um tipo (como int, char, string, etc.) que admite comparação.

Uma árvore binária deste tipo é de busca se cada nó tem a seguinte propriedade:  a chave de p é (1) maior ou igual à chave de qualquer nó na subárvore esquerda de p  e (2) menor ou igual à chave de qualquer nó na subárvore direita de p.  

Em outras palavras, se p é um nó qualquer então:

esq->chave   ≤   p->chave   ≤   dir->chave

 

O que deve ser realizado na questão:

Considerando-se uma árvore ordenada, ou árvore binária de busca, sem balanceamento, faça um programa para manipular uma árvore que armazene dados de um cliente.

O cliente pode ser uma estrutura com nome, data de nascimento e salário.

Para a árvore, faça as seguintes rotinas:

a) inserir ordenando por nome

b) inserir ordenando por data de nascimento

c) remover um nó folha qualquer

d) verificar se a árvore está vazia

e) mostrar a árvore (basta que os dados dos clientes sejam mostrados “em  ordem”, um cliente por linha)

No main, insira de 10 a 15 clientes, ordenando por nome. Mostre sua árvore.

Depois remova os elementos da primeira árvore, inserindo numa segunda, agora ordenando por data de nascimento. Mostre a segunda árvore no final.

Dicas:

·                    Datas podem ser representadas por uma struct ou por uma string.

·                    Assista as videoaulas 6.2, 7.1 e 7.2.

·                    Faça a tarefa por partes: primeiro insira por nome, depois mostre a árvore, depois remova, depois insira por data.

·                    Se não conseguir fazer o exercício todo, não se esqueça de que notas parciais também serão consideradas.