Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

Estrutura de Dados – 2º período 2019 
Gabarito Segunda Avaliação à Distância 
1. (2,0) Desenhe a árvore AVL obtida pela sequência de inserções das chaves 25, 19, 18, 16, 12, 17, 3, 
5, nesta ordem. Mostre com desenhos as operações de rotação necessárias em cada inclusão. 
R: A seguir são apresentados os passos obtidos na construção de uma AVL para o conjunto de chaves 
dados. 
Inserir 21 Inserir 19 Inserir 18 
 
 
 
 
 Inserir 16 Inserir 12 
 
 
 
 
 
 
 
 Inserir 17 Inserir 3 
 
 
 
 
 
 Inserir 5 
 
 
 
 
 
 
 
25 25
19
25
19
18
19
18 25
19
18
16
25
19
18
16
12
25
19
16
12 18
25
19
16
12 18
17
25
18
16
12 17
19
25
18
16
12
3
17
19
25
18
16
12
3
5
17
19
25
18
16
5
3 12
17
19
25
 
2. (1,5) Desenhe uma árvore B de ordem 2 e altura três que contenha o menor número de chaves 
possível. A seguir, escolha uma chave qualquer para ser removida, e desenhe a árvore B resultante da 
remoção desta chave. 
R: A árvore B a seguir possui o menor número possível de chaves dada a ordem uma ordem 2 e altura 3. 
 
 
 
 
 
 
 
 
Ao removermos a chave 2, obtemos a seguinte árvore B: 
 
 
 
 
 
 
 
 
20
10, 15
1, 2 11, 12 16, 17
25, 30
21, 22 26, 27 31, 32
15, 20, 25, 30
1, 10, 11, 12 16, 17 21, 22 26, 27 31, 33
3. (2,0) Execute o método de ordenação por heap (“heapsort”), aplicando-o as seguintes prioridades 
(nesta ordem): 48, 25, 41, 34, 14, 18, 10, 52, 50. Desenhe os passos intermediários do algoritmo, 
desenhando cada passo em formato de árvore. 
R: Para aplicarmos o heapsort precisamos que a lista apresentada seja um heap. Neste sentido, 
aplicando o algoritmo de construção em tempo linear (O(N)) à lista de prioridades dada, tempos os 
seguintes passos. 
 
Condição Inicial 
 
Desce 34 
 
Desce 25 
 
 
Desce 25 
 
Desce 48 
 
Desce 48 – Condição final do heap 
 
 
 
48
25
34
52 50
14
41
18 10
48
25
52
34 50
14
41
18 10
48
52
25
34 50
14
41
18 10
48
52
50
34 25
14
41
18 10
52
48
50
34 25
14
41
18 10
52
50
48
34 25
14
41
18 10
Agora, aplicamos o heapsort a partir do heap 52, 50, 41, 48, 14, 18, 10, 34, 25. Os seguintes passos são 
executados. 
Condição Inicial 
 
Troca 52 e 25
 
Desce 25
 
Troca 50 e 25 
 
Desce 25 
 
Troca 48 e 10 
 
Desce 10 
 
Troca 41 e 10
 
52
50
48
34 25
14
41
18 10
25
50
48
34 52
14
41
18 10
50
48
34
25 52
14
41
18 10
25
48
34
50 52
14
41
18 10
48
34
25
50 52
14
41
18 10
10
34
25
50 52
14
41
18 48
41
34
25
50 52
14
18
10 48
10
34
25
50 52
14
18
41 48
Desce 10 
 
Troca 34 e 14 
 
Desce 14 
 
Troca 25 e 10
 
Desce 10 
 
Troca 18 e 10 
 
Desce 10 
 
Troca 14 e 10 – Condição Final
 
 
 
34
25
10
50 52
14
18
41 48
14
25
10
50 52
34
18
41 48
25
14
10
50 52
34
18
41 48
10
14
25
50 52
34
18
41 48
18
14
25
50 52
34
10
41 48
10
14
25
50 52
34
18
41 48
14
10
25
50 52
34
18
41 48
10
14
25
50 52
34
18
41 48
4. (1,5) Suponha um conjunto de 6 chaves S, dispostos em uma tabela de dispersão T de tamanho 9, 
segundo uma função de dispersão h, onde o tratamento de colisões se realiza pelo método do 
encadeamento interior. Para cada item abaixo, determine valores que as chaves devem possuir, a 
função de dispersão h e a tabela T obtida, de forma a satisfazer a condição solicitada. 
a) Não existam colisões 
R: Utilizando o modelo de encadeamento interior heterogêneo, sejam h = x mod 6 e S = {1, 2, 3, 4, 5, 
6}, temos a seguinte tabela de dispersão: 
Posição Chave 
0 6 
Endereços 
Bases 
1 1 
2 2 
3 3 
4 4 
5 5 
6 
Sinônimos 7 
8 
 
b) Existem colisões, mas não colisões secundárias. 
R: Utilizando o modelo de encadeamento interior heterogêneo, sejam h = x mod 6 e S = {1, 3, 5, 7, 9, 
10}, temos a seguinte tabela de dispersão: 
Posição Chave 
0 
Endereços 
 Bases 
1 1 
2 
3 3 
4 10 
5 5 
6 7 
Sinônimos 7 9 
8 
 
c) Exista exatamente uma colisão secundária. 
R: Utilizando o modelo de encadeamento interior homogêneo, sejam h = x mod 9 e S = {1, 2, 3, 4, 10, 
8}, teremos uma colisão secundária ao inserir a chave 8. A seguinte tabela de dispersão será obtida: 
 
 
 
 
 
 
 
Posição Chave 
0 
1 1 
2 2 
3 3 
4 4 
5 
6 
7 8 
8 10 
5. (1,5) Dê exemplo de duas cadeias X e Y, com 8 e 4 caracteres respectivamente, que leve o algoritmo 
de força bruta para casamento de cadeias a realizar o maior número possível de comparações entre 
caracteres. Observação: o algoritmo procura determinar se Y é subcadeia de X. 
R: De acordo com o conteúdo da Aula 34, as seguintes cadeias de caracteres podem resultar no maior 
número possível de comparações: 
X = bbbbbbbb 
Y = bbba 
Equação: 
M x (N – M + 1), onde M = tamanho de Y e N = tamanho de X 
Número máximo de comparações: 
4 x (8 – 4 + 1) = 20 Comparações. 
 
 
6. (1,5) Para um certo conjunto de 8 símbolos, em relação aos quais se deseja construir uma árvore de 
Huffman H, escolha as frequências correspondentes a esses símbolos, de tal forma que H possua 
altura mínima. Desenhe a árvore obtida. 
R: De uma forma geral, para se obter uma árvore de Huffman de altura mínima, é necessário que, no 
caso de empate na escolha de uma sub -árvore de altura mínima durante o processo de construção, a 
árvore escolhida seja sempre a de menor altura. Desta maneira, a árvore de Huffman resultante terá 
altura mínima para qualquer conjunto de frequências. Como temos 8 símbolos, a menor altura possível 
para uma árvore com 8 folhas é 3, sendo esta uma ́arvore cheia. Tendo 8 frequências iguais, por 
exemplo, todas as possíveis árvores de Huffman construídas a partir deste conjunto de frequências 
serão cheias, e, portanto, de altura mínima. 
Portanto, sejam s1= 1,s2= 1,s3= 1,s4= 1,s5= 1,s6= 1,s7= 1,s8= 1, temos a seguinte árvore H. 
 
8
4
2
s1 s2
2
s3 s4
4
2
s5 s6
2
s7 s8

Mais conteúdos dessa disciplina