MO417 - Questão para a prova oral

Número: 082

Enunciado:
Considerando o problema de construir uma árvore de codificação ótima e o algoritmo de Huffman apresentado a seguir para esse problema, julgue as seguintes afirmativas:

Huffman(C)
1 n ← |C|
2 Q ← C
3 for i ← 1 to n - 1
4     do allocate a new node z
5        left[z] ← x ← Extract-Min(Q)
6        right[z] ← y ← Extract-Min(Q)
7        f[z] ← f[x] + f[y]
8        Insert(Q,z)
9 return Extract-Min(Q)

(1) Em uma árvore de codificação ótima com profundidade máxima ‘x’, todos os nós que estão na profundidade 'x' sempre apresentam freqüências menores ou iguais aos demais nós folha da árvore.

(2) O algoritmo é um exemplo de algoritmo guloso que usa uma abordagem bottom-up, ou seja, resolve primeiro os subproblemas, e usa as soluções deles para resolver o problema.

(3) O problema apresenta a propriedade de subestrutura ótima porque é possível construir a árvore a partir da construção de árvores menores.

Qual das alternativas está CORRETA:

1. Apenas as afirmativas (1) e (2) são verdadeiras.
2. Apenas as afirmativas (1) e (3) são verdadeiras.
3. Apenas as afirmativas (2) e (3) são verdadeiras.
4. Todas estão corretas
5. NDA

Autor(a): Luiz Augusto Muniz de Paula