Round12—Huffman 樹

判斷題：

1-1對N（≥2）個權值均不相同的字元構造哈夫曼樹，則樹中任一非葉結點的權值一定不小于下一層任一結點的權值。 （T）

解析：考察哈弗曼樹的構造方法，哈弗曼樹的構造思想就是貪心的思想，每次選擇權值最小的兩個節點來形成新的節點，自底向上建樹，是以對于一棵哈弗曼樹來說，樹中任一非葉節點的權值一定不小于下一層的任意節點的權值。

單選題：

2-1對N（N≥2）個權值均不相同的字元構造哈夫曼樹。下列關于該哈夫曼樹的叙述中，錯誤的是： (2分)

• 樹中一定沒有度為1的結點
• 樹中兩個權值最小的結點一定是兄弟結點
• 樹中任一非葉結點的權值一定不小于下一層任一結點的權值
• 該樹一定是一棵完全二叉樹

解析：因為哈弗曼樹的構造每一次選擇兩個權值最小的節點是以，整個哈弗曼樹的節點的度要麼為0要麼為2，不存在度為1的節點。

是以我們第一次的選取就是将權值最小的兩個節點來形成哈弗曼樹的第一個新節點，是以樹中兩個權值最小的結點一定是兄弟結點。

根據1-1的分析我們可以知道第三個是正确的。

不難看出哈弗曼樹不一定符合完全而二叉樹的定義。

2-2設一段文本中包含字元{a, b, c, d, e}，其出現頻率相應為{3, 2, 5, 1, 1}。則經過哈夫曼編碼後，文本所占位元組數為： (2分)

• 40
• 36
• 25
• 12

解析：考察哈弗曼樹的構造與WPL（帶權路徑長度）的求法。

應該是10個字元的文本平均占用的位元組數。

2-3設一段文本中包含4個對象{a,b,c,d}，其出現次數相應為{4,2,5,1}，則該段文本的哈夫曼編碼比采用等長方式的編碼節省了多少位數？ (2分)

• 2
• 4
• 5

解析：等長編碼也就是說abcd四個字元用兩位二進制數表示（00,01,10,11），采用哈弗曼編碼計算WPL為24，比等長編碼少了2。

2-4由分别帶權為9、2、5、7的四個葉子結點構成一棵哈夫曼樹，該樹的帶權路徑長度為： (2分)

• 23
• 37
• 44
• 46

解析：考察哈弗曼樹的建立與WPL的求法。

2-5已知字元集{ a, b, c, d, e, f, g, h }。若各字元的哈夫曼編碼依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，則編碼序列 0100011001001011110101 的譯碼結果是：(2分)

• acgabfh
• adbagbb
• afbeagd
• afeefgd

解析：因為哈夫曼編碼使得兩兩之間不會互為字首碼，是以可以唯一确定序列。

2-6若以｛4，5，6，3，8｝作為葉子節點的權值構造哈夫曼樹，則帶權路徑長度是（）。 (2分)

• 28
• 68
• 55
• 59

解析：同上。

2-7下列叙述錯誤的是（）。 (2分)

• 一棵哈夫曼樹的帶權路徑長度等于其中所有分支結點的權值之和
• 當一棵具有n 個葉子結點的二叉樹的WPL 值為最小時，稱其樹為哈夫曼樹，其二叉樹的形狀是唯一的
• 哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近
• 哈夫曼樹的結點個數不能是偶數

解析：對于第四個，我們知道n個葉子節點，那麼其哈弗曼樹的節點數為2*n-1。

2-8哈夫曼樹是n個帶權葉子結點構成的所有二叉樹中（）最小的二叉樹。 (2分)

• 權值
• 高度
• 帶權路徑長度
• 度

解析：哈弗曼樹的性質。

2-9(neuDS)在哈夫曼樹中，任何一個結點它的度都是（ ）。 (2分)

• 0或1
• 1或2
• 0或2
• 0或1或2

解析：哈弗曼樹的性質。

程式設計題：

7-1 修理牧場 (25 分)

農夫要修理牧場的一段栅欄，他測量了栅欄，發現需要N塊木頭，每塊木頭長度為整數L​i​​個長度機關，于是他購買了一條很長的、能鋸成N塊的木頭，即該木頭的長度是L​i​​的總和。

但是農夫自己沒有鋸子，請人鋸木的酬金跟這段木頭的長度成正比。為簡單起見，不妨就設酬金等于所鋸木頭的長度。例如，要将長度為20的木頭鋸成長度為8、7和5的三段，第一次鋸木頭花費20，将木頭鋸成12和8；第二次鋸木頭花費12，将長度為12的木頭鋸成7和5，總花費為32。如果第一次将木頭鋸成15和5，則第二次鋸木頭花費15，總花費為35（大于32）。

請編寫程式幫助農夫計算将木頭鋸成N塊的最少花費。

輸入格式:

輸入首先給出正整數N（≤10​4​​），表示要将木頭鋸成N塊。第二行給出N個正整數（≤50），表示每段木塊的長度。

輸出格式:

輸出一個整數，即将木頭鋸成N塊的最少花費。

輸入樣例:

8
4 5 1 2 1 3 1 1
           

輸出樣例:

49
           

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    priority_queue<int, vector<int>, greater<int> > que;
    int n, x;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        que.push(x);
    }

    int ans = 0;
    while(que.size() != 1)
    {
        int a = que.top();
        que.pop();
        int b = que.top();
        que.pop();

        int c = a + b;
        ans += c;
        que.push(c);
    }
    cout << ans << endl;
    return 0;
}