Universidade Federal de Minas Gerais
Disciplina: DCC002 - Algoritmos e Estrutura de Dados 2
Professor: Flavio Vinicius Diniz de Figueiredo
- Dada uma árvore AVL inicialmente vazia, insira as chaves 0,2,4,6,8 nessa ordem nela e desenhe a árvore depois de cada operação. Indique as rotações que são feitas.
- Escreva o código de uma rotação para a esquerda. O mesmo deve receber apenas um nó. Use ponteiros para cima no seu struct.
- Imagine que você tem o seguinte vetor
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]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. Você teria alguma ideia para inserir esses elementos na árvore AVL de forma a evitar qualquer rotação? Se sim, descreva sua ideia.
- Insira os seguintes valores em uma árvore PV inicialmente vazia e mostre a árvore (incluindo a cor dos nós) após cada operação: 41, 38, 31, 12, 19, 8.
- Implemente um algoritmo recursivo que retorna a quantidade de nós pretos em uma árvore PV
- Para cada propriedade de árvore PV, implemente um algoritmo que verifica cada uma (true se a propriedade é respeitada, false se não).
- Considerando a ordem alfabética, mostre o resultado da inserção dos elementos F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E nessa ordem, em uma árvore B 2-3 inicialmente vazia. Desenhe a árvore após a inserção de cada elemento. Qual a altura da árvore resultante? Caso a ordem da árvore fosse 7, qual seria a altura da árvore resultante?
- Escreva um método que acha o maior elemento de uma árvore B.
- Escreva um método que acha o menor elemento de uma árvore B.
- Qual é a vantagem mais significativa do uso de tabelas hash em relação as outras estruturas de dados?
- 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 e 18 na tabela nessa ordem e mostre o estado final da tabela após executar todas as operações.
- 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 você pode utilizar considerando que a tabela tem endereçamento fechado e usa chianino para resolver os conflitos?