Aula de exercicios 05 (Heap, AVL e Tabela hash)

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Eletrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
Aula de exercícios sobre árvores AVL e tabela hash 
Obs: para resolver essas questoes considere as representacoes (e implementacoes) vistas em sala de 
aula. Nas estruturas recursivas, resolva as questoes usando recursao. 
1. Partindo de uma árvore AVL vazia, realize a inserção da seguinte sequência de chaves: 99, 44, 71, 
80, 74, 63, 59, 120, 98, 150. Redesenhe a árvore após cada inserção. Indique para cada rotação 
feita, o nó desregulado e a rotação aplicada (LL,RR,LR,RL). 
2. Usando a árvore construída no exercício anterior, remova os nós 59 e 63 mostrando as árvores 
resultantes a cada exclusão e a rotação aplicada (quando necessário). 
3. Um programador A inseriu os elementos do vetor [14,8,25,19,16,6,3,4,5] em ordem em uma 
árvore AVL inicialmente vazia. Um programador B inseriu os elementos do vetor 
[14,8,25,19,16,6,3,5,4] em ordem em uma outra árvore AVL inicialmente vazia. Ambos 
programadores afirmam que apenas rotações simples aconteceram. Eles estão corretos? 
Justifique sua resposta. 
4. Imagine que você tem o seguinte vetor [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] e quer inseri-los 
numa árvore AVL inicialmente vazia de forma a evitar rotações. Note que se você inserir nessa 
ordem, a árvore começa a pesar para a direita e as rotações inevitavelmente acontecem. Voce 
teria alguma idéia para inserir esses elementos na árvore AVL de forma a evitar qualquer rotação? 
Se sim, descreva sua idéia. 
5. Qual é a vantagem mais significativa do uso de tabelas hash em relação as outras estruturas de 
dados? 
6. Desenhe uma tabela hash com endereçamento aberto e tamanho 9 (com probing linear). Use a função de 
hash "f(k)=k%9". Insira as chaves: 5, 29, 20, 0, 27 and 18 na tabela nessa ordem e mostre o estado final da 
tabela após executar todas as operações. 
7. Você planeja inserir 1000 itens em uma tabela hash e quer um número médio de 2 acessos em 
uma busca com sucesso. Qual o tamanho do array interno que voce pode utilizar considerando 
que a tabela tem endereçamento fechado e usa chaining para resolver os conflitos? 
8. Uma tabela hash com chaining tem tamanho 512. Qual o número máximo de elementos que 
podem ser colocados na tabela? 
A. 256 
B. 511 
C. 512 
D. 1024 
E. Não existe limite máximo. 
9. Suponha que voce deseja fazer um estudo comparativo entre duas tabelas hash de tamanho 11. 
Uma delas usa endereçamento aberto com probing linear e função primária de hash h’(k)=k % m. 
A outra usa mesma função primaria e probing quadrático com c1=1 e c2=3. Qual a melhor tabela 
considerando que as operações realizadas foram apenas inserções dos valores: 10,22,31,4, 15, 28, 
17, 88, 59?