Prova-Final-2012-2 Prova 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/02/2013 
 
 
Questão 1 (1 ponto): 
(a) Escreva um algoritmo de remocao de um valor inteiro x de uma lista duplamente encadeada, 
ordenada, com nó cabeça. 
 
Questão 2 (2 pontos): 
Calcule a arvore binaria de busca otima, para as chaves 1, 2, 3, 4, e 5 com frequencias de 
acesso iguais a 1, 3, 7 , 8 e 5 respectivamente. Mostre a tabelinha que o algoritmo preenche. 
 
Questão 3 (1.5 pontos): 
 
a) Insira, em uma arvore rubro-negra, Left-leaning, as seguintes chaves: 12, 7, 20, 26, 18 , 24, 25 
nesta ordem. Mostre a arvore após cada passo que altere a sua estrutura. 
 
Questão 4 (2 pontos): 
 a) Insira em uma árvore B na qual cada no tem entre 2 e 4 chaves (3 e 5 filhos) , inicialmente 
contendo as chaves 10, 15 e 42, as seguintes chaves, nesta ordem: 
 70, 90, 75, 80, 92, 91 e 60. Sempre que a estrutura da arvore for afetada, voce deve mostrar a arvore 
antes e após sua operacao. 
 
 b) da arvore obtida em (a), remova a menor chave no nó que e' a raiz da arvore. 
 
Questão 5 (1,5 pontos): 
 a) Insira em uma heap de fibonacci inicialmente vazia, SEM AVALIACAO TARDIA, os 
seguintes valores, nesta ordem: 1, 3, 5, 7, 9, 11, 13, 15, 17, 33. 
 b) Da heap obtida, remova o valor minimo. 
 
Questão 6 (2 pontos): 
 Considere uma tabela de Hash com encadeamento interno, e area de colisao (separada do resto 
da tabela, com 8 posicoes disponiveis na tabela e outras 8 na area de colisao), e funcao hash dada por 
h(x) = x mod 8. 
 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, 4, 8, 9, 16, 20, 24, 28, 32. 
 
 b) Remova da tabela hash obtida a chave 24. Lembre-se de mostrar como fica a lista L.