德州市建设局质监站网站,河南郑州新闻,崇州市微信端网站建,wordpress 固定链接结构出错应用题打卡
数组的应用
对称矩阵的压缩存储 注意#xff1a;
1. 2.上三角的行优先存储及下三角的列优先存储与数组的下表对应 上/下三角矩阵的压缩存储 注意#xff1a;
上/下三角压缩存储是将0元素统一压缩存储#xff0c;而不是将对角线元素统一压缩存储 三对角矩阵的…应用题打卡
数组的应用
对称矩阵的压缩存储 注意
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、10LL、3、5LR、60、90RR、40、55、100、59RL 最后插入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*21 若顺序二叉树从数组下标0开始存储结点则 ● 结点 i 的父结点编号为 [(i1)/2] - 1 ● 结点 i 的左孩子编号为 [(i1)*2] - 1 2*i 1 ● 结点 i 的右孩子编号为 [(i1)*21] - 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)-11 个虚段。 补充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 树中所有叶节点的带全路径之和 (034)*2 (66)*1 26 注最佳归并树形态不唯一但WPL一定是 26 归并过程中读磁盘次数WPL26次 写磁盘次数WPL26次 磁盘I/O总次数WPL*252次。 注每个记录刚好占一个磁盘块因此每读一个记录就需要一次读磁盘每写一个记录就需要一次写磁盘。 在进行第一趟归并时需要三个归并段中的记录依次读入磁盘、再按归并顺序依次写回磁盘。因此第一趟归并带来了 0347 次读磁盘、以及7次写磁盘。 在进行第二趟归并时需要将三个归并段中的记录依次读入磁盘、再按归并顺序依次写回磁盘因此第二趟归并带来了 766 19 次读、以及19次写。 综上经过两趟归并读磁盘次数 71926次写磁盘次数71926次。 最佳败者树 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个归并段中的最小关键字。如下所示 至此应用题打卡结束
