[RUY] Perguntas das provas antigas de AA - P2

Prévia do material em texto

EXERCÍCIOS P2 AA
1) Ao inserir uma nova chave numa árvore AVL, SEMPRE é feita pelo menos uma operação de rotação, para garantir o balanceamento por altura da árvore.
( ) Verdadeiro. Justifique.			( ) Falso. Justifique.
2) Utilizando o algoritmo de Programação Dinâmica, determinte o caminho mais curto do vértice A até o vértice H no grafo abaixo. 
A
C
B
E
D
G
F
J
H
I
3
2
2
1
4
5
3
3
1
4
2
1
3
2
Além disso, determine o comprimento do correspondente caminho mais curto.
OBS.: Indique a execução do algoritmo, armazenando as informações intermediárias no próprio desenho dado do grafo.
3) . Admita os custos da tabela seguinte para as operações de edição.
Operação
Copiar
Trocar
Inserir
Apagar
Custo
0
4
3
2
(i) Utilizando o algoritmo de programação dinâmica, determine a distância de edição entre as cadeias “REGUA” e “ENTREGA”.
(ii) Além disso, forneça a seqüência de operações de edição correspondentes a referida distância
4) Numa árvore AVL de altura 8, o número de nós na subárvore à direita da raíz é pelo menos 33.
( ) Verdadeiro. Justifique.			( ) Falso. Justifique.
5) Considere a seguinte lista ORDENADA de palavras: 				 Abacate < Banana < Caqui < Lima
com freqüências de busca dadas pelos pesos da tabela abaixo.
Item
Abacate
Banana
Caqui
Lima
Freqüência
2
4
1
1
2
3
4
5
2
	Utilizando o algoritmo de Programação Dinâmica, construa uma ABB que minimize o custo ponderado de busca para este caso.
	Impondo “Banana” como raiz, construa uma ABB que minimize o custo ponderado de busca.
Obs: justifique suas respostas apresentando os cálculos intermediários
e as correspondentes tabelas.
6) Utilizando o algoritmo de programação dinâmica, forneça a seqüência de operações que determine a distância de edição entre as cadeias “TREGUA” e “REFREGA”. Admita os custos da tabela seguinte para as operações de edição.
Operação
Copiar
Trocar
Inserir
Apagar
Custo
0
1
1
1
Qual a maior altura possível para uma árvore AVL com 638 nós?