民族文化网站建设的作用,WordPress和微信公众号,网站开发流程详细步骤,浙江绿建设计院网站文章目录 1.树相关应用大题1.1 已知二叉树的中序序列和前序or中序#xff0c;画出二叉树1.2 二叉树的遍历、树的遍历、森林的遍历总结1.3二叉树与森林之间的转换1.3.1 已知树的先序序列和中序序列#xff0c;画出森林 1.4 二叉树的线索化1.5 二叉排序树1.5.1 二叉排序树的删除… 文章目录 1.树相关应用大题1.1 已知二叉树的中序序列和前序or中序画出二叉树1.2 二叉树的遍历、树的遍历、森林的遍历总结1.3二叉树与森林之间的转换1.3.1 已知树的先序序列和中序序列画出森林 1.4 二叉树的线索化1.5 二叉排序树1.5.1 二叉排序树的删除(重点)1.5.2 二叉排序树的ASL成功与ASL失败 1.6 平衡二叉树1.6.1 平衡因子1.6.2 平衡二叉树的构建(插入) 2.哈希函数2.1 拉链法求平均成功查找长度与查找失败长度2.2 开发地址法之线性探测法求平均成功查找长度与查找失败长度2.3 开发地址法之平方探测法求平均成功查找长度 3.图的相关应用题3.1 根据图画邻接矩阵与邻接表(根据邻接矩阵与邻接表)3.1.1 画邻接矩阵3.1.2 画邻接表 3.2 求图的强联通分量3.3 深度优先生成树与广度优先生成树3.4 哈夫曼树与哈夫曼编码3.4.1 哈夫曼树WPL3.4.2 构造哈夫曼树 3.5 最小生成树3.5.1 prim算法3.5.2 克鲁斯卡尔算法 3.6 最短路径3.6.1 迪杰斯特拉算法 3.7 关键路径 4.排序4.1 快速排序4.2 堆排序4.3 希尔排序4.4 归并排序4.5 基数排序 本篇文章的目的是梳理一遍数据结构中容易出应用题的地方整理成一个模版。 1.树相关应用大题
1.1 已知二叉树的中序序列和前序or中序画出二叉树 1.2 二叉树的遍历、树的遍历、森林的遍历总结
二叉树的遍历分三种不再赘述。树的遍历分两种先根遍历后根遍历 树的先根遍历序列二叉树的先序遍历树的后根遍历序列二叉树的中序遍历 森林的遍历分两种先序遍历森林中序遍历森林 先序遍历森林对各个树进行先根遍历后序遍历森林对各个树进行后根遍历
1.3二叉树与森林之间的转换 孩子兄弟表示法 1.3.1 已知树的先序序列和中序序列画出森林 点睛树是二叉树孩子兄弟表示法森林可不是二叉的就是普通的 1.4 二叉树的线索化 主要是将二叉树线索化成前序线索二叉树和后序线索二叉树 做题思路: 1.写出二叉树的前序序列或后序序列 2.填充根据第一步写出的序列比较着将空闲的左子树指向前驱。将空闲的右子树指向后继。
1.5 二叉排序树 1.5.1 二叉排序树的删除(重点)
二叉排序树根据删除结点的情况可分为三种情况
先搜索找到目标结点 1️⃣若被删除结点z是叶结点则直接删除不会破坏二叉排序树的性质。 2️⃣若被删除的结点只有左子树或右子树直接让它的那个子树代替它的位置即可 3️⃣被删除的结点既有左子树又有右子树
从左子树找到最大的结点代替它的位置(即左子树最右下的结点从右子树找到最小的结点代替它的位置(即右子树最左下的结点 1.5.2 二叉排序树的ASL成功与ASL失败 左图计算平均查找成功ASL右图计算平均失败查找长度 查找成功 (查询次数✖️同等查询次数结点数)➗结点总数 ASL1*12*23*44*1/82.625 查找失败 (判断出是空子树需要的查找次数*这种情况的数量)/情况数 ASL3*74*2/93.22 注意空子树判断到它的父结点即可意味着第四的空子树判断次数是三。 注意ASL成功每一个结点都要判断ASL失败每一个空子树都要判断。
1.6 平衡二叉树
平衡二叉树是一种特殊的二叉排序树
1.6.1 平衡因子
为了方便起见给树上的每个结点附加一个数字给出该结点左子树与右子树的高度差这个数字称为结点的平衡因子BF
平衡因子结点左子树的高度-结点右子树的高度。
因此平衡二叉树所有结点的平衡因子只能是-1、0、1如下图是一个平衡二叉树
1.6.2 平衡二叉树的构建(插入)
根据插入位置不同分为四种类型
LL(插入在左孩子的左子树RR(插入在右孩子的右子树LR(插入在左孩子的右子树RL(插入在右孩子的左子树 为什么假定所有子树的高度都是H 如何调整最小不平衡子树(笔试过程中如何调整平衡二叉树 方法提炼:从下往上寻找到不平衡的结点然后以该结点出发往下再找两个结点这个就是它局部最小的不平衡然后调整根节点三个数找中间的数为新的根节点把它调整其他的结点按照二叉排序树的规则填好就行。 真题 1.已知关键字序列221213892033424438244860画出对应的平衡二叉树
2.哈希函数
2.1 拉链法求平均成功查找长度与查找失败长度
ASL成功要横着看一次查找到的结点数2*两次的查到的结点数…n*n次查到的结点数/表中所有的结点数
ASL失败表中所有的结点数/mod的数 解释说明上面给出的ASL失败只是一种数值相等的公式并不是理解。 拉链法中空指针算0次比较所以拉链法在每一种查找失败的情况就是该条链下结点的个数mod的数就是情况数比如mod7会得到0-67种情况。 例题如下: 【1999年 9分】
2.2 开发地址法之线性探测法求平均成功查找长度与查找失败长度 重点讲解 1.当用哈希函数算完之后使用线性探测的时候要注意分母变成了表长不是哈希函数中的modx中的x并且使用结果是上一步中哈希函数的结果比如算完46%112假设表长为13线性探测就是21%13而不是461%13也不是21%11这都是值得注意的。 2.在计算平均查找失败长度的过程中每一次的情况是遇到空的时候就停止。 分母是映射空间哈希函数是mod7地址空间就是0-67种情况从为0的情况出发一直加到6的情况 3.查找成功就是比较次数这里不多说了 例题1:
例题2: 注意计算ASL失败的时候看的是映射空间 0-10 11种情况地址为11的时候不计算ASL失败 例题3(手把手分析ASL失败和ASL成功) 分析 ASL成功分母是关键字的数目分子就是插入过程中的比较次数 ASL失败分母是情况数mod取余13那就是13种情况即0-12地址。 分子就是从当前地址出发(当前地址算比较一次)找到下一个空白块的比较次数假如地址到头没找到就按照计算的hash函数12没找到就从0找1…2…3 2.3 开发地址法之平方探测法求平均成功查找长度 根据题目给出的Hi函数来具体进行平方探测法的计算本质和线性探测是一回事 注意线性探测平方法是1-14-49-9 别算错了 例题1:
3.图的相关应用题
3.1 根据图画邻接矩阵与邻接表(根据邻接矩阵与邻接表)
3.1.1 画邻接矩阵 3.1.2 画邻接表
不带权的情况
带权的情况规范的画法是表结点中权值在前连接的序号在后
3.2 求图的强联通分量
如何写出一个图中的所有强连通分量 写出一个图中的所有强连通分量
3.3 深度优先生成树与广度优先生成树 本质上就是去掉多余的边 3.4 哈夫曼树与哈夫曼编码
3.4.1 哈夫曼树WPL
带权路径长度WPL是指树中所有叶子结点的带权路径长度之和。具体来说每个叶子结点的权值与其到根结点的路径长度即经过的边数的乘积称为该叶子结点的带权路径长度。所有叶子结点的带权路径长度之和即为该树的带权路径长度。 图一4个2条边的叶子结点 图二2个3条边的叶子结点1个2条边的叶子结点1个1条边的叶子结点 图三2个3条边的叶子结点1个2条边的叶子结点1个1条边的叶子结点 图四2个3条边的叶子结点1个2条边的叶子结点1个1条边的叶子结点 乘上对应的权值
3.4.2 构造哈夫曼树
构造步骤 1️⃣ 找到当前权值最小的两个结点包括两个结点构造出的新结点 2️⃣ 将这两个结点通过一个构造出的父结点联系起来父结点的权值是他俩权值之和。 3️⃣重复上面的步骤直到没有结点可以添加
3.5 最小生成树
3.5.1 prim算法
核心加入点加入的点和之前加入的点看成一个整体 从某一个顶点出发每次将代价(权值)最小的新顶点加入到点集中记录他们之间的连接边从这个点集出发循环上面的过程将新结点加入直到所有结点都加入进点集中。
时间复杂度O|v|2,适用于边稠密图
例题
3.5.2 克鲁斯卡尔算法
核心加入边
每次选择代价最小的边让这条边的两头连通(原本已经连通的不选)直到所有结点都连通。 时间复杂度O|E|log2|E|,适用于边稀疏图
3.6 最短路径
3.6.1 迪杰斯特拉算法
理论方法学习:迪杰斯特拉算法求最短路径
例题1:给出一个无向图从A出发用迪杰斯特拉算法写出到达每个顶点的最短路径 3.7 关键路径
解题思路 拓扑排序决定了事件最早的发生的顺序 逆拓扑排序决定了事件最晚发生的顺序
起点和终点的事件最早发生时间和事件最晚发生时间相同。
做题逻辑顺序 1.写出拓扑排序和逆拓扑排序 2.由拓扑排序写出事件的发生顺序开始算事件最早发生时间。起点的最早发生时间是0从这开始写。下一个事件的最早发生事件看前面的事件最长的活动时间(就是最晚)到达下一个事件的时间就是算事件最早发生时间以此类推。总结就是**从前往后找最大** 3.从逆拓扑排序开始写事件的最晚发生事件由起点和终点的事件最晚发生时间相同开写看看前面最短的活动时间前面事件的最早开始事件-最短的活动时间总结就是从后往前找最小 4.活动最早的开始时间就是活动弧尾指向事件的最早发生事件 5.活动最晚的开始时间是活动弧头指向事件的最晚发生时间-活动时间
大总结小口诀 事件时间起手求从前往后找最大从后往前找最大 活动时间用箭头最早弧尾最晚弧头减活动。 注意 终点事件的最晚发生时间就是关键路径长度 事件最早发生时间和最晚发生时间相同的事件就是关键事件 活动时间差值为0的活动就是关键路径它的路径就是关键路径 多路径事件最早发生时间选最长的 多路径事件最晚发生时间选最短的 活动最早发生时间—弧尾顶点最早发生时间 活动最晚发生时间----弧头顶点最迟发生时间-权值 弧头有箭头弧尾没箭头 事件时间整体算就是每次以起点或者终点找路径计算。 例题2:
4.排序
4.1 快速排序
真题1: 真题2: 4.2 堆排序 4.3 希尔排序 4.4 归并排序
算法思想 把两个或多个已经有序的序列合并成一个序列合并的过程就是两个有序序列依次对比把更小(或更大的拿出来合并。
算法流程 以二路归并为例
从每一个元素都是一个队列开始都是一个独立的有序序列相邻两个元素合并成一个在排好序以此类推不断将相邻的两个有序序列合并并排好序直到就剩一个有序序列为止。
4.5 基数排序
0到9写标号 升序从左往右收集。将序从右往左收集。 整体都是从上到下收集
题目来源:计算机2018年真题