MO417 - Questão para a prova oral

Número: 2013-042

Enunciado: Seja F={a:45, b:13, c:12, d:16, e:9, f:5} um conjunto de caracteres e suas respectivas frequências, e o seguinte algoritmo de Huffman:

HUFFMAN(C)
1   n = |C|
2   Q = C
3   for i = 1 to n-1
4       allocate a new node z
5       z.right = x = EXTRACT-MIN(Q)
6       z.left = y = EXTRACT-MIN(Q)
7       z.freq = x.freq + y.freq
8       INSERT(Q,z)
9   return EXTRACT-MIN(Q)

A chamada HUFFMAN(F) gera qual árvore:

a)

b)

c)

 
d)

 
e) NDA.


Ideia original de: Carlos Eduardo Alfaro Morales