【数据结构强化】应用题打卡

应用题打卡

数组的应用

对称矩阵的压缩存储

注意：

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次

写磁盘次数=WPL=26次

磁盘I/O总次数=WPL*2=52次。

注：每个记录刚好占一个磁盘块，因此每读一个记录就需要一次读磁盘，每写一个记录就需要一次写磁盘。

在进行第一趟归并时，需要三个归并段中的记录依次读入磁盘、再按归并顺序依次写回磁盘。因此第一趟归并带来了 0+3+4=7 次读磁盘、以及7次写磁盘。

在进行第二趟归并时，需要将三个归并段中的记录依次读入磁盘、再按归并顺序依次写回磁盘，因此第二趟归并带来了 7+6+6 = 19 次读、以及19次写。

综上，经过两趟归并，读磁盘次数 = 7+19=26次，写磁盘次数=7+19=26次。

最佳败者树

3）

本题要求构造4路归并的败者树，因此需要对比关键字 3 次。

注：三次关键字对比如图下所示

首先分别取出4个初始归并段中的最小值，用于构造初始败者树。

第一次关键字对比：将关键字8、37进行对比。37更大，为“失败者”；8更小，为“胜利者”，晋级至下一轮对比。

第二次关键字对比：将关键字14、23进行对比。23更大，为“失败者”；14更小，为“胜利者”，晋级至下一轮对比。

第三次关键字对比：将上一层的两个“胜利者”，即关键字8、14进行对比。14更大，为“失败者”；8更小，为最终“胜利者”，也就找到了最小元素。

基于构造好的败者树，每次从4个归并段中找到最小关键字所需的关键字对比次数是2次。

举个例子，在初始败者树构造完成后，可知4个归并段中，最小元素为8（来自于最左边一个归并段）。

接下来，基于已经构造好的败者树，要继续找到剩余元素中的最小关键字，仅需进行两次关键字对比。

第一次关键字对比：将关键字17、37进行对比。37更大，为“失败者”；17更小，为“胜利者”，晋级至下一轮对比。

第二次关键字对比：将关键字14、17进行对比。17更大，为“失败者”；14更小，为最终“胜利者”，也就找到了最小元素。

注：

咸鱼认为，如果考题中考到败者树，最有可能的三个出题角度是：

①问你败者树的作用

②构造k路归并的败者树时，关键字对比次数是多少？

③基于构造好的败者树，每次从k个归并段中找到最小关键字，至多/至少需要对比关键字多少次？

下面对着三个问题进行总结：

①败者树的作用是：在进行多路归并时，减少关键字对比次数。

②构造k路归并的败者树时，需要对比关键字 k-1 次。

例如：构造7路归并的败者树时，需要对比关键字6次。

③基于构造好的败者树，每次从k个归并段中找到最小关键字 所需的关键字对比次数，取决于败者树的高度和形态。万一考到这类问题，可以先画出败者树的形态，再来分析。

k路归并的败者树，形态上是一棵具有 k 个叶子结点的完全二叉树。

例如：7路归并的败者树形态如下

总共有7个叶子结点，每个叶子对应一个归并段。

基于这棵构造好的败者树，从7个归并段中找到最小关键字，最多需要3次关键字对比；最少需要2次关键字对比。

如果本轮新关键字来自于归并段1，则只需要2次关键字对比即可找到7个归并段中的最小关键字。如下所示：

如果本轮新关键字来自于归并段2，则需要3次关键字对比才能找到7个归并段中的最小关键字。如下所示：

至此，应用题打卡结束