malbarbo.pro.br

7256 Algoritmos e estruturas de dados

Edição 2013/2 - Engenharia de Produção

Exercícios / Árvores

  1. Dado a árvore a seguir, determine

                  E
            / | \
           /  |  \
          /   |   \
         A    D    B
        /         / \
       C         F   H
                  \
                   G
    1. A raiz
    2. As folhas
    3. Os nós internos
    4. O grau de cada nó
    5. A altura de cada nó
    6. A altura da árvore
    7. Os filhos de E
    8. Os descendente de B
    9. Os ancestrais de G
    10. O pai de H

  2. (PF-BINT 2) Árvores binárias podem ser usadas, de maneira muito natural, para representar expressões aritméticas (como $((a+b) \times (c-d)/(e-f)+g$, por exemplo). Discuta os detalhes.

  3. (PF-BINT 11). Desenhe uma árvore binária que tenha os valores $1, \dots , 17$ e a menor altura possível. Repita com a maior altura possível.

  4. (CLRS 12.1-1) Para o conjunto de valores ${1, 4, 5, 10, 16, 17, 21}$ desenhe árvores binárias de busca de altura 2, 3, 4, 5 e 6.

  5. (PF-BINST 2) Suponha que para cada nó x de uma árvore binária, temos que x.esq.valor <= x.valor <= x.dir.valor. Esta árvore é de busca?

  6. (CLRS 12.2-1) Suponha que uma árvore binária de busca tenha números entre 1 e 1000 e queremos encontrar o número 363. Qual das seguintes sequências não pode ser a sequência de nós examinados? Explique.

    1. 2, 252, 401, 398, 330, 344, 397, 363.
    2. 924, 220, 911, 244, 898, 258, 362, 363.
    3. 925, 202, 911, 240, 912, 245, 363.
    4. 2, 399, 387, 219, 266, 382, 381, 278, 363.
    5. 935, 278, 347, 621, 299, 392, 358, 363.

  7. (CLRS 12.2-4) O professor Bunyan acha que descobriu um propriedade notável das árvores binárias de busca. Suponha que um valor $k$ em uma árvore binária esteja em uma folha. Considere 3 conjuntos: $A$, os valores a esquerda do caminho de busca; $B$, os valores no caminho de busca; e $C$, os valores a direita do caminho de busca. O professor Bunyan afirma que três valores quaisquer $a \in A$, $b \in B$ e $c \in C$ satisfazem $a \le b \le c$. Dê o menor contra exemplo possível para afirmação.

  8. (PF-BINT 4) Defina um método que calcule o número de folhas de uma árvore binária de busca.

  9. Defina um método que calcule a soma dos valores de uma árvore binária de busca.

  10. (PF-BINST 6) Defina uma função que transforme um arranjo crescente em uma árvore de busca balanceada.

  11. (PF-BINST 90) Suponha que as chaves 50, 30, 70, 20, 40, 60, 80, 15, 25, 35, 45, 36 são inseridas, nesta ordem, numa árvore de busca inicialmente vazia. Desenhe a árvore que resulta. Em seguida remova os nós que contém 30, 50, 60. Desenhe a árvore a cada remoção.

Referências