【2023考研】数据结构常考应用典型例题（含真题）

前言

本文针对《数据结构》，博主花了几天时间列出了考研常考的应用题型，讲解详细，方便复习。

各类题型所涉及的知识点包括但不限于队列、二叉排序树、平衡二叉树、哈夫曼树及哈夫曼编码、图的存储、最小生成树、关键路径、排序算法等等。（标题即为考点）。

例题出自408真题，以及各高校的自主命题（含王道解析）。

本文干货十足，建议收藏，以防丢失。

（后期会继续补充题目，已补充B树插入删除、二次探测法题目）

目录

一、队列

1、请设计一个队列，满足：

① 初始时队列为空；

② 入队时，允许增加队列占用空间；

③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；

④ 入队操作和出队操作的时间复杂度始终保持为 O(1)。

（1）该队列是应选择链式存储结构，还是应选择顺序存储结构？

（2）画出该队列的初始状态，并给出判断队空和队满的条件。

（3）画出第一个元素入队后队列状态。

（4）给出入队操作和出队操作的基本过程。

来源：2019统考真题（408）

解：（1）顺序存储无法满足要求 ② 的队列占用空间随着入队操作而增加。根据要求来分析：

要求 ① 容易满足；

链式存储方便开辟新空间，要求 ② 容易满足；

对于要求 ③，出队后的结点并不真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间，赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入队操作和出队操作的时间复杂度均为 O(1)，要求 ④ 可以满足。

因此，采用链式存储结构（两段式单向循环链表），队头指针为 front，队尾指针为 rear。

（2）该循环链式队列的实现可以参考循环队列，不同之处在于循环链式队列可以方便地增加空间，出队的结点可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也要区分队满和队空的情况，这里参考循环队列牺牲一个单元来判断。

初始时，创建只有一个空闲结点的循环单链表，头指针 front 和尾指针 rear 均指向空闲结点， 如下图所示：

队空的判定条件: front == rear
队满的判定条件: front == rear->next 

（3）插入第一个元素后的状态如下图所示。

 （4）操作的基本过程如下:

//入队操作:
若(front == rear->next)      //队满
    则在rear后面插入一个新的空闲结点;

入队元素保存到rear所指结点中; rear=rear->next; 返回。

//出队操作:
若(front == rear)        //队空
    则出队失败，返回;

取front所指结点中的元素e; front-front->next; 返回e。

2、请回答以下问题：(10分)
（1）队列在顺序存储时的 “假溢出” 现象指什么?
（2）简述一种可行的假溢出的解决方法。
（3）若用数组 q[1..m] 表示队列，队列头指针 front、尾指针 rear 的初值均为1,
基于（2）中的方法，如何求队列的当前长度？如何判定队空？如何判定队满？

来源：北京邮电大学803 2018年

 解：（1）对于顺序存储的队列，执行入队和出队操作时，头、尾指针只增大不减小，致使出队元素的空间无法被重新利用。因此，尽管队列中实际元素个数可能远小于数组大小，但可能由于尾指针已超出数组下标的界限而不能执行入队操作。该现象称为 “假溢出” 。

（2）解决假溢出的方法，可以采用循环队列。

入队操作时，若队列不满，则将新元素插入队尾指针 rear 所指位置，并令 rear = (rear+1)%m；

出队操作时，若队列不空，则令队头指针 front 所指元素出队，并令 front = (front+1)%m。

其中，m 为队列总长度。

（3）队空条件: front == rear

队满条件: front == (rear+1)%m

队列长度: length = (rear-front+m)%m

二、树

（一）二叉排序树

利用逐点插入法建立序列(50， 72，43, 87, 75，20, 34，53, 65, 30) 对应的二叉排序树。并求出这 10 个元素基于该二叉排序树的组织，在等概率情况下查找成功时的平均查找长度。(15 分)

来源：华中科技大学834 2018年

解：⼆叉排序树中，各结点关键字的⼤⼩关系为：左⼦树 ≤ 根节点 ≤ 右⼦树。如下图：

 若查找的目标关键字位于树的第 i 层，则查找长度为 i。

因此在等概率情况下，查找成功的平均查找长度：ASL = (1×1 + 2*2 + 3*3 + 4*3 + 5*1) / 10 = 3.1

（二）平衡二叉树

可搭配以下链接学习：​​​​​​【考研】数据结构之平衡二叉树考点_住在阳光的心里的博客-CSDN博客_考研平衡二叉树

 【考研】数据结构：红黑树（2022新增考点）_住在阳光的心里的博客-CSDN博客_考研红黑树

47. 将关键字序列 {116, 100, 101, 115, 117, 103} 依次插入到初始为空的平衡二叉树(AVL树)，给出每插入一个关键字后的平衡树，并说明其中可能包含的平衡调整步骤(即，先说明是哪个结点失去平衡，然后说明做了什么平衡处理)；然后分别给出前序、中序和后序遍历该二叉树的输出结果。(10分)

来源:中国科学院大学 863 2019年

解： 如下图：

前序遍历（根左右）: 115，101，100，103，116，117
中序遍历（左根右）: 100，101，103，115，116，117
后序遍历（左右根）: 100，103，101，117，116，115

（三）森林与二叉树的转换

1、森林转换成二叉树的画法：

① 将森林中的每棵树转换成相应的二叉树；

② 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线;

③ 以第一棵树的根为轴心顺时针旋转 45 度。

2、二叉树转换为森林的规则：

若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。

二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二又树依次转换成树，就得到了原森林。

3、二叉树转换为树或森林是唯一的。

将下面一个由 3 棵树组成的森林转换为二叉树。

（四）哈夫曼树及哈夫曼编码

1. 假设传输的数据包含 5 个字母 A, B, C, D, E 字母出现的频率: A-20%，B-10%，C-30%，D-25%，E-15%，请构造哈夫曼编码以及哈夫曼树。 (10分)

来源：北京大学869 2019年

 解：哈夫曼树如下图：（注意：本题哈夫曼树、哈夫曼编码不唯一。）

 所以，哈夫曼编码为：（不是唯一的）

A：01                 

B：000                 

C：10                 

D：11               

E：001

【补充】树的带权路径长度（树中所有叶子结点的带权路径长度之和）计算。

结点的带权路径长：从该结点到树根之间的路径长度与结点上权的乘积。

（1）针对步骤四的二叉树：

其带权路径长度 WPL =  =20*2 + 10*3 + 30*2 + 25*2 + 15*3 = 225

（2）针对下图：

2. 对于一个字符集中具有不同权值的字符进行 Huffman 编码时，如果已知某个字符的Huffman 编码为 0101，对于其他无字符的 Huffman 编码，请分析说明:

(1) 具有哪些特征的编码是不可能的
(2) 具有哪些特征的编码是一定会有的 (10分)

来源:四川大学874 2018年

解：如下图：

(1) 0，01, 010， 三个编码不可能出现；以0101为前缀的编码也不可能出现。

(2) 以 1，00， 011， 0100 为开头的编码一定会有。

三、图

（一）邻接表及邻接矩阵、最小生成树

(15分) 针对下图的无向带权图，
（1）写出它的邻接矩阵，并按 Prim 算法求其最小生成树。
（2）写出它的邻接表，并按 kruskal 算法求其最小生成树。

来源:北京大学869 2018年

解： （1）邻接矩阵如下：

 按 Prim 算法求得的最小生成树如下：

（2）邻接表如下：

按 kruskal 算法求得的最小生成树如下：

【补充】Prim 算法和kruskal 算法详细步骤如下：

（二）DFS和BFS（图的遍历）

可搭配以下链接进行学习：

深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜） (biancheng.net)

画出以下的无向图的深度优先生成树和广度优先生成树。

  1、DFS（深度优先搜索是一个不断回溯的过程。）

（1）首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；

（2）然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；

（3）当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；

（4）通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3  邻接点 V6 ，然后 V7 ；

（5）由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；

（6）最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。

当使用深度优先搜索算法（DFS）时，假设 V1 作为遍历的起始点，涉及到的顶点和边的遍历顺序为（不唯一）：V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7，此种遍历顺序构建的生成树为：

2、BFS

假设 V1 作为起始点，遍历其所有的邻接点 V2 和 V3 ，以 V2 为起始点，访问邻接点 V4 和 V5 ，以 V3 为起始点，访问邻接点 V6 、 V7 ，以 V4 为起始点访问 V8 ，以 V5 为起始点，由于 V5 所有的起始点已经全部被访问，所有直接略过， V6 和 V7 也是如此。

进行广度优先搜索遍历得到的顺序：

V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8，其生成树为：

（三）拓扑排序

可搭配以下链接一起学习：

【考研】数据结构考点——拓扑排序_住在阳光的心里的博客-CSDN博客

 输出以下有向图的拓扑序列。

 拓扑序列：（拓扑排序每次选取入度为0的结点输出）

1，5，2，3，6，4

1，5，2，6，3，4

5，1，2，3，6，4

5，1，2，6，3，4

（四）关键路径

已知图G的邻接矩阵为下表所示，请画出该图，并求该图 G 的关键路径及路径长度。(10分)

来源:中国科学院大学863 2017年。

 解：可知此图为有向带权图，该图如下：

关键路径就是从源点到汇点的所有可能路径中，最长的一条。 即如下图：

 【补充】分析关键路径的详细步骤如下：

（五）最短路径

41.(10分)已知有向图描述为{<A,B,1>, <A,E, 6>, <A,D,7>, <B,C,2>, <B, E, 4>, <C,D,3>,<C,E,1>, <E,D,1> }，各项中的数字表示两顶点间的权值。
(1) 画出该有向图;
(2) 利用迪杰斯特拉(Djkstra) 算法求顶点A到其它各顶点间的最短距离，写出求解过程。

来源:北京邮电大学803 2017年

解： 如下图：

所以， 顶点A到其它各顶点间的最短距离如下：

A到B的最短距离：A->B，路径长度为1。

A到C的最短距离：A->B->C，路径长度为3。

A到D的最短距离：A->B->C->E->D，路径长度为5。

A到E的最短距离：A->B->C->E，路径长度为4。

【注意】用 Floyd（弗洛伊德）算法计算最短路径：

如下图：

四、散列(Hash)表及其查找

（一）线性探测法

采用哈希函数 H (k) = 3*k mod 13 并用线性探测开放地址法处理冲突，在数列地址空间[0..12] 中对关键字序列 22, 41, 53, 46, 30, 13,1, 67, 51。
（1）构造哈希表(画示意图);
（2） 装填因子;
（3）成功的平均查找长度。
（4）不成功的平均查找长度。

来源:华中科技大学834 2017年

解：（1） 如下图所示：（在数列地址空间[0..12] 中，此句意思为：表长13）

 （2） 散列表的地址空间大小为13，有9个关键字已经插入，因此装填因子 = 9/13

（3）如下图： 

（4）查找失败时的平均查找长度 ASL失败 = (3+2+1+3+2+1+4+3+2+1+2+1+4)/13 = 29/13 = 2.23

例如：

对于散列地址为0的关键字，查找失败时的查找长度为3。(发生冲突时， 通过线性探测，找到第一个空,也就是2的位置，才能确定查找失败)

对于散列地址为1的关键字，查找失败时的查找长度为2。(发生冲突时， 通过线性探测，找到第一个空，也就是2的位置，才能确定查找失败)

对于散列地址为2的关键字，查找失败时的查找长度为1。(刚开始检查的Hash地址就是空的， 可以直接确定查找失败)

需要注意，若散列表采用这种顺序存储，则对空结点的检查也算一次关键字的对比。 而对于采用拉链法实现的散列表，对空指针的比较不能算作一次关键字对比。
 

（二）拉链法（即链地址法）

1、已知一组关键字为（22, 41, 53, 46, 30, 13, 1, 67, 51），设散列函数 H (k) = 3*k mod 13，用链地址法处理冲突。
（1）构造散列表(画示意图);
（2） 装填因子;
（3）成功的平均查找长度。
（4）不成功的平均查找长度。

 解：如下图：

 （2） 散列表的地址空间大小为13，有9个关键字已经插入，因此装填因子 = 9/13

（3）对每个单链表中的第 1 个结点的关键字（如13，22，53，41，46，51，30），查找成功只需比较 1 次，而对第 2 个结点（如1，67），查找成功需比较 2 次。

此时，查找成功的平均查找长度为：ASL成功 = (1*7 + 2*2) / 9 = 11/9 = 1.22

（4）整个散列表有13个单链表组成，用数组 HT[0..12] 存放各个链表的头指针。如散列地址为 3 的同义词 53，1 构成一个单链表，链表的头指针存放在 HT[3] 中。

在用链地址法处理冲突时，待查的关键字不在表中，例如：若计算散列函数 H(k) = 0， HT[0] 的指针域为空，比较1次即确定查找失败。若 H(k) = 1, HT[1] 所指单链表包括 4 个结点，则需比较 5 次才能确定失败。

如此，针对上图：

HT[0] 所指单链表包括 1 个结点，需比较 2 次才能确定失败。

HT[1] 所指单链表包括 1 个结点，需比较 2 次才能确定失败。

HT[2] 的指针域为空，比较 1 次确定失败。

HT[3] 所指单链表包括 2 个结点，需比较 3 次才能确定失败。

HT[4] 的指针域为空，比较 1 次确定失败。

……

以此类推，可得查找失败的平均查找长度为：ASL失败 = ( 6*1 +5*2 + 2* 3 ) / 13 = 1.69

2、设关键字序列为（64, 5, 95, 53, 18, 25, 65, 27, 16），散列函数为H(key)=key%7，采用链地址法解决冲突，请回答：（8分）

（1）画出散列表示意图（用头插法向单链表中插入结点）

（2）查找关键字 95 时，需要依次与哪些关键字比较

（3）求等概率下查找成功的平均查找长度

来源：2013 暨南大学 830

解：（1）（一定要特别注意是用头插法向单链表中插入结点，输出结果与输入顺序相反）

散列表如下图：

（2）查找关键字95时，需要依次与关键字 25、18、53 比较。

（3）平均查找长度为：（1*5 + 2*2 + 3*1 + 4*1）/ 9 = 16/9

（三）二次探测法

设有一组关键字（71, 23, 73, 14, 55, 89, 33, 43, 48），采用哈希函数：H(key) = key %10，采用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列 ( 按从左到右的次序 ) 构造哈希表，并计算在查找概率相等的前提下，成功查找的平均查找长度。

来源：2016 暨南大学真题

解：首先要了解二次探测法的增量序列  的取值 ：

注意：二次探测处理冲突时，散列表的表长要满足 4j + 3 的形式，由 H(key) = key %10 可知，表长不应该是10，而是11。（这是平方探测法处理冲突的时候的要求，不是所有散列表的要求。）

哈希函数：H(key) = key %10，所以

71 % 10 = 1，比较次数为1

23 % 10 = 3，比较次数为1

73 % 10 = 3，冲突，则 （73 + 1 ）% 10 = 4，比较次数为2

14 % 10 = 4，冲突，则 （14 + 1 ）% 10 = 5，比较次数为2

55 % 10 = 5，冲突，则 （55 + 1 ）% 10 = 6，比较次数为2

89 % 10 = 9，比较次数为1

33 % 10 = 3，冲突，则 （33 + 1 ）% 10 = 4，冲突，则 （33 – 1 ）% 10 = 2，比较次数为3

43 % 10 = 3，冲突，则 （43 + 1 ）% 10 = 4，冲突，则 （43 – 1 ）% 10 = 2，冲突，则 （43 + 4 ）% 10 = 7，比较次数为4

48 % 10 = 8，比较次数为1

所以，由二次探测处理冲突得：

成功查找的平均查找长度 ASL = (1 + 1 + 2 + 2 + 2 + 1 + 3 + 4 + 1) / 9 = 17/9。

（四）总结

由上述可看出，线性探测法在处理冲突的过程中易产生记录的二次聚集，使得散列地址不同的记录又产生新的冲突；而链地址法处理冲突不会发生类似情况，因为散列地址不同的记录在不同的链表中，所以链地址法的平均查找长度小于开放地址法。

另外，由于链地址法的结点空间是动态申请的，无需事先确定表的容量，因此更适用于表长不确定的情况。同时，易于实现插入和删除操作。

五、折半查找判定树

可搭配以下链接学习：

【考研】数据结构考点——折半查找和折半插入排序_住在阳光的心里的博客-CSDN博客

设一组有序的记录关键字序列为( 14, 19, 25, 36, 48, 51, 63, 84, 91)，运用二分法进行查找，请给出二分查找的判定树，以及查找关键字84时的比较次数，并计算出查找成功时的平均查找长度。

来源:华中科技大学834 2019年

解：二分查找的判断树如下: 

查找成功时的平均查找长度 ASL成功 = (1*1 + 2*2 + 3*4 + 4*2)/9 = 25/9
 

六、B 树

可搭配以下链接一起学习：

【考研复习：数据结构】查找（不含代码篇）_住在阳光的心里的博客-CSDN博客

1、已知一棵 3 阶的 B- 树如图 2 所示，依次插入关键字 30 及 90，分别画出每插入一个关键字后所生成的 B- 树。(7 分)

源自：暨南大学2014真题

 解：见下图：

 【补充】含 B 树概念和对此题的具体分析

（1）此题分析如下：

 3 阶的 B- 树，可知其他结点的关键字数范围为 [1, 2]，子树的数量范围为 [2, 3]

插入 30 时，先与根结点 32 比较，30 < 32，在左子树。

再与 24 比较，24 < 30，在右子树，与 25 并列排放。

（25，30）满足分支结点的关键字数范围 [1, 2]，所以不用再调整。

插入 90 时，插入到 80 的右边，有（50，80，90），不符合分支结点的关键字数范围 [1, 2]，所以需要分裂。

拆分前，设此时结点数内的关键字数为 m ，则拆分的关键是找  的位置，

（50，80，90）的   的位置是 80，则以 80 为界，一分为二，如下图。

 将 80 并入到其父结点中，并判断是否满足分支结点的关键字数范围 [1, 2] 的条件，则有如下图：

 在拆分的过程中，一定要注意隐含条件：即 40 < 45 < 50 < 80 < 90

即 子树1 < 关键字1 < 子树2 < 关键字2 < …..

针对此题，B 树删除结点情况举例：

 删除15，可知 15 的兄弟结点（25，30）够借，所以 15 的父结点下来，25变成父结点。

（更具体的原理分析，在基本概念的下方）

 注意一点，无论是插入还是删除操作，叶子结点（失败结点）要在同一层。

（2）基本概念：

B- 树，也称 B 树，其关键字数和子树数量等如下表，对比 B+ 树

m阶		B 树	B+ 树
关键字数	根结点	[1, m-1]	[1, m]
子树数量		[2, m]	非根叶结点至少 2 棵子树
关键字数	其他结点
子树数量			（分支结点）
n 个关键字对应		n + 1 个分叉（子树）	n 个分叉
叶子结点		失败结点，不含信息	带信息

拿个 B 树和 B+ 树的图示对比一下，应该都可以理解：

B 树删除结点操作：（比较复杂，大家看下图的王道讲解） 

七、排序算法的应用

可搭配以下链接进行学习，有直接插入排序、折半插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序等排序算法的详解，并附有408真题，配以图文进行详细解析。

【考研】数据结构九种内部排序算法考点链接分享-CSDN社区

1、序列 {24, 4,32, 55, 62, 18, 32*, 39, 13,35}，写出应用下列排序算法进行第一趟排序之后的序列状态。(10分)
(1) 直接插入排序
(2) 冒泡排序
(3) 快速排序
(4) 简单选择排序
(5) 二路归并排序

来源:北京大学869 2020年

解：第一趟排序之后的序列状态如下：（默认按元素递增进行排序）

(1) 直接插入排序：4，24，32，55，62，18，32*，39，13，35
(2) 冒泡排序：4，24，32，55，18，32*，39，13，35，62
(3) 快速排序：13，4，18，24，62，55，32*，39，32，35
(4) 简单选择排序：4，24，32，55，62，18，32*，39，13，35
(5) 二路归并排序：4，24，32，55，18，62，32*，39，13，35

【补充】针对快排，博主的思路是确定枢轴，从最右侧往左找比枢轴小的，从最左侧往右找比枢轴大的，并确定指针 low 与 high 的位置。简单列出如下图：

2、{6，5，4，3，2，1} 利用数组建成一个最小堆并使用堆排序将其排序成唯一的降序数组。要求画出所有中间过程。

来源:华中科技大学834 2017年

解：堆排序：

（1）大根堆：较小的关键字筛下去，较大的关键字筛上来。

（2）小根堆：较大的关键字筛下去，较小的关键字筛上来。

【步骤】

（1）建初堆，则按层序遍历排列成二叉树，因为要组成最小堆，即小根堆，则为调整堆。

（2）并将其排序成降序数组，则是依次将堆顶元素与待排序序列中最后一个元素交换位置，再将待排序序列调整为小根堆。反复重述上述操作，直到全部元素都已排好序。如下图所示：

3、假设已经有 k 个长度分别为 Mo,  M1,  Mk-1 的有序表，现通过两两合并的方式将它们合并为一个有序表，若要使合并过程中元素的总比较次数最小，应该按照什么次序进行合并？说明你的理由，必要时可以举例说明。 (8 分)

来源:四川大学874 2019年

解：长为 m 和 n 的两个有序表合并，最坏情况下，关键字比较次数为 m + n – 1次。

最坏情况下关键字对比次数依赖于两表的表长之和。因此每次合并时，应挑选表长最短的的两个有序表进行合并，直到最终合并为一个表为止。（类似哈夫曼树的思想）

【补充】

（1）假设有 9 个有序表，表长分别为 9，30，7，18，3，17，2，6，24。则哈夫曼树作为2-路归并树如下：

【注意】这题有些类似于最佳归并树。(可参考：最佳归并树详解 (biancheng.net))

为减少访问外存的次数的问题，就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。然后回归到：带权路径长度最短的二叉树为哈夫曼树。

（通过以构建哈夫曼树的方式构建归并树，使其对读写外存的次数降至最低（k-路平衡归并，需要选取合适的 k 值，构建哈夫曼树作为归并树）。所以称此归并树为最佳归并树。）

针对上图，其对外存的读写次数为：(2+3)*5 + (6+7+9)*4 + (17+18)*3 + (24+30)*2 = 1446

（2）可知，若要使合并过程中元素的总比较次数最大，则是在每次合并时，挑选表长最长的两个有序表进行合并，直到最终合并为一个表为止。