作业14-Huffman树及其应用(防止标题重复)

r囧r小猫 2022-12-27 09:30 150阅读 0赞

1-1  
对N（≥2）个权值均不相同的字符构造哈夫曼树，  
则树中任一非叶结点的权值一定不小于下一层任一结点的权值。(T)  
\[解析\]我会想到 \{1,1,3,5\}这个序列 , 第一次构造的结点的权值确实小于\{3,5\}但是  
之后是 2和3 构造结点,之后是 5和5 构造结点,所以还是符合条件的

2-1  
对N（N≥2）个权值均不相同的字符构造哈夫曼树。  
下列关于该哈夫曼树的叙述中，错误的是：(D)  
A.树中一定没有度为1的结点  
B.树中两个权值最小的结点一定是兄弟结点  
C.树中任一非叶结点的权值一定不小于下一层任一结点的权值  
D.该树一定是一棵完全二叉树

2-2  
设一段文本中包含字符\{a, b, c, d, e\}，其出现频率相应为\{3, 2, 5, 1, 1\}。  
则经过哈夫曼编码后，文本所占字节数为：()  
A.40  
B.36  
C.25  
D.12  
\[解析\]求得huffman编码后,所占字节数 = ∑(频率 \* 其编码长度)

2-3  
设一段文本中包含4个对象\{a,b,c,d\}，其出现次数相应为\{4,2,5,1\}，  
则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？(B)  
A.0  
B.2  
C.4  
D.5  
\[解析\]求huffman编码后占的位数,与等长的做差

2-4  
由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：©  
A.23  
B.37  
C.44  
D.46  
\[解析\]这里推荐用一下:WPL = 分支结点的和

2-5  
已知字符集\{ a, b, c, d, e, f, g, h \}。若各字符的哈夫曼编码依次是  
0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列 0100011001001011110101  
的译码结果是：(D)  
A.acgabfh  
B.adbagbb  
C.afbeagd  
D.afeefgd  
\[解析\]huffman编码是前缀码,可以唯一确定序列

2-6  
若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长度是()。(D)  
A.28  
B.68  
C.55  
D.59

2-7  
下列叙述错误的是()。(B)  
A.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和  
B.当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为哈夫曼树，其二叉树的形状是唯一的  
C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近  
D.哈夫曼树的结点个数不能是偶数  
\[解析\]之前的博客有相关的解释  
https://blog.csdn.net/qq\_45591813/article/details/109142285

2-8  
哈夫曼树是n个带权叶子结点构成的所有二叉树中()最小的二叉树。©  
A.权值  
B.高度  
C.带权路径长度  
D.度  
\[解析\]最优编码就是为了求带权路径最小的二叉树

2-9  
(neuDS)在哈夫曼树中，任何一个结点它的度都是()。©  
A.0或1  
B.1或2  
C.0或2  
D.0或1或2  
\[解析\]结点包括 需要编码的结点(叶子结点) 以及由两个结点组成的结点

7-3 哈夫曼编码 (30分)  
给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，  
使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。  
例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为  
4、2、1、1。我们可以设计编码 \{‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111\}，也可以用另一套  
\{‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000\}，还可以用 \{‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101\}，  
三套编码都可以把原文压缩到 14 个字节。但是 \{‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001\}  
就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，  
“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否  
哈夫曼编码。  
输入格式：

首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

c\[1\] f\[1\] c\[2\] f\[2\] … c\[N\] f\[N\]

其中c\[i\]是集合\{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘\_’\}中的字符；f\[i\]是c\[i\]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

c\[i\] code\[i\]

其中c\[i\]是第i个字符；code\[i\]是不超过63个’0’和’1’的非空字符串。  
输出格式：

对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码  
都应被判为正确。

int main()
    {
        
    	//先求得一套huffman编码
    	//输入是否是huffman编码的判断条件:
    	//1. 是前缀码
    	//2. WPL = 自己求得的huffman的WPL
        //两条都满足才是huffman编码   
        
        //ios::sync_with_stdio(false);
        string codes[MAXN];
        int N, M;
        int f[MAXN], c[MAXN];
        //一会改一下输入，别人不人鬼不鬼的
        cin >> N;
        getchar();
        for (int i = 1; i <= N; i++)
        {
        
            scanf("%c %d", &c[i], &f[i]);
            getchar();
            //printf("%c %d\n", c[i], f[i]);
        }
        //getchar();
        HuffmanTree HT;
        HuffmanCoding(HT, f, N);
        
        //得到这个huffman树的带权路径长度
        int WPL = 0;
        for (int i = 1; i <= 2 * N - 1; i++)
        {
        
            if (HT[i].lchild != 0 && HT[i].rchild != 0)
                WPL += HT[i].weight;
        }
        //cout << WPL << endl;
        
        //
        string code[65];
        int m;
        cin >> m;
        getchar();
        while (m--)
        {
        
            int This_solution_weight = 0;
            for (int i = 1; i <= N; i++)
            {
        
                char c;
                cin >> c >> code[i];
                //cout << code[i] << endl;
                This_solution_weight += code[i].length() * f[i];
            }
            
            //最短路径大于WPL
            if (This_solution_weight > WPL)
            {
        
                cout << "No" << endl;
                continue;
            }
    
            //判断是否是前缀编码
            int flag = 0;
            for (int i = 1; i <= N; i++)
            {
        
                for (int j = 1; j <= N; j++)
                {
        
                    if (i == j) continue;
    
                    if (code[i].length() < code[j].length()) 
                    {
        
                        if (code[i] == code[j].substr(0, code[i].length()))
                        {
        
                            flag = 1;
                            break;
                        }
                    }
                    else if (code[i] == code[j])
                    {
        
                        flag = 1;
                        break;
                    }
                }
            }
    
            if (flag == 1) 
                cout << "No" << endl;
            else 
                cout << "Yes" << endl;
        }
        
        //system("pause");
        return 0;
    }