民國107年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第66題
有一文字檔共有4 個符號,這些符號所對應的霍夫曼碼(Huffman Codes),那些長度不可能出現?
題目
有一文字檔共有4 個符號,這些符號所對應的霍夫曼碼(Huffman Codes),那些長度不可能出現?
- (1) 2222
- (2) 3222
- (3) 3321
- (4) 3322
官方答案
(2) 3222、(4) 3322
解析
霍夫曼碼建構於完整的二元樹上，每個內部節點皆有兩個子節點，因此所產生的前置碼必滿足 Kraft 不等式且總和恰為 1（∑2^(-l_i)=1）。以 4 個符號檢驗：選項 1『2222』總和=4×(1/4)=1，可行；選項 3『3321』總和=1/8+1/8+1/4+1/2=1，可行。選項 2『3222』總和=1/8+3×(1/4)=7/8<1；選項 4『3322』總和=2×(1/8)+2×(1/4)=3/4<1，二者均小於 1，代表樹非完整，不可能是霍夫曼碼。故不可能出現者為 2、4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。