Exercícios

Questão 1

Classifique as árvores A-F quanto ao número de filho e calcule:

  • O tamanho da árvore
  • A altura de cada nó
  • O grau de cada nó
  • A profundidade de cada nó

flowchart LR
subgraph s ["Árvore A"]
     A((A))
     B((B))
     C((C))
     D((D))
     E((E))
     F((F))
     G((G))
     H((H))
     I((I))
end

subgraph s1 ["Árvore B"]
     A1((A))
     B1((B))
     C1((C))
     D1((D))
     E1((E))
     F1((F))
     G1((G))
     H1((H))
     I1((I))
     J1((J))
     K1((K))
end

     A --- B
     A --- C
     A --- D
     B --- E
     B --- F
     C --- G
     D --- H
     D --- I
     
     A1 --- B1
     A1 --- C1
     A1 --- D1
     B1 --- E1
     B1 --- F1
     C1 --- G1
     C1 --- H1
     D1 --- I1
     D1 --- J1
     H1 --- K1
     s ~~~ s1
A:::WT
B:::WT
C:::WT
D:::WT
E:::WT
F:::WT
G:::WT
H:::WT
I:::WT
A1:::WT
B1:::WT
C1:::WT
D1:::WT
E1:::WT
F1:::WT
G1:::WT
H1:::WT
I1:::WT
J1:::WT
K1:::WT
classDef WT fill:#FFFFFF
 style s stroke:none,fill:none
 style s1 stroke:none,fill:none


flowchart LR
subgraph s ["Árvore C"]
     A((A))
     B((B))
     C((C))
     D((D))
     E((E))
     F((F))
     G((G))
     H((H))
end

subgraph s1 ["Árvore D"]
     A1((A))
     B1((B))
     C1((C))
     D1((D))
     E1((E))
     F1((F))
     G1((G))
     H1((H))
     I1((I))
     J1((J))
end

     A --- B
     A --- C
     B --- D
     B --- E
     D --- F
     E --- G
     E --- H
     
     A1 --- B1
     A1 --- C1
     B1 --- D1
     C1 --- E1
     C1 --- F1
     D1 --- G1
     F1 --- H1
     F1 --- I1
     I1 --- J1
     s ~~~ s1
A:::WT
B:::WT
C:::WT
D:::WT
E:::WT
F:::WT
G:::WT
H:::WT
A1:::WT
B1:::WT
C1:::WT
D1:::WT
E1:::WT
F1:::WT
G1:::WT
H1:::WT
I1:::WT
J1:::WT
classDef WT fill:#FFFFFF
 style s stroke:none,fill:none
 style s1 stroke:none,fill:none


flowchart LR
subgraph s ["Árvore E"]
     A((A))
     B((B))
     C((C))
     D((D))
     E((E))
     F((F))
     G((G))
     H((H))
     I((I))
     J((J))
     K((K))
     L((L))
     M((M))
end

subgraph s1 ["Árvore F"]
     A1((A))
     B1((B))
     C1((C))
     D1((D))
     E1((E))
     F1((F))
     G1((G))
     H1((H))
     I1((I))
     J1((J))
     K1((K))
     L1((L))
     M1((M))
     N1((N))
     O1((O))
end

     A --- B
     A --- C
     B --- D
     B --- E
     B --- F
     F --- G
     C --- H
     C --- I
     C --- J
     H --- K
     K --- L
     K --- M
     
     
     A1 --- B1
     A1 --- C1
     A1 --- D1
     B1 --- E1
     B1 --- F1
     B1 --- G1
     C1 --- H1
     C1 --- I1
     E1 --- J1
     E1 --- K1

     F1 --- L1
     F1 --- M1
     I1 --- N1
     I1 --- O1
     
     s ~~~ s1
A:::WT
B:::WT
C:::WT
D:::WT
E:::WT
F:::WT
G:::WT
H:::WT
I:::WT
J:::WT
K:::WT
L:::WT
M:::WT

A1:::WT
B1:::WT
C1:::WT
D1:::WT
E1:::WT
F1:::WT
G1:::WT
H1:::WT
I1:::WT
J1:::WT
K1:::WT
L1:::WT
M1:::WT
N1:::WT
O1:::WT
classDef WT fill:#FFFFFF
 style s stroke:none,fill:none
 style s1 stroke:none,fill:none

Questão 2

Em relação às árvores cheia, perfeita e completa:

  1. Qual delas implica em outra? Por exemplo, árvores cheias são também completas? E as completas são cheias?
  2. O que dizer das cheias e das perfeitas? E sobre as perfeitas e as completas?

Questão 3

Insira, na sequência dada, as chaves a seguir em uma BST vazia

  1. 10, 5, 15, 3, 7, 12, 18
  2. 2, 5, 8, 12, 15, 20
  3. 25, 20, 15, 10, 5
  4. 20, 10, 30, 5, 15, 25, 35, 12
  5. 10, 5, 20, 3, 7, 15, 30, 18, 25, 35

Cada sequência corresponde a uma árvore. Em seguida, classifique as árvores em cheia, completa, perfeita e degenerada.

Questão 4

Determine os percursos em pré-ordem, ordem e pós-ordem das árvores obtidas no exercício anterior.

Questão 5

Se você tivesse a tarefa de implementar um BST que permitisse chaves duplicadas, como você trataria elas? Cite pelo menos duas abordagens.

Questão 6

Dada a BST abaixo

flowchart LR
subgraph s [" "]
     A((52))
     B((34))
     C((81))
     D((20))
     E((41))
     F((64))
     G((93))
     H((10))
     I((22))
     J((39))
     K((44))
     L((61))
     M((74))
     N((92))
     I1((" "))
     I2((" "))
     O((24))
     I3((" "))
     P((52))
     Q((58))
     I4((" "))
     R((85))
     I5((" "))
     S((49))
     I6((" "))
     T((64))
     I7((" "))
end

     A --- B
     A --- C
     B --- D
     B --- E
     C --- F
     C --- G
     D --- H
     D --- I
     E --- J
     E --- K
     F --- L
     F --- M
     G --- N
     G ~~~ I1
     I ~~~ I2
     I --- O
     K ~~~ I3
     K --- P
     L --- Q
     L ~~~ I4
     N --- R
     N ~~~ I5
     P --- S
     P ~~~ I6
     R --- T
     R ~~~ I7

A:::WT
B:::WT
C:::WT
D:::WT
E:::WT
F:::WT
G:::WT
H:::WT
I:::WT
J:::WT
K:::WT
L:::WT
M:::WT
N:::WT
O:::WT
P:::WT
Q:::WT
R:::WT
S:::WT
T:::WT
classDef WT fill:#FFFFFF
style I1 stroke:none,fill:none
style I2 stroke:none,fill:none
style I3 stroke:none,fill:none
style I4 stroke:none,fill:none
style I5 stroke:none,fill:none
style I6 stroke:none,fill:none
style I7 stroke:none,fill:none
style s stroke:none,fill:none

Determine a árvore após a remoção dos nós 49, 22, 81, 34, 92 e 52

Questão 7

Qual a relação entre BST e AVL? Ou seja, o que elas tem em comum e o que as diferenciam.

Questão 8

Seja T uma árvore do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam inseridos nessa ordem em T, qual a sequência que corresponde a um percurso de T em pré-ordem?

Questão 9

Seja uma árvore do tipo AVL vazia, insira os elementos: 10, 20, 30, 40, 50, 25, 60, 70, 80 e 90. Lembre-se de realizar as rotações necessárias.

Questão 10

Seja uma árvore do tipo AVL vazia, insira os elementos: 40, 20, 10, 30, 25, 60, 45, 42, 52, 50, 55, 75, 70, 80 e 85. Lembre-se de realizar as rotações necessárias.

Questão 11

Suponha que um programa constrói uma BST de palavras, usando a ordem do dicionário para decidir em qual ramo a palavra deve ser armazenada. Desenhe quatro árvores, uma para cada uma das seguintes ordens de entrada de palavras:

  1. nice food roam dodge gate office wave
  2. wave roam office nice gate food dodge
  3. food dodge roam wave office gate nice
  4. nice roam office food wave gate dodge

Como ficaria cada uma das árvores depois que a palavra ‘food’ fosse removida?

Questão 12

Refaça o exercício anterior considerando uma AVL ao invés de uma BST.

Questão 13

Pesquise e disserte sobre a sobrecarga de recursão (ou recursion overhead)

Questão 14

Compile e execute o código a seguir. Observe a saída.

#include <stdio.h>

void swap_by_value(int a, int b){
    int temp = a; a = b; b = temp;
    printf("Dentro da função (swap_by_value):\n");
    printf("a = %d, b = %d\n", a, b);
}

int main(){
    int a = 10; int b = 20;

    printf("Antes da chamada da função (swap_by_value):\n");
    printf("a = %d, b = %d\n", a, b);

    swap_by_value(a, b);

    printf("Depois da chamada da função (swap_by_value):\n");
    printf("a = %d, b = %d\n", a, b);

    return 0;
}

Após executar o programa, responda às seguintes perguntas:

  1. A função swap_by_value realmente trocou os valores de a e b? O que aconteceu com os valores de a e b no main depois que a função terminou?

  2. Explique em suas próprias palavras por que a função não conseguiu trocar os valores de a e b na função main. Qual conceito de passagem de parâmetros em C está em jogo aqui?

Questão 15

Modifique o programa do exercício anterior para que a função realmente troque os valores das variáveis a e b na função main. Para fazer isso, você terá que usar ponteiros e o conceito de passagem por referência.

Sua nova função deve ter esta assinatura:

void troca_por_referencia(int* a, int* b);

Responda em que tipo de situação a passagem por referência é indispensável.

Questão 16

Você foi encarregado de escrever um função para apagar uma árvore liberando a memória alocada para cada nó. Qual estratégia de visitação você abordaria para que nenhum nó fosse esquecido e porquê?

De volta ao topo