哈夫曼编码及平均编码长度_哈夫曼编码平均编码长度怎么计算

2023年408真题数据结构篇 　　一、单项选择题 　　第01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。 　　01. 　　下列对顺序存储的有序表（长度为
）实现给定操作的算法中，平均时间复杂度为
的是（ ）。 　　A. 查找包含指定值的素的位置 　　B. 插入包含指定值素的算法 　　C. 删除第
个素的算法 　　D. 第
个素的算法 　　解答： 　　方法一：分析选项 　　顺序存储的有序表即有序数组。 　　A选项中，在有序数组中查找包含指定值的素的位置最快的方法是用二分查找，时间复杂度为
。该选项错误。 　　B选项中，在有序数组中查找包含指定值的素最快的方法是首先用二分查找找到插入素的位置，时间复杂度为
，然后把位于插入素后面的素的位置后移一格，平均时间复杂度为
，综上，总的时间复杂度为
。该选项错误。 　　C选项中，删除第
个素的最快的方法是首先利用顺序表支持随机访问的性质找到第
个素并删除，时间复杂度为
，然后把位于插入素后面的素的位置前移一格，平均时间复杂度为
，综上，总的时间复杂度为
。该选项错误。 　　D选项中，第
个素利用顺序表支持随机访问的性质找到第
个素并访问即可，时间复杂度为
。该选项正确。 　　本题选D。 　　方法二：性质顺序表（顺序存储）：方便随机访问，不方便插入和删除。链表（链式存储）：方便插入和删除，不方便随机访问。 　　顺序表中只有随机访问素时间复杂度为
，即根据素位置（下标）访问素时间复杂度为
。只有D选项符合要求。 　　本题选D。 　　本题难度：⭐️ 　　02. 　　现有非空双向链表
，其结点结构为：
，
是指向直接前驱结点的指针，
是指向直接后继结点的指针，若要在
中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句 “s->next = p->next; p->next = s;” 后，下列语句序列中还需要执行的是（ ）。 　　A. s->next->prev = p; s->prev = p; 　　B. p->next->prev = s; s->prev = p; 　　C. s->prev = s->next->prev; s->next->prev = s; 　　D. p->next->prev = s->prev; s->next->prev = p; 　　解答： 　　设原来插入新结点前指向 p 的直接后继结点的指针为 q ，题目要求在 p 和 q 之间插入新的结点 s 。 　　双向链表插入结点的时候要修改四个指针，这四个指针的修改顺序没有强制要求，也就是有
种连接顺序，但是这里注意要按照题目要求的顺序连线。

　　初始为图(a)。四个指针的初始状态为： 　　p->next = q; q->prev = p; s->next = null; s->prev = null; 　　最终状态为： 　　p->next = s; q->prev = s; s->next = q; s->prev = p; 　　先按照题目要求执行前两步： 　　s->next = q; 注意此时 q = p->next，即 s->next = p->next; 此时变为图(b)。 　　p->next = s; 此时变为图(c)。 　　还有两条线没有连，目标是得到图(d)。还需要连接 s->prev = p; 和 q->prev = s; 注意此时 q = s->next，即 s->next->prev = s; 找了一圈发现没有这种写法，命题组在这里加大了难度，把写法复杂化，我们只能逐一分析选项了。按照选项的指针在图(c)上运行： 　　A选项，等价于 q->prev = p; s->prev = p; 第一句错误。 　　B选项，等价于 s->prev = s; s->prev = p; 第一句错误。 　　C选项，等价于 s->prev = p; q->prev = s; 正确。 　　D选项，等价于 s->prev = null; q->prev = p; 第一句和第二句均错误。 　　本题选C。 　　评：本题把图给画出来才不容易被选项绕晕，命题组编题确实煞费苦心。 　　本题难度：⭐️⭐️⭐️ 　　03. 　　若采用三组表存储结构存储系数矩阵 M。则除三组外，下列数据中还需要保存的是（ ）。 　　I. M 的行数 　　II M 中包含非零素的行数 　　III. M 的列数 　　IV. M 中包含非零素的列数 　　A. 仅 I 和 III 　　B. 仅 I 和 IV 　　C. 仅 II 和 IV 　　D. I、II、III 和 IV 　　解答： 　　三组存储矩阵的表示方法出现在2017年第3题，三组表的表项存储了行row、列col、值value三种信息，我们还需要知道矩阵 M 的规模 rows × cols，即 M 的行数 rows 和 M 的列数 cols，这个信息应该直接给出，即 I 和 III 。 　　本题选A。 　　本题难度：⭐️⭐️ 　　04. 　　在由 6 个字符组成的字符集 S 中，各字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼编码的加权平均长度为（ ）。 　　A. 2.4 　　B. 2.5 　　C. 2.67 　　D. 2.75 　　解答： 　　构建哈夫曼树：

　　每个关键字的查找长度为： 　　
　　注意，题目要求求加权平均长度，这里的权重就是频次。 　　加权平均长度为
。 　　如果不考虑权重，会错误计算为
，从而误选C。 　　本题选B。 　　本题难度：⭐️⭐️⭐️⭐️ 　　05. 　　已知一棵二叉树的树形如下图所示，若其后序遍历为 f, d, b, e, c, a，则其先（前）序遍历序列是（ ）。

　　A. a, e, d, f, b, c 　　B. a, c, e, b, d, f 　　C. c, a, b, e, f, d 　　D. d, f, e, b, a, c 　　解答： 　　这道题的图与2014年的图一模一样。 　　方法一：递归法 　　首先按照后序遍历左右根的递归遍历顺序自下而上，从左到右将 f, d, b, e, c, a 填入二叉树。 　　然后按照先序遍历根左右的递归顺序输出先序序列 a, e, d, f, b, c 。 　　本题选A。

　　方法二：环线法 　　首先构造环线按后序遍历顺序填入后序序列 f, d, b, e, c, a 。 　　然后按照环线进行先序遍历输出先序序列 a, e, d, f, b, c 。 　　本题选A。 　　注：补充一下二叉树前序遍历、中序遍历、后序遍历的特征：

　　按照箭头方向遍历。前序遍历顺序为“根左右”，在第一次访问某结点时输出该结点的关键字。中序遍历顺序为“左根右”，在第二次访问某结点时输出该结点的关键字。后序遍历顺序为“左右根”，在第三次访问某结点时输出该结点的关键字。 　　本题难度：⭐️⭐️ 　　06. 　　已知无向连通图 G 中各边的权值均为 1，下列算法中，一定能够求出图 G 中从某顶点到其余各顶点最短路径的是（ ）。 　　I. 普利姆（Prim）算法 　　II. 克鲁斯卡尔（Kruskal）算法 　　III. 图的广度优先搜索算法 　　A. 仅 I 　　B. 仅 III 　　C. 仅 I 和 II 　　D. I、II 和 III 　　解答： 　　无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可以用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比Dijkstra算法更加高效。III正确。 　　I 和 II 是最小生成树算法，也可直接排除。 　　本题选B。 　　本题难度：⭐️⭐️ 　　07. 　　下列关于非空 B 树的叙述中，正确的是（ ）。 　　I. 插入操作可能增加树的高度 　　II. 删除操作一定会导致叶结点的变化 　　III. 查找某关键字总是要查找到叶结点 　　IV. 插入的新关键字最终位于叶结点中 　　A. 仅 I 　　B. 仅 I 和 II 　　C. 仅 III 和 IV 　　D. 仅 I、II 和 IV 　　解答： 　　原则上一切以《数据结构（C语言版）》和其参考用书《数据结构基础》1976年版等为准。 　　I. 插入操作可能会导致关键字上溢，关键字上溢到根结点，树的高度加一。I 正确。 　　II. 如果删除的关键字位于叶结点：在叶结点中删除该关键字，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果删除该结点后关键字个数
，没有后续操作，如果该结点删除关键字后关键字个数
，需要从兄弟结点借一个关键字，又分兄弟够借和兄弟不够借两种情况，这里不进行继续分析。无论上述哪种情况，此时叶结点一定发生变化。如果删除的关键字位于非叶结点：用被删除关键字的后继关键字替换被删除关键字，该后继关键字为于被删除关键字的右子树的最下层最左边，即一定位于叶结点，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果该结点删除关键字后关键字个数
，没有后续操作，如果删除该结点后关键字个数
，需要从兄弟结点借一个关键字，又分兄弟够借和兄弟不够借两种情况，这里不进行继续分析。此时叶结点一定发生变化。 　　综上，无论删除关键字是位于叶结点还是位于非叶结点，一定有叶结点发生变化。II 正确。 　　III. B树中所有结点均可以存储关键字，若查找的关键字位于非叶结点，则不可能查找到叶结点。III错误。 　　IV. 插入新的关键字，插入后进行调整，新插入的关键字不一定位于叶结点中。可以用依次将关键字5, 6, 9, 14, 8, 2, 12, 15, 13插入初始为空的4阶B树进行模拟，最后13位于非叶结点中。也就是插入关键字后若被插入关键字所在的结点需要进行调整（结点发生分裂），且被插入的关键字此时恰为该结点的第
个关键字，则该关键字会上溢到该结点的父结点，如此迭代，也就是在这种情况下被插入的关键字最终一定位于非叶结点中。 　　分享一个数据可视化网站：B-Tree Visualization，可以模拟B树的插入和删除过程，该网站的B树基本操作的算法在不勾选勾选 Preemptive Split / Merge (Even max degree only) 的情况下和《数据结构（C语言版）》（参考用书《数据结构基础》1976年版）的B树插入操作算法完全一致，B树删除操作算法略有区别，《数据结构（C语言版）》要求用直接后继关键字代替被删除关键字，而该网站用直接前驱关键字代替被删除关键字。 　　还有，为什么《数据结构（C语言版）》不详细介绍删除的关键字位于非叶结点的情况，第一个原因可能是该情况相比删除的关键字位于叶结点更加复杂，直接留给学生自学。第二个原因可能是B树是是一棵分支极多的树，导致的结果是绝大多数关键字都位于叶结点上，也就意味着绝大多数关键字操作都是直接作用在叶结点上。 　　综上，I 和 II 正确。 　　本题选B。 　　拓展 　　《数据结构（C语言版）》：B树插入操作算法：后置分裂；B树删除操作算法：后置合并。 　　《算法导论》：B树插入操作算法：前置分裂；B树删除操作算法：前置合并。 　　注意408考试中不能使用《算法导论》的B树基本操作的算法进行模拟。因为如果用《算法导论》中的B树基本操作的算法进行分析会得出错误答案： 　　I. 插入操作前置分裂可能需要分裂根结点，此时需要创建新的根结点，树的高度加一。I 正确。 　　II. 如果删除的关键字位于叶结点：在叶结点中删除该关键字，该叶结点一定发生变化。如果删除的关键字位于非叶结点：先进行单程向下的合并进行前置分裂，可以合并被删除关键字结点的孩子结点
和
，设
在左边，
在右边，若
和
还有孩子结点，
的最右边的孩子结点会和
最左边的孩子结点合并，递归到叶结点终止，一定有两个叶结点发生合并。此时叶结点一定发生变化。 　　综上，无论删除关键字是位于叶结点还是位于非叶结点，一定有叶结点发生变化。II 正确。 　　III. B树中所有结点均可以存储关键字，若查找的关键字位于非叶结点，则不可能查找到叶结点。III错误。 　　IV. 插入新的关键字，一定位于叶结点。IV 正确。 　　此时，I 、II 和 IV 正确。 　　所以如果按照《算法导论》B树基本操作的算法进行模拟，本题选D。但是408中凡是《算法导论》与《数据结构（C语言版）》有冲突的地方一切以《数据结构（C语言版）》为准。 　　2022年第8题B选项为如果按照《数据结构（C语言版）》的删除算法进行模拟，为错误选项，但可以用《算法导论》B树删除操作的算法解释。但命题组的出题意图应该仅仅是为了考察B树性质（详见本人2022年第8题题解的方法一），以及B树的基本操作必须维护B树性质这两点，所以出现了这种包含多种B树删除操作的算法的真题，考纲中也没有明确说明，只能从历年真题进行推断。注意，《数据结构（C语言版）》中B树插入操作的算法与《数据结构（C语言版）》中B树删除操作的算法是配对的，《算法导论》中B树插入操作的算法与《算法导论》中B树删除操作的算法是配对的，原则上两者不能混用。 　　本题难度极高，全面考察了《数据结构（C语言版）》中B树的基本操作。 　　本人完整整理B树考点如下： 　　408数据结构考点：B树 　　本题难度：⭐️⭐️⭐️⭐️⭐️ 　　08. 　　对含 600 个素的有序顺序表进行折半查找，关键字间的比较次数最多是（ ）。 　　A. 9 　　B. 10 　　C. 30 　　D. 300 　　解答： 　　本题几乎与2010年第9题完全一致。 　　由于素数量过大，不方便画图，采用公式法。 　　方法一：公式法 　　若采用折半查找法查找一个顺序表中不存在的素，最大比较次数为对应二叉搜索树的高度，设结点数为
， 　　二叉搜索树高度为
。 　　代入
，解得
。 　　本题选B。 　　本题难度：⭐️⭐️ 　　09. 　　现有长度为 5 ，初始为空的散列表 HT，散列函数
，用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入 HT 中，然后删除关键字 25 ，则 HT 中查找失败的平均查找长度为（ ）。 　　A. 1 　　B. 1.6 　　C. 1.8 　　D. 2.2 　　解答： 　　散列函数为
，处理冲突采用线性探测再散列法，依次填入关键字 2022, 12, 25。 　　插入
，
，此时槽位
为空，直接插入。 　　
　　插入
，
，此时槽位
被占据，发生冲突，执行冲突处理方法，这里为线性探测法，每次向右探索一个槽位，如果探测到达末尾，那么从第一个槽位开始继续探测，直到到达一个空槽位，然后插入。 　　
　　
　　插入
，
，此时槽位
为空，直接插入。 　　
　　删除
，注意，线性探测再散列法属于开放寻址法，从运用开放寻址法的散列表中删除关键字比较困难。当我们从某槽位删除关键字时，不能简单地将槽位设置为
，如果这样做，就会出现问题。所以需要为该槽位增加
标记，这里
简单记为
。 　　
　　最后查找失败的平均查找长度。 　　查找素失败统计项数目与散列表槽位数和散列函数均有关。这里取
。 　　散列函数散列到槽位
到
，按照冲突处理方法，我们可以计算出每种情况查找失败需要的次数，即失败查找长度： 　　散列到槽位
： 　　
　　散列到槽位
： 　　
　　散列到槽位
： 　　
　　散列到槽位
： 　　
　　散列到槽位
： 　　
　　综上，所有情况查找失败需要的次数，即失败查找长度： 　　
　　
　　本题选C。 　　评：这道题综合考察了散列函数，冲突处理方法，开放寻址法的散列表中删除标记，以及平均失败查找长度。在2010年第43题的基础上继续加大难度。 　　参考《算法导论》相关章节如下：算法导论（第四版）第十一章：散列表　第四节：开放寻址法 　　本题难度：⭐️⭐️⭐️⭐️⭐️ 　　10. 　　下列排序算法中，不稳定的是（ ）。 　　I. 希尔排序 　　II. 归并排序 　　III. 快速排序 　　IV. 堆排序 　　V. 基数排序 　　A. 仅 I 和 II 　　B. 仅 II 和 V 　　C. 仅 I、III 和 IV 　　D. 仅 III 、 IV 和 V 　　解答： 　　本题为送分题，牢记八大排序表格。 　　稳定的排序有：插入排序、冒泡排序、归并排序、基数排序。 　　不稳定的排序有：选择排序、希尔排序、快速排序、堆排序。 　　本题选C。 　　本题难度：⭐️ 　　11. 　　使用快速排序算法对数据进行升序排序， 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢是（ ）。 　　A. 11 　　B. 70 　　C. 80 　　D. 81 　　解答： 　　快速排序一个非常重要的性质是枢轴左边的关键字全部小于或等于枢轴，枢轴右边的关键字全部大于或等于枢轴。 　　由于序列比较长，正向推导不容易观察，可以代入选项后分析。 　　A选项，枢轴为11 ，左边 68 > 11 。该选项错误。 　　B选项，枢轴为70 ，右边 23 < 70 。该选项错误。 　　C选项，枢轴为80，右边 48 < 80 。该选项错误。 　　D选项，枢轴为81。该选项正确。 　　本题选D。 　　本题难度：⭐️ 　　二、综合应用题 　　41~47小题，共70分。 　　41. 　　（13分） 　　已知有向图
采用邻接矩阵存储，类型定义如下： 　　将图中出度大于入度的顶点称为 K 顶点。例如在题41图中，顶点 a 和 b 都是 K 顶点。

题41图 　　请设计算法： int printVertices(MGraph G)，对给定的任意非空有向图 G，输出 G 中所有 K 顶点，并返回 K 顶点的个数。要求： 　　⑴ 给出算法的基本设计思想。 　　⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 　　解答： 　　本题与2021年第41题及其相似，但是由于要分别统计入度和出度，比2021年第41题略难，2021年第41题408史上最简单算法题，本题为408史上第二简单算法题。 　　⑴ 由于
是采用邻接矩阵
表示，
表示存在有向边
，
表示不存在有向边
。 　　算法的基本设计思想如下：第一步：统计所有顶点的入度和出度。若存在边
，即
，则顶点
的出度加一，顶点
的入度加一。若不存在边
，即
，则顶点
的出度不变，顶点
的入度不变。综上，顶点
的出度加
，顶点
的入度加
。第二步：统计所有顶点中出度大于入度的顶点（即 K 顶点）的个数，本题还需要打印 K 顶点，注意是打印 K 顶点的名称（char 类型），不是打印 K 顶点的下标（int 类型），所以需要通过 VerticesList 将顶点下标转换为顶点名称。 　　⑵ 根据上述思路，C代码如下（含测试用例）： 　　复杂度分析时间复杂度：
，其中
为图中点个数。因为需要遍历整个邻接矩阵，所以为
。空间复杂度：
，开辟了
大小的辅助数组。 　　时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）： 　　复杂度分析时间复杂度：
，其中
为图中点个数。因为需要遍历整个邻接矩阵，所以为
。空间复杂度：
，使用了常数个辅助变量。 　　42. 　　（10分） 　　对含有
0)” eeimg=”1″> 个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存
个记录，请回答下列问题。 　　⑴ 若文件中含有 19 个记录，其关键字是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100；当
时，可以生成几个初始归并段？各是什么？ 　　⑵ 对任意的
0)” eeimg=”1″> ，生成的第一个初始归并段的长度最大值和最小值分别是多少？ 　　解答： 　　408史上第一次对外部排序进行考察，本题要求模拟置换-选择排序的过程。 　　假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA初始为空，并设内存工作区WA的容量可容纳w个记录。则置换-选择排序的操作过程为：(1) 从FI输入w个记录到缓冲区WA。(2) 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。(3) 将MINIMAX记录输出到FO中去。(4) 若FI不空，则从FI输入下一个记录到WA中。(5) 从WA中所有比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。(6) 重复(3)~(5)，直到在WA中选不出新的MINIMAX为止，由此得到一个初始归并段，输出归并段结束标志到FO中。(7) 重复(2)~(6)，直到WA为空，由此得到全部初始归并段。 　　⑴ 对题目所给关键字序列进行置换-选择排序： 　　
　　最后分成三个归并段：37, 51, 63, 92, 94, 9914, 15, 23, 31, 48, 56, 60, 90, 1668, 17, 43, 100 　　⑵ 对任意的
0)” eeimg=”1″> ，生成的第一个初始归并段的长度： 　　设输入序列为
，假设所有关键字互不相同。 　　最大值为
，刚开始进入WA的
个关键字一定能够被输出，一般地，考虑
均能够被输出到第一个归并段，则只要每次进入WA的关键字恰巧大于刚刚离开WA的关键字。也就是
，这里
m” eeimg=”1″> ，只要
在序列
中为第
大的关键字，其中
，则
一定能被输出到第一个归并段。特殊地，假设输入序列为一个升序序列， 即
，则所有关键字一定都被输出到第一个归并段。 　　最小值为
，刚开始进入WA的
个关键字一定能够被输出，一般地，考虑
均不能被输出到第一个归并段，有
\max\{x_{m+1},x_{m+2},\dots,x_{2m}\}” eeimg=”1″> ，也就是集合
中所有关键字被输出后，停留在WA的集合
中所有关键字均无法被输出到第一个归并段。特殊地，假设输入序列为一个降序序列， 即
x_2>\dots>x_n ” eeimg=”1″> ，则只有前
个关键字能够被输出到第一个归并段。 　　后记 　　2023考研人数为474万，再创新高，很多同学都是阳了以后顶着高烧在考场上拼搏，真的非常不容易。2023真题除了冷门考点，大多数都是在历年真题的基础上强化。我给选择题难度打⭐️，数据结构部分有两道题5⭐️难度，平均2.8⭐️，应该是历年真题中比较难的一年了，比2021难，比2022简单，这个卷子能上120绝对高分了，今年国家线继续上涨的可能性极小。现在考研真的一年比一年难，只要有梦想，就还有希望。