Prova-Final-2012-1-Estrutura-de-Dados

Prévia do material em texto

Universidade Federal do Rio de Janeiro 
Instituto de Matemática - DCC 
Prova Final – Organização de Dados I 27/06/2012 
 
 
Questão 1 (2 pontos): 
Calcule a arvore binaria de busca otima, para as chaves 10, 20, 30, 40, com frequencias de 
acesso iguais a 10, 5, 6 e 7 respectivamente. Mostre a tabelinha que o algoritmo preenche. 
 
Questão 2 (3 pontos): 
 
a) Insira, em uma arvore rubro-negra, Left-leaning, as seguintes chaves: 
 20, 17, 18, 12, 5, 14, 16 nesta ordem. Mostre a arvore após cada passo que altere a sua 
estrutura. 
 
b) Repita as operacoes, para uma arvore AVL. 
 
 
Questão 3 (1 ponto): 
 a) Insira as seguintes chaves em uma árvore patricia inicialmente vazia: 
 00000, 00100, 11111, 111011, 10101 
 
Questão 4 (2 pontos): 
 a) Insira em uma heap binomial de minimo os seguintes valores, nesta ordem: 1, 3, 5, 7, 9, 11, e 4. 
 b) Da heap obtida, remova o valor 1. 
 
Questão 5 (2 pontos): 
 Considere uma tabela de Hash com encadeamento interno, e area de colisao (separada do resto 
da tabela, com 16 posicoes disponiveis na tabela e outras 16 na area de colisao), e funcao hash dada 
por h(x) = x mod 16. 
 Considere que a area de colisao encontra-se inicialmente em uma lista apontada por L de 
posicoes disponiveis. 
 a) Mostre como fica a hash com a insercao das chaves 2, 34, 18, 16, 32 , 64, e 34. 
 
 b) Escreva o algoritmo de busca de uma chave x nesta tabela hash.