MO417 - Questão para a prova oral

Número: 091

Enunciado: Para usar a codificação Huffman foram vistos dois possíveis símbolos no alfabeto de códigos: 0 e 1. Se adicionarmos um símbolo adicional (2) e continuarmos exigindo um código de prefixo que minimize o número de símbolos usados, formaríamos o que chamamos de uma codificação Huffman ternária. Qual das seguintes alternativas é correta sobre esta forma alternativa de codificar:

1. A altura da árvore tende a ser maior numa codificação Huffman ternária do que numa codificação de Huffman binária.
2. Trocando o símbolo 2 por 10 numa codificaç%atilde;o Huffman ternária é resulta em um código de prefixo válido.
3. Cada nó interno da árvore gerada terá dois filhos.
4. Uma codificação Huffman ternária pode ser obtida em tempo O(n lg n).
5. NDA.

Autor(a): Sheila Maricela Pinto Cáceres