Uma árvore binária completa pode ser armazenada de
maneira eficiente em um vetor (os nós no vetor seguem a mesma
ordem de um percurso em largura na árvore).
Escreva uma função não recursiva que
verifica se a árvore armazenada em um vetor é um heap de
máximo, isto é, se todo nó possui uma chave maior
ou igual às chaves dos seus filhos.
int verifica_heap(int *heap, int n);
Escreva uma função não recursiva que
retorna o valor da chave mínima em um heap como definido no item
anterior. Quais elementos precisam ser avaliados?
int chave_mínima(int* heap ,
int n);
Seja H um heap de máximo de tamanho n armazenado
em um vetor. Em quais posições do vetor você pode
encontrar:
a segunda menor chave;
a terceira menor chave;
a segunda maior chave e
a terceira maior chave?
Descreva dois métodos para transformar um vetor em um
heap. Simule seu métodos para a seguinte entrada: 12, 25, 13,
17, 19, 3, 14, 5, 11. Qual método é o melhor?
Execute as operações indicadas no heap contendo os
seguintes elementos (nesta ordem): 90, 80, 70, 50, 60, 68, 56, 45, 54,
55.
insira 104
remova 90
substitua 80 por 27 e atualize o heap
substitua 50 por 85 e atualize o heap
Crie um algoritmo O(log n) para a operação
Remove_Heap(A,i), que remove do heap A o elemento na
posição i do vetor.
Qual o número mínimo e máximo de elementos
que podem ser armazenados em um heap de profundidade d?
Árvore AVL
Dada uma árvore binária T, proponha um algoritmo
que determine se T é uma árvore AVL (lembrando-se das
restrições de altura e de árvore de busca).
Uma árvore AVL pode ter 2 folhas cujas profundidades (isto
é, as respectivas distâncias até a raiz) difiram de
mais do que 2? Por exemplo, uma folha teria profundidade 10 e outra
teria 7.
Desenhe a sequência de árvores que se obtém
pela construção de uma árvore AVL pela
inclusão das chaves a seguir, nesta ordem em uma árvore
originalmente vazia: 170, 289, 110, 153, 128, 140, 303, 240, 264, 255.
Nesta questão, você deverá executar duas
inserções e duas remoções de chaves da
árvore AVL mostrada baixo. Desenhe a árvore resultante da
operação correspondente, seguindo estritamente os
algoritmos explicados em classe.
Insira 105
Insira 20
Remova 99
Remova 36
Árvore B
Dada uma árvore B de ordem 512, diga:
Qual é o número máximo de descendentes
de um uma nó?
Qual é o número mínimo de descendentes
de uma nó (excluindo a raiz e as folhas)?
Qual é o número mínimo de descendentes
do nó raiz?
Qual é o número mínimo de descendentes
de uma folha?
Quantas chaves há numa nó não-folha com
200 descendentes?
Qual é a máxima profundidade da árvore
se ela contém 100000 chaves?
Dada a árvore B (com no máximo 4 chaves e 5
subárvores) mostrada abaixo, desenhe as árvores
resultantes da aplicação das operações
seguintes operações: inserção de 98,
inserção de 28, remoção de 94 e
remoção de 13.
Mostrar as árvores B resultantes da remoção
de A, B, Q e M, nesta ordem.
Descreva como prover acesso seqüencial ordenado a um
arquivo indexado por uma árvore B.
Tabela de Espalhamento
Na tabela de espalhamento representada na figura abaixo, a
função de hashing é dada pelo resto da
divisão do valor da chave pelo tamanho da tabela e a
estratégia para resolução de colisões
é linear.
Posição
Chave
Estado
0
-
Livre
1
6
Ocupado
2
1
Ocupado
3
-
Livre
4
-
Removido
Explique a importância para a operação de
busca dos três estados: livre, ocupado e removido.
Quais são os problemas relacionados à
resolução de colisões usando a estratégia
linear?
Escreva um algoritmo para remover um valor X de uma hash table
que usa uma função de espalhamento f e
endereçamento aberto com reespalhamento linear para resolver
colisões. Mostre que marcar a posição previamente
ocupada por X como "livre" não resolve o problema. Como deve ser
elaborado um algoritmo de busca para que funcione corretamente quando
remoções são permitidas?
Grafo
Desenhe um grafo orientado e sua representação
utilizando listas de adjacências e matrizes de adjacências.
Comente quais são as vantagens e desvantagens de cada uma destas
representações levando em consideração o
espaço para armazenamento e a complexidade das seguintes
operações: (i) verificar a existência de uma
aresta; (ii) verificar quais são os nós adjacentes a um
nó j e (iii) verificar quais nós apontam para um
nó j. Para cada um destes itens, leve em
consideração a existência de grafos densos (muitas
arestas) e esparsos (poucas arestas).
O professor Ricardo promoverá um jantar de
confraternização para os n alunos deste curso. Todos os
alunos deverão se sentar numa mesa redonda de n lugares. O
problema do professor é o seguinte: verificar se é
possível garantir que cada pessoa tenha um amigo ou amiga
sentado de ambos os lados, sabendo-se as relações de
amizade entre os alunos e sendo que estas não são
necessariamente transitivas (isto é: se A é amigo de B e
B é amigo de C isto não significa necessariamente que A
é amigo de C). Formule o problema do professor Ricardo como um
problema em grafos e diga claramente qual o problema que tem que ser
resolvido usando a linguagem de grafos.