Estruturas de Dados - Lista de exercícios 5

(Não precisa entregar mas ... vale a pena fazer !!)

1. Considere uma árvore binária implementada por elementos com os campos info, llink, e rlink. Dada um apontador a uma árvore binária, escreva um algoritmo que mude todos os apontadores nil da árvore para apontar para a raiz da árvore.
2. Escreva um algoritmo breadthfirst(T) que percorre uma árvore binária T em ordem ``breadth-first'' ou ``por alargamento'', visitando primeiro a raiz (nível 1), em seguida os seus filhos (nível 2) da esquerda para a direita, e assim sucessivamente. Caso precise de alguma estrutura de dado auxiliar, especifique qual, e suponha existentes rotinas para a sua manipulação.
3. Escreva um algoritmo que, dada uma árvore binária de busca, remove o nó contendo o menor valor.
4. Uma árvore binária de busca pode ser usada para implementar uma fila de prioridade. Escreva um algoritmo eficiente para realizar a operação de remoção de um elemento da fila de prioridade assim implementada. Qual a complexidade desse algoritmo no pior caso?
5. Escreva uma função recursiva que retorna a altura de uma árvore binária.
6. Escreva um algoritmo que verifica se uma dada árvore binária é do tipo AVL. Suponha já existente uma função altura(P) que retorna a altura de uma árvore binária apontada por P.
7. Desenhe uma árvore AVL de 20 nós de maior altura. Desenhe uma árvore AVL de altura 7 com o menor número de nós.
8. Desenhe uma árvore de busca do tipo AVL com um total de 36 nós possuindo a maior altura possível. Mostre seus trabalhos.
9. Obtenha a árvore de busca binária ótima, com as seguintes chaves e frequências de acesso, por meio da técnica de programação dinâmica. Ilustre todos os passos (figuras) como foi feito no exemplo dado em aula.
   
   
10. Use a técnica de programação dinâmica para mostrar a melhor maneira de multiplicar 5 matrizes , respectivamente, . Mostre também o número de operações aritméticas usadas.
11. Considere uma B-árvore de ordem 1 (isté, cada página ou nó da árvore contém 1 ou 2 chaves). Considere a inserção das chaves de valores 1, 2, , etc. Após a inserção de quais chaves ocorrem quebra de páginas? Indique também as chaves (maiores que a chave 1) que provocam o aumento da altura da B-árvore.

 
• About this document ...