Estrutura de Dados

Estrutura de Dados - 1◦. per´ıodo de 2014

GABARITO - Segunda Avaliação a Distacia

1. (1,5) Desenhe uma árvore binária de busca de altura 4, que seja estritamente binária e com um número mínimo de n´os, colocando dentro de cada no´ o valor de sua chave. As chaves são 1,2,···,k, onde k ´e o número de nos da árvore. A seguir, escreva a sequência de chaves que corresponde ao percurso em pós-ordem desta árvore.

Resposta: Sendo k = 7 temos:

[pic 1]

• Percurso em pós-ordem: 1,3,2,5,4,7,6.

1. (1,5) Desenhe uma árvore B de ordem d = 3 com dois n´níveis que contenha um número máximo de chaves (os valores das chaves ficam a sua escolha). A seguir, insira uma chave, demonstrando o passo-a-passo desta inserção, até a obtenção da arvore final.

[pic 2]

Após inserção do elemento 47:

[pic 3]

Nova entrada na raiz:

[pic 4]

Nova raiz criada:

[pic 5]

1. (2,0) A partir de uma árvore inicialmente vazia, desenhe a ´arvore AVL resultante da inserção dos nós com chaves 15,90,50,72,80,105,10,12,20, nesta ordem. Mostre com desenhos as operações de rotação necessárias em cada inclusão.

Incluir 15:

15[pic 6]

Incluir 90:

[pic 7]

Incluir 50:

[pic 8]

Rotação Dupla Esquerda

[pic 9]

Incluir 72:

[pic 10]

[pic 11]

Rotação Dupla Direita:

[pic 12]

Inserir 105:

[pic 13]

Rotação Esquerda

www.CompCEDERJ.com.br

[pic 14]

Inserir 10:

[pic 15]

Inserir 12:

[pic 16]

Rotação Dupla Direita:

[pic 17]

Inserir 20:

[pic 18]

Rotação Dupla Direita:

[pic 19]

4. (2,0) Considere a seguinte sequência de números: 10, 91, 20, 40, 32, 88, 5, 74, 90. Execute o método de ordenação por heap (heapsort) para ordenar a sequência dada. Desenhe as configurações sucessivas da árvore durante o processo de ordenação.

Resposta:

[pic 20]

Aplicando o comando arranjar(n).

Descer 40:

[pic 21]

Descer 20:

[pic 22]

Descer 10 (heap obtido):

[pic 23]

m:=9

trocar(TB[1],TB[9])

[pic 24]

[pic 25]

m:=8

trocar(TB[1],TB[8])

[pic 26]

Descer 10:

[pic 27]

m:=7 trocar(TB[1],TB[7])

[pic 28]

Descer 5:

[pic 29]

m:=6

trocar(TB[1],TB[6])

[pic 30]

Descer 10:

[pic 31]

m:=5

trocar(TB[1],TB[5])

[pic 32]

Descer 10:

[pic 33]

m:=4

trocar(TB[1],TB[4])

[pic 34]

Descer 5 m:=3

trocar(TB[1],TB[3])

[pic 35]

Descer 5 m:=2

[pic 36]

1. (1,5) Suponha um conjunto de 7 chaves S, dispostos em uma tabela de dispersão T de tamanho 8, segundo uma função de dispersão h, onde o tratamento de colisões se realiza pelo método do encadeamento interior. Determinar valores que as chaves devem possuir, bem como, escolher a função de dispersão h e descrever a tabela T, em cada caso, para que T obedeça, respectivamente, às seguintes condições:

1. Nao existam colisões.
2. Existam colisões, mas não colisões secundárias.
3. Exista exatamente uma colisão secundária.

ANULADA.

1. (1,5) Desenhe uma ´arvore de Huffman relativa às frequências: 1,1,2,3,4,7,14. A ´arvore que você desenhou ´e a única ´arvore de Huffman possível para estas frequências? Justifique sua resposta. Seja

s1 = 1, s2 = 1, s3 = 2, s4 = 3, s5 = 4, s6 = 7, s7 = 14.

Uma possível árvore de Huffman para as frequências acima ´e:

[pic 37]

Como podemos observar esta representação não ´e única. Abaixo segue uma outra possível representação:

[pic 38]