Série de Exercícios
Árvores
Exercício 1
• Suponhamos que temos uma árvore binária com campos esquerda,
direita, e de dados. Os campos de dados contêm números inteiros.
A raiz da árvore é r. Sendo o procedimento mistério mostrado
abaixo, qual seria o efeito da chamada mistério (r; 0)?
void mystery(x; i)
{ if (x ≠ null) {
x.value = x.data + i;
mystery(x.left, x.value);
mystery(x.right, x.value);
}
}
• Solução
Para todos os nós x, da árvore, o valor do campo de dados se torna
igual à soma dos campos de dados dos ancestrais de x
3
Exercício 1
• Suponhamos que temos uma árvore binária com campos esquerda,
direita, e de dados. Os campos de dados contêm números inteiros.
A raiz da árvore é r. Sendo o procedimento mistério mostrado
abaixo, qual seria o efeito da chamada mistério (r; 0)?
void mystery(x; i)
{ if (x ≠ null) {
x.value = x.data + i;
mystery(x.left, x.value);
mystery(x.right, x.value);
}
}
• Solução
Para todos os nós x, da árvore, o valor do campo de dados se torna
igual à soma dos campos de dados dos ancestrais de x
4
Exercício 2
• O percurso infixo em uma árvore de busca binária
gera uma lista classificada. Suponha que esta lista é
armazenada em um array A de tamanho n. Uma
árvore de busca binária globalmente balanceada
possui como raiz A[mid], tem como sub árvore da
esquerda a árvore de busca binária globalmente
balanceada dos elementos no sub array A[0..mid-1],
e como sub árvore da direita a árvore de busca
binária globalmente balanceada dos elementos no
sub array A[mid+1..n-1]. Escrever um método para
construir uma árvore de busca binária globalmente
balanceada a partir de um array classificado A.
5
Exercício 2
Solução
template <class Object>
BinarySearchTree<Object>* BinarySearchTree<Object>::makeTree (
ArrayClass<Object>& a, int start, int end)
{ // BinarySearchTree<Object>::makeTree
BinarySearchTree<Object>* bst;
int mid = (start + end) / 2;
if (end < start) return new BinarySearchTree<Object>;
bst = new BinarySearchTree<Object>(a[mid]);
bst->_left = makeTree(a, start, mid - 1);
bst->_right = makeTree(a, mid + 1, end);
return bst;
} // BinarySearchTree<Object>::makeTree
6
Exercício 3
• Conhecendo-se os percursos pré-fixo e infixo de uma árvore binária
só há uma árvore binária que satisfaça estes percursos. Para os
percursos pré-fixo e infixo que se seguem construa a árvore binária
correspondente.
• Percurso pré-fixo: a, e, f, h, g, b, c, d
• Percurso infixo: h, f, e, g, a, c, b, d
• Solução
7
Exercício 3
• Conhecendo-se os percursos pré-fixo e infixo de uma árvore binária
só há uma árvore binária que satisfaça estes percursos. Para os
percursos pré-fixo e infixo que se seguem construa a árvore binária
correspondente.
• Percurso pré-fixo: a, e, f, h, g, b, c, d
• Percurso infixo: h, f, e, g, a, c, b, d
• Solução
8
Heaps e filas de prioridades
Exercício 4
• Considere um heap sobre um array A de 13
elementos numerados de 1 até 15
• O conteúdo corrente do array nas posições A[1] a
A[13] é
17; 27; 22; 29; 31; 42; 86; 43; 56; 71; 34; 67; 53
• Este heap suporta um fila de prioridades de mínimo
• Após a aplicação do método dequeueMin() qual será
a posição no array do elemento 53?
• Solução
A[6]
10
Exercício 4
• Considere um heap sobre um array A de 13
elementos numerados de 1 até 15
• O conteúdo corrente do array nas posições A[1] a
A[13] é
17; 27; 22; 29; 31; 42; 86; 43; 56; 71; 34; 67; 53
• Este heap suporta um fila de prioridades de mínimo
• Após a aplicação do método dequeueMin() qual será
a posição no array do elemento 53?
• Solução
A[6]
11
Exercício 5
• Considere um heap sobre um array A de 13
elementos numerados de 1 até 15
• O conteúdo corrente do array nas posições A[1] a
A[13] é
17; 27; 22; 29; 31; 42; 86; 43; 56; 71; 34; 67; 53
• Este heap suporta um fila de prioridades de mínimo
• Após a aplicação do método enqueue(Int(81)) qual
será a posição no array do novo elemento?
• Solução
A[7]
12
Exercício 5
• Considere um heap sobre um array A de 13
elementos numerados de 1 até 15
• O conteúdo corrente do array nas posições A[1] a
A[13] é
17; 27; 22; 29; 31; 42; 86; 43; 56; 71; 34; 67; 53
• Este heap suporta um fila de prioridades de mínimo
• Após a aplicação do método enqueue(Int(81)) qual
será a posição no array do novo elemento?
• Solução
A[7]
13
Exercício 6
• A figura mostra uma fila de prioridades
armazenada em um heap
• Na árvore binária do heap quantos nós existem
na sub-árvore da direita da raiz?
• Solução
7
14
Exercício 6
• A figura mostra uma fila de prioridades
armazenada em um heap
• Na árvore binária do heap quantos nós existem
na sub-árvore da direita da raiz?
• Solução
7
15
Exercício 7
• Um heap representando uma fila de prioridades
está armazenado em um array A
• A raiz do heap está armazenada em A[1]
• Aonde está armazenada a filha esquerda da folha
direita da raiz?
• Solução
A[6]
16
Exercício 7
• Um heap representando uma fila de prioridades
está armazenado em um array A
• A raiz do heap está armazenada em A[1]
• Aonde está armazenada a filha esquerda da folha
direita da raiz?
• Solução
A[6]
17
Exercício 8
• Considere a fila de prioridade armazenada em
um heap (min), como indicado. Caso seja
inserido na fila 31 em qual posição do heap vai
ficar?
18
Exercício 8
• Solução
• A inclusão é feita no nó 11, filho mais novo do nó 5
(E contendo 63)
• A chave de 11 é menor do que a de seu pai (nó 5) e
o conteúdo troca de lugar, indo 31 para o nó 5
• O pai do nó 5 é o nó 2 (B contendo 52)
• A chave de 5 é menor do que a de seu pai (nó 2) e o
conteúdo troca de lugar, indo 31 para o nó 2
• O heap está correto e 31 ocupa a posição 2 (B)
19
Classificação
Exercício 9
• Deseja-se classificar objetos armazenados em um vetor com 9
elementos. A classificação deve ser feita por:
•
•
•
•
Seleção
Bolha
“Shell sort”
“Quick sort”
Posição
Conteúdo
1
2
2
8
3
6
4 5 6
1 10 15
7 8 9
3 12 11
• Pede-se mostrar passo a passo a classificação do vetor
supondo:
• a área classificada se expanda do início do vetor para o seu final na
seleção e na inserção
• a área classificada se expanda do final do vetor para o seu início na
bolha
• no “Shell sort” os intervalos sejam 4, 2 e 1 (inserção)
• no “Quick sort” o ponto de separação seja obtido da média dos
valores extremos.
21
Exercício 9
Posição
Conteúdo
1
2
2
8
3
6
4 5 6
1 10 15
7 8 9
3 12 11
Solução
Seleção
Posição
1
2
3
4
5
6
7
8
9
22
1
1
1
1
1
1
1
1
1
1
2
8
2
2
2
2
2
2
2
2
3
6
6
3
3
3
3
3
3
3
4
2
8
8
6
6
6
6
6
6
5
10
10
10
10
8
8
8
8
8
6
15
15
15
15
15
10
10
10
10
7
3
3
6
8
10
15
11
11
11
8
12
12
12
12
12
12
12
12
12
9
11
11
11
11
11
11
15
15
15
Exercício 9
Bolha
1
2
2
2
2
2
2
2
2
23
2
8
8
6
6
6
6
6
6
3
6
6
8
1
1
1
1
1
4
1
1
1
8
8
8
8
8
5
10
10
10
10
10
10
10
10
6
15
15
15
15
15
3
3
3
7
3
3
3
3
3
15
12
12
8
12
12
12
12
12
12
15
11
9
11
11
11
11
11
11
11
15
2
2
2
2
2
2
2
6
1
1
1
1
1
1
1
6
6
6
6
6
6
8
8
8
8
8
8
8
10
10
10
10
3
3
3
3
3
3
3
10
10
10
12
12
12
12
12
12
11
11
11
11
11
11
11
12
15
15
15
15
15
15
15
2
1
1
1
1
1
1
2
2
2
2
2
6
6
6
6
6
6
8
8
8
8
3
3
3
3
3
3
8
8
10
10
10
10
10
10
11
11
11
11
11
11
12
12
12
12
12
12
15
15
15
15
15
15
1
1
1
1
1
1
2
2
2
2
2
2
6
6
6
3
3
3
3
3
3
6
6
6
8
8
8
8
8
8
10
10
10
10
10
10
11
11
11
11
11
11
12
12
12
12
12
12
15
15
15
15
15
15
1 2 3 6
8
10
11
12
15
Posição
Conteúdo
1
2
2
8
3
6
4 5 6
1 10 15
7 8 9
3 12 11
Exercício 9
“Shell sort”
Intervalo
4
2 86 1
10 15 3 12 
11
2
83
2 8
10 15
11
1 10 15
3 1
6 12
6 12 11
Intervalo
2
2 8
3 1
10 15 
6 12
11
2 1
3 8
6 12
10 15
11
2
13
8
6 12 10 15 11
2
2
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
8
8
8
8
6
6
6
6
6
6
6
6
6
6
8
8
8
8
8
8
Intervalo
1
Inserção
1
2
3
4
5
6
7
8
9
24
3
3
3
3
3
3
3
3
3
3
12
12
12
12
12
12
12
10
10
10
10
10
10
10
10
10
10
12
12
11
15
15
15
15
15
15
15
15
15
12
11
11
11
11
11
11
11
11
11
15
Posição
Conteúdo
1
2
2
8
3
6
4 5 6
1 10 15
7 8 9
3 12 11
Exercício 9
“Quick sort”
Separador
6,5
2
8
6
1 10 15
3 12 11
2
3
6
1 10 15
8 12 11
2
1
3
3
6
6
1
2
1,5
3
2
6
3
2
6
2,5
3
6
1
10 15 8 12 11
10 8 15 12 11
10,5
10 8
8 10
15 12 11
11 12 15
11 12
1
25
2
3
6
8 10 11 12 15
13
Exercício 10
• Deseja-se classificar objetos armazenados em um vetor
com 10 elementos. A classificação deve ser feita por:
• “Quick sort”
Posição
Conteúdo
1
3
2
1
3
4
4
1
5
5
6
9
7
2
8
6
9 10
5 4
• Pede-se mostrar passo a passo a classificação do vetor
supondo:
• O pivô ponto de separação seja obtido pela MedianOfThree
26
Exercício 10
3
1
4
1
5
9
2
6
5
4
Array original
3
1
4
1
5
9
2
6
5
4
Seleção de pivô
3
1
4
1
5
9
2
6
5
4
Partição
3
1
2
1
5
9
4
6
5
4
Restauração do pivô
3
1
2
1
4
9
4
6
5
5
3
1
2
1
9
4
6
5
5
Seleção de pivô
3
1
2
1
9
4
6
5
5
Partição
1
3
2
1
5
4
6
9
5
Restauração do pivô
1
1
2
3
5
4
5
9
6
2
3
5
4
9
6
Cutoff = 2
1
27
1
1
2
3
4
5
4
5
9
6
Concluir com Inserção
1
1
2
3
4
5
4
5
9
6
Array classificado