数据结构-资源 试题库及解析 《数据结构》期末考试试卷C卷-应用题1-微课.pptxVIP

大数据技术与应用资源库数据结构（C语言版）主讲人：章万静目录C卷应用题分析 试题分析1、字符集为{C，H，I，N，A}，各字符出现的次数为{4，2，3，1，7}。1、以各字符出现的次数为权值，构造一棵最优二叉树（哈夫曼树）。（4分）2、求此哈夫曼树的WPL值 (请给出计算过程)。（3分）3、约定从各非终端结点发出的左分支表示0，右分支表示1，并且从根结点读到各叶子结点，请给出各字符相应的哈夫曼编码。（3分）【哈夫曼树】①哈夫曼树的带权路径长度之和最小②权值越小的结点离根结点越远，权值越大的结点离根结点越近③相同的叶子结点构成的哈夫曼树有可能不唯一 试题分析17（1）构建的哈夫曼树如左图所示。01（2）WPL=1*4+2*4+3*3+4*2+7*1=36A10107（3）各字符的哈夫曼编码字符C的哈夫曼编码：10C6字符H的哈夫曼编码：1101014字符 I 的哈夫曼编码：1113I字符N的哈夫曼编码：1100301字符A的哈夫曼编码：0CC17CAAIH106AI3NANH哈夫曼树构建完成{7，10}{4，7，6}{4，3，7，3}{17}{4，2，3，1，7}21大数据技术与应用资源库数据结构（C语言版）谢谢观看主讲人：章万静