Alternativa A
A codificação de Huffman é um algoritmo de compressão de dados que constrói uma árvore binária onde os símbolos com maior probabilidade recebem códigos mais curtos e os com menor probabilidade recebem códigos mais longos. Para resolver a questão, devemos reconstruir a árvore de Huffman passo a passo combinando os nós com menores probabilidades.
Construção da Árvore de Huffman
Os passos seguem a ordem crescente das probabilidades dadas na tabela:
- Probabilidades Iniciais:
- F: $0,02$
- E: $0,03$
- D: $0,10$
- C: $0,20$
- B: $0,30$
- A: $0,35$
- Primeira Combinação (Menores valores):
- Unimos F ($0,02$) e E ($0,03$).
- Novo nó (FE): $0,02 + 0,03 = 0,05$.
- Lista atual ordenada: FE($0,05$), D($0,10$), C($0,20$), B($0,30$), A($0,35$).
- Segunda Combinação:
- Unimos FE ($0,05$) e D ($0,10$).
- Novo nó (FED): $0,05 + 0,10 = 0,15$.
- Lista atual ordenada: FED($0,15$), C($0,20$), B($0,30$), A($0,35$).
- Terceira Combinação:
- Unimos FED ($0,15$) e C ($0,20$).
- Novo nó (FEDC): $0,15 + 0,20 = 0,35$.
- Lista atual ordenada: B($0,30$), A($0,35$), FEDC($0,35$).
- Quarta Combinação (Ponto Crítico):
- Temos B ($0,30$) e dois nós com $0,35$ (A e FEDC).
- O menor é B ($0,30$). O segundo menor é arbitrário entre A e FEDC.
- Em questões de concurso, quando há empate, costuma-se priorizar a estabilidade ou a existência de uma única resposta válida. Se unirmos B e A, obtemos um nó de $0,65$, deixando FEDC ($0,35$) separado.
- Nó (BA): $0,30 + 0,35 = 0,65$.
- Lista final: FEDC($0,35$), BA($0,65$).
- Raiz da Árvore:
- Unimos FEDC ($0,35$) e BA ($0,65$).
- Raiz: $1,00$.
Análise dos Comprimentos dos Códigos
Com a estrutura definida acima (onde B e A são irmãos diretos da raiz ou próximos dela), calculamos a profundidade (comprimento do código) para cada símbolo:
| Símbolo | Profundidade (Bits) | Justificativa Estrutural |
|---|
| A | 2 | Raiz \rightarrow BA \rightarrow A |
| B | 2 | Raiz \rightarrow BA \rightarrow B |
| C | 2 | Raiz \rightarrow FEDC \rightarrow C |
| D | 3 | Raiz \rightarrow FEDC \rightarrow FED \rightarrow D |
| E | 4 | Raiz \rightarrow FEDC \rightarrow FED \rightarrow FE \rightarrow E |
| F | 4 | Raiz \rightarrow FEDC \rightarrow FED \rightarrow FE \rightarrow F |
Verificação das Alternativas
Agora comparamos os comprimentos esperados com as opções apresentadas:
- (A) A sequência binária que representa B é 10: Correto. O símbolo B tem 2 bits de comprimento. A sequência "10" possui 2 bits.
- (B) A sequência binária que representa E é 10111: Incorreto. E tem 4 bits. A opção apresenta 5 bits.
- (C) A sequência binária que representa C é 000: Incorreto. C tem 2 bits. A opção apresenta 3 bits.
- (D) A sequência binária que representa A é 0101: Incorreto. A tem 2 bits. A opção apresenta 4 bits.
- (E) A sequência binária que representa F é 11000: Incorreto. F tem 4 bits. A opção apresenta 5 bits.
Portanto, a única alternativa consistente com a estrutura da árvore de Huffman gerada pelos dados fornecidos é a letra A.