MO417 - Questão para a prova oral

Número: 106

Enunciado:
Sobre o algoritmo guloso de Huffman (descrito abaixo) para a construção de um código de prefixo ótimo, assinale a alternativa INCORRETA.

Huffman (C)
    n = |C| 
    Q = C  // Inicializa fila de prioridades Q
    for i =1 to n-1
      do alocar um nó z
         esquerda[z] = x = EXTRACT_MIN(Q)
         direita[z] = y = EXTRACT_MIN(Q) 
         f[z] = f[x] + f[y] 
         INSERT (Q, z)
return EXTRACT_MIN(Q) 

onde: 
  C é um conjunto de n caracteres e que cada caractere c pertencente a C tem frequência definida f[c]
  Q é uma fila de prioridade mímina, tendo f como chave

1. O algoritmo constrói de baixo para cima uma árvore que corresponde ao código ótimo.
2. O algoritmo roda em tempo O(n lg n).
3. O algoritmo nem sempre produz uma árvore binária cheia (onde cada nó interno tenha exatamente dois filhos).
4. Sua prova de correção se baseia nas propriedades de escolha gulosa e subestrutura ótima encontradas no problema de se determinar um código de prefixo ótimo.
5. NDA

Autor(a): Renato Hirata