应用题打卡
数组的应用
对称矩阵的压缩存储
注意：
1.
2.上三角的行优先存储及下三角的列优先存储与数组的下表对应
上/下三角矩阵的压缩存储
注意：
上/下三角压缩存储是将0元素统一压缩存储，而不是将对角线元素统一压缩存储
三对角矩阵的压缩
栈、队列的应用
栈的定义和基本操作实现
①顺序栈
②链栈
③双向链栈
队列的定义和基本操作实现
①顺序存储的队列：注意队首尾指针进1的公式
②链式存储的队列：注意链式存储的队列出队操作
树的应用
二叉树的性质
知识点：
题目：
1.
2.
二叉树的顺序存储和基本操作
①注意二叉树的顺序存储的定义
②注意二叉树判空
数组下标从1开始存储
数组下标从0开始存储
树的性质
1.树的基本性质
5.1.4
1.
5.4.4
1.
2.
树/森林的定义和画图
①双亲表示法：森林也可以用树的双亲表示法
②孩子表示法
注：
③对比：树的孩子表示法存储 v.s. 图的邻接表存储 v.s. 散列表的拉链法 v.s. 基数排序。你发现了什么？
（1）孩子表示法
（2）图的邻接表存储
（3）散列表的拉链法
（4）基数排序
④自己动手创造，画一个结点总数不少于10的树/森林，并画出对应的“双亲表示法、孩子表示法、孩子兄弟表示法”三种数据结构的示意图
注意孩子兄弟表示法，是纯链表表示，不像孩子表示法是顺序存储+链式存储
哈夫曼树的应用
并查集的应用
3.5.1~3.5.3 实现并查集的数据结构定义，并实现 Union、Find 两个基本操作
并查操作优化：
3.5.4 设计一个例子，对10个元素 Union
记住Union操作是小树并大树，如果两个集合大小相等，则右边并入左边的树
3.5.5 基于上述例子，进行若干次 Find，并完成“压缩路径”
二叉排序树、平衡二叉树的应用题潜在考法
①计算ASL（注意需要除以结点个数）
②二叉排序树的删除
注意结点z如果只有一棵左子树或右子树，则直接让z的子树称为z父结点的子树，替代z的位置
③自己设计一个例子，给出不少于10个关键字序列，按顺序插入一棵初始为空的平衡二叉树，画出每一次插入后的样子（你设计的例子要涵盖LL、RR、LR、RL四种调整平衡的情况）
例：从一棵初始为空的AVL Trees 开始，依次插入：50、26、10（LL）、3、5（LR）、60、90（RR）、40、55、100、59（RL）
最后插入59
二叉平衡树的插入：
总结：
LL单旋：如果A结点的平衡因子绝对值大于1，就将A结点左子树根结点右旋
RR单旋：如果A结点的平衡因子绝对值大于1，就将A结点右子树根结点左旋
LR单旋：如果A结点的平衡因子绝对值大于1，就将A结点左孩子的右子树根结点先左旋再右旋
RL单旋：如果A结点的平衡因子绝对值大于1，就将A结点右孩子的左子树根结点先右旋再左旋
图的应用
图的性质
1.
2.
3.
4.
5.
图的数据结构定义
①顺序存储和链式存储的图
②带权无向图和带权有向图的邻接矩阵和邻接表表示
图的应用：最小生成树
①
②prim算法和kruskal算法
图的应用：最短路径
图的应用：拓扑排序
图的应用：关键路径
略
查找算法
分块查找
折半查找
略
散列查找
线性再探法
散列表计算，ASL成功的分母是元素总个数，ASL失败的分母是mod的那个数
来自群u的解答：
拉链法
排序算法
希尔排序
堆排序
建堆规则：
自己设计一个长度不小于10的乱序数组，用堆排序，最终要生成升序数组，画出建堆后的状态
假设乱序数组的初始状态如下，元素从0开始存储????：
若顺序二叉树从数组下标1开始存储结点，则：
● 结点 i 的父结点编号为 i/2
● 结点 i 的左孩子编号为 i*2
● 结点 i 的右孩子编号为 i*2+1
若顺序二叉树从数组下标0开始存储结点，则：
● 结点 i 的父结点编号为 [(i+1)/2] - 1
● 结点 i 的左孩子编号为 [(i+1)*2] - 1 = 2*i + 1
● 结点 i 的右孩子编号为 [(i+1)*2+1] - 1 = 2*i + 2
在本例中，元素从数组下标0开始存储，因此，0号元素是根节点，1号元素是其左孩子，2号元素是其右孩子。其他元素间的关系如下：
由于最终要生成升序数组，因此需要建立大根堆，从最后一个分支（即6号结点）开始调整，即依次调整结点 6、5、4、3、2、1、0。建立好的大根堆如下：
注：如果应用题让你画出一个乱序数组建堆后的样子，只需要画出数组形式的图示即可，不用画二叉树形态的图示。如下????
画出每一轮堆排序的状态
快速排序
自己设计一个长度不小于10的乱序数组，用快速排序，最终要生成升序数组
画出每一轮快速排序的状态
基数排序
略
外部排序
置换选择算法
“外部排序”在历年真题中的考频不算高，因此许多考生并不重视对该考点的复习。但是2023年应用题突然深入考察了“外部排序”，让广大考生感到被偷袭，猝不及防。因此，我们需要重视这个考点。以下是历年真题中，涉及到“外部排序”的题目：
【2016年真题11题】（选择题）考察了“外部排序的思想”
【2019年真题11题】（选择题）考察了“最佳归并树”
【2023年真题42题】（应用题）考察了“置换-选择排序”
【2024年真题11题】（选择题）考察了“败者树”
接下来，我们将2023年真题进行改编，用于回顾外部排序的三个重要考点：①置换-选择排序，②最佳归并树，③败者树
对含有19个记录的文件进行外部排序，其关键字依次是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100。假设每个文件记录刚好占一个磁盘块。请回答下列问题：
1）若采用置换-选择排序生成初始归并段，工作区中能保存3 个记录，可生成几个初始归并段？各是什么？请问置换-选择排序的过程中，读、写磁盘次数分别是几次？
2）若要对几个初始归并段进行3路归并，为实现最佳归并，需要补充的虚段个数是多少？请画出最佳归并树的样子，并计算该归并树的WPL。请问归并过程中，读、写磁盘次数分别是多少次？磁盘I/O次数是多少次？
3）若要对几个初始归并段进行4路归并，为减少归并过程中关键字对比次数，需使用“败者树”。请问构造初始败者树时，需要对比几次关键字？基于构造好的败者树，每次从4个归并段中找到最小关键字所需的关键字对比次数是多少？
1）
排序过程如下表所示：
| 输出文件FO |
工作区WA |
输入文件FI |
| — |
— |
51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| — |
51, 94, 37 |
92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37 |
51, 94, 92 |
14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51 |
14, 94, 92 |
63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 92 |
14, 94, 63 |
15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 92, 94 |
14, 15, 63 |
99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 92, 94# |
14, 15, 63 |
99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 14 |
99, 15, 63 |
48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 14, 15 |
99, 48, 63 |
56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 14, 15, 48 |
99, 56, 63 |
23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 14, 15, 48, 56 |
99, 23, 63 |
60, 31, 17, 43, 8, 90, 166, 100 |
| 14, 15, 48, 56, 63 |
99, 23, 60 |
31, 17, 43, 8, 90, 166, 100 |
| 14, 15, 48, 56, 63, 99 |
31, 23, 60 |
17, 43, 8, 90, 166, 100 |
| 14, 15, 48, 56, 63, 99# |
31, 23, 60 |
17, 43, 8, 90, 166, 100 |
| 23 |
31, 17, 60 |
43, 8, 90, 166, 100 |
| 23, 31 |
43, 17, 60 |
8, 90, 166, 100 |
| 23, 31, 43 |
8, 17, 60 |
90, 166, 100 |
| 23, 31, 43, 60 |
8, 17, 90 |
166, 100 |
| 23, 31, 43, 60, 90 |
8, 17, 166 |
100 |
| 23, 31, 43, 60, 90, 166 |
8, 17, 100 |
— |
| 23, 31, 43, 60, 90, 166# |
8, 17, 100 |
— |
| 8 |
17, 100 |
— |
| 8, 17 |
100 |
— |
| 8, 17, 100 |
— |
— |
| 8, 17, 100# |
— |
— |
可生成4个归并段，分别是：
37, 51, 92, 94
14, 15, 48, 56, 63, 99
23, 31, 43, 60, 90, 166
8, 17, 100
置换-选择排序的过程中，需要读磁盘19次，写磁盘19次。因为19条文件记录（即上表所示的“输入文件FI”）初始时存储在磁盘，每条记录占一个磁盘块，进行置换-选择排序时，这19条记录需要依次读入内存中（即上表所示的“工作区WA”），再逐一写回外存（即上表所示的“输出文件FO”）。因此，整个过程需要读磁盘19次，写磁盘19次。
最佳归并树练习
2）
回顾“最佳归并树”的构造方法：
本题中，有4个初始归并段，进行3路归并，因此需要构造 3叉最佳归并树。
(初始归并段数量-1) % (k-1) = (4-1)%(3-1)=1≠0，因此需要补充 (k-1)-u = (3-1)-1=1 个虚段。
补充1个虚段后，各初始归并段的长度为：
37, 51, 92, 94——归并段①长度为4
14, 15, 48, 56, 63, 99——归并段②长度为6
23, 31, 43, 60, 90, 166——归并段③长度为6
8, 17, 100——归并段④长度为3
NULL ——归并段⑤为虚段，长度为0
最佳归并树形态如下：
WPL = 树中所有叶节点的带全路径之和 = (0+3+4)*2 + (6+6)*1 = 26
注：最佳归并树形态不唯一，但WPL一定是 26
归并过程中，读磁盘次数=WPL=26次