1. Escrever um procedimento para inserção em árvore AVL (naturalmente isso inclui a rotação simples e a dupla), e outro para impressão dos filhos à esquerda e à direita de um dado nó.

IMPORTANTE:
Leia (e entenda) o texto nas páginas 71 a 77 do livro de Udi Manber antes de começar a sua implementação.

Observe que há diversos casos de inserção que não requerem rotação.
No caso de ser necessário fazer rotação, há quatro situações diferentes para considerar:
Se A é o nó crítico, B é o seu filho à esquerda e C seu filho à direita, então:

Veja as figuras das rotações: fig1, fig2, fig3 e fig4.

IMPORTANTE:
A função de inserção deve ser da ordem de (log n) no pior caso!!!
O seu programa só deve visitar cada nó da árvore a partir do pai no máximo duas vezes, uma para cada um dos módulos acima.
Assim, as informações devem ser ``carregadas'' enquanto estão disponíveis, obedecendo ao fluxo da informação.

2. Escreva um programa para, dados n números inteiros, ordená-los usando o algoritmo Mergesort.

O seu algoritmo deve usar dois arrays, A e B, com n elementos cada, e alternar entre eles a entrada e a saída da rotina Intercala. Naturalmente, ao nível das folhas a direção deverá ser: (entrada = A, saída = B).
Este controle deve ser feito através do valor retornado (bottom-up) pela função Intercala.
IMPORTANTE: Não use variável global para fazer isso.

3. Faça o exercício 3.5 (pág. 56) do livro de Udi Manber.
Observe que cada um dos itens deste exercício de comparação de ordens de magnitude entre funções cobre um caso diferente.

A resposta deste exercício deve ser entregue em papel impresso junto com o disquete que contém as questões (1) e (2).
Para cada um dos itens, dê uma justificativa baseada na definição formal dada em sala.
Seja objetivo (vá direto ao ponto, sem divagações) e rigoroso na sua justificativa.
 

Retorna à página Principal do Curso