Questão para a Prova Oral 103

Semana 8: 21/04/2003
Assunto: Códigos de Huffman

Sobre Códigos de Huffman e o respectivo algoritmo (extraído do livro Algotitmos) a seguir, é CORRETO afirmar que:

HUFFMAN(C)
1  N <- |C|
2  Q <- C
3  for i <- 1 to n-1 do
4     alocar um novo nó z
5     esquerda[z] <- x <- EXTRACT-MIN(Q) // EXTRACT-MIN() é uma operação de heap
6     direita[z] <- y <- EXTRACT-MIN(Q) // EXTRACT-MIN() é uma operação de heap
7     f[z] <- f[x] + f[y]
8     INSERT(Q, z)
9  return EXTRACT-MIN(Q)

A) Apesar de ser muito utilizado, essa técnica de compressão não é eficiente.
B) O máximo que consegue é guardar a relação típica de 50% dos dados.
C) A complexidade do algoritmo é n^2, pois o loop executa n-1 vezes várias operações, que juntas, têm complexidade n.
D) O código de Huffman pode formar uma estrutura binária (árvores), mas é normalmente usado como gerador de estruturas ternárias (esqerda, central, e direita).
E) n.d.a.
Autor: Patrick Henrique da Silva Brito
RA: 022279