Prova de Estrutura de Dados - Questões de AVL, B-Árvore, Heap e Huffman

Prévia do material em texto

FACOM – UFMS
Segunda Prova de Estrutura de Dados
Questão I [2.5 pontos] Considere a árvore AVL abaixo. Usando o algoritmo estudado em sala,
qual a árvore AVL resultante após realizar a remoção do elemento “d”.
lb
c
d
e
f
g
h
i
j
ka
Questão II [2.5 pontos] Considere a B-árvore de ordem d = 2 abaixo cujas chaves são as
letras do alfabeto. Usando os algoritmos estudado em sala, qual a B-árvore resultante após
realizar as seguintes operações: (i) inserção da chave A; (ii) remoção da chave P (na árvore
resultante do item (i)). Desenhe a árvore após cada operação.
SN O U V Y ZB C D E J K L
G M XT
P
R
Questão III [2.5 pontos]
1. [0.5] A sequencia (3, 4, 1, 2) corresponde a um heap? Justifique sua resposta.
2. [2.0] Liste todas as permutações de (1, 2, 3, 4) que correspondem a um heap.
Questão IV [2.5 pontos] Considere o seguinte texto “AGACAGACCTCAGCATCACA”.
1. [1.5] Aplique o algoritmo de Huffman estudado em sala para realizar a compactação
do texto. Desenhe a árvore de Huffman. Qual o código de cada caracter?
2. [1.0] Qual o tamanho (em bits) do texto compactado?
Boa prova!