Question

Estrutura de Dados - Informatica e Logica
Valendo o máximo de pontos para a resolução das duas questões !!!

Questão 1
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ó p 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:
e->chave ≤ p->chave ≤ d->chave

Questões
Considerando-se uma árvore ordenada, ou árvore binária de busca, sem balanceamento, faça:

a) A partir de uma árvore vazia, insira os seguintes nós na árvore, na ordem apresentada:
15, 18, 3, 22, 8, 1, 12, 4
Mostre a árvore resultante.

b) Qual é o caminho do nó 4?

c) Remova o nó de valor 3. Como ficará a árvore resultante? Explique sua resposta.

d) Faça outra árvore, inserindo os seguintes nós:
2, 5, 8, 10, 12

Que tipo de árvore é essa?
Mostre a árvore resultante.

--------------------------------------------

Questão 2

Explicação do problema na imagem anexada...

Veículos somente podem entrar ou sair do anel viário se estiverem na faixa externa do anel viário (faixa 1).

Veículos somente podem desenvolver alta velocidade e fazer ultrapassagens se estiverem na faixa interna do anel viário (faixa 2).

Um sistema de trânsito pode ser monitorado por um programa eletrônico que mostre a ocupação da via, a velocidade dos automóveis, os pontos de engarrafamento, entre outras informações.

O anel possui uma carga máxima de veículos que pode comportar em suas pistas.

Questões

a) Que tipo de estrutura de dados (lista, fila, pilha, árvore, ...) você usaria para resolver este problema? Que tipo de implementação esta estrutura de dados deveria ter (por vetor, por nós alocados dinamicamente, ...)? Justifique sua resposta.

b) Programe esta estrutura de dados criando funções para inserir um veículo, remover um veículo, verificar se a estrutura de dados está vazia ou cheia, procurar um veículo, alterar velocidade de um veículo, alterar faixa do veículo.

c) Teste sua estrutura de dados inserindo pelo menos 10 veículos inicialmente e fazendo um loop de repetição no qual os veículos vão sendo inseridos, removidos, alterando de faixa, aleatoriamente.

Dicas:

· Utilize as funções rand() e srand() do C++ (ou similar em outra linguagem) para gerar valores aleatórios para a velocidade e tempo em que o automóvel vai permanecer no anel;

· Faça apenas um programa para resolver as questões B e C.




Valendo o máximo de pontos para a resolução das duas questões !!!

Agradeço a ajuda de quem é mais experiente na área

Bjoss

Answer 1

questao 1

a) figura em anexo - 1
b) figura em anexo - 2
c) figura em anexo - 3 -> Quando removemos um nó de uma árvore tentamos substitui-lo pelo MENOR valor maior que o valor removido. Para isso é feita uma na árvore da direita de todas as sub-árvores a esquerda. Para cada árvore buscada (recursivamente) se não achar nada a a direita, busca-se a esquerda, e se não achar nada a esquerda, busca-se a direita. (nessa ordem). No caso, o menor valor maior que 3 é o 4. Ele é removido da folha e trazido para ficar no lugar de 3.

d) figura em anexo 4 - Como as chaves estão em ordem crescente, a árvore ficará desbalanceada e é dita degenerada