网站空间可以自己做服务器张店网站建设yx718

当前位置： 首页 > news >正文

网站空间可以自己做服务器,张店网站建设yx718,网站建设 技术要求,旅游景点网站模板【征服数据结构】#xff1a;期末通关秘籍 #x1f498; 数据结构的基本概念#x1f608; 数据结构的基本概念#x1f608; 逻辑结构和存储结构的区别和联系#x1f608; 算法及其特性#x1f608; 简答题 #x1f498; 线性表#xff08;链表、单链表#xff09;期末通关秘籍 数据结构的基本概念 数据结构的基本概念 逻辑结构和存储结构的区别和联系 算法及其特性 简答题 线性表链表、单链表 大题1❄️ 题目解析❄️ 算法思想和时间复杂度❄️ 代码实现❄️ 某搜题软件上的答案 大题2❄️ 答案解析 栈和队列 大题1❄️ 题目分析❄️ 答案解析❄️ 标准答案取自某搜题软件 简答题1 简答题2 树 二叉树的定义、性质和应用 二叉树的先序、中序遍历和后序遍历 已知遍历序列构造二叉树❄️ 大题1 二叉树如何转换成森林 二叉树如何转换成树 将二叉树如何转换成森林 标准答案出自某搜题软件 ❄️ 大题2 答案解析 标准答案 ❄️ 大题3 答案 标准答案 ❄️ 简答题1 标准答案 ❄️ 简答题2 标准答案 ❄️ 简答题3 答案解析 标准答案 森林的先序遍历和中序遍历可能出选择题 树转化为二叉树以及森林转化成二叉树 哈夫曼树和哈弗曼编码这里肯定会出大题 大题1❄️ 答案解析 线索二叉树 图 图的连通性问题 出度和入度 带权无向图的最小生成树Prim、KrusKal算法 有向无环图、拓扑排序 大题1❄️ 答案解析 大题2❄️ 标准答案 关键路径和关键活动❄️ 大题2 答案解析 标准答案 图的遍历广度优先和深度优先 最短路径❄️ 大题3 答案解析 标准答案 查找 静态查找表顺序查找、折半查找❄️ 大题1 答案解析 标准答案 动态查找表: 二叉排序树、二叉平衡树、m阶B树❄️ 二叉排序树❄️ 二叉平衡树❄️ 大题1 答案解析 标准答案 B树❄️ 大题2 答案解析 哈希表❄️ 哈希表的长度、哈希表的装填因子等❄️ 常用的构造哈希函数的方法❄️ 处理冲突的方法❄️ 大题3 答案解析 前言本篇博客只做博主复习使用不做其它若有问题也欢迎大家留言反馈。所有例题均为ZZULI往年期末题正当途径获得。最后一章排序章节较简单博主没有单独列出。 参考鸣谢 AVL树的插入操作旋转图解 MaxBruce 解决Hash哈希表冲突的四种方案 FrozenPenguin 图——关键路径 傅华涛Fu 拓扑排序详解 Dream of maid 生成树基础) 莫忘、莫念 图的连通性问题 _Tham 数据结构】树、二叉树和森林的相互转换 JackyFeng 【专题】树和森林的遍历 ᝰꫛꪮꪮꫜ hm 数据结构的基本概念 数据结构的基本概念 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。—选自百度百科 逻辑结构和存储结构的区别和联系 算法及其特性 简答题 2) 3) 线性表链表、单链表 顺序存储结构及其基本操作请看博主这篇博客。 链式存储结构及其基本操作请看博主这篇博客 大题1 ❄️ 题目解析 ❄️ 算法思想和时间复杂度 题目说了需要我们释放结点的空间。 首先创建两个结点指针变量precur让pre初始化为Headcur初始化为Head-next开始遍历带头单链表,分为两种情况 如果pre指针的数据域和cur指针的数据域相等那我们就删除掉cur指针指向的结点释放结点空间后完成链接即可删除cur之前保存cur-next给变量next,删除完之后更新cur为nextpre不用更新因为当前的值还可能和pre的数据域相等。如果pre指针的数据域和cur指针的数据域不相等更新这两个指针pre更新为curcur更新为cur-next。 最后cur结点指针指向NULL循环结束。 时间复杂度是 O ( l o g N ) O(logN) O(logN)。 ❄️ 代码实现 void remove(LinkList Head) {LinkList pre Head;//前一个结点指针LinkList cur Head-next;//后一个结点指针while (cur ! NULL){if (pre-data ! cur-data)//如果pre和cur的data不相等{pre cur;cur cur-next;}else//如果pre和cur的data相等{//先删除掉cur结点LinkList node cur-next;//保存cur-next指针结点free(cur);//释放结点空间pre-next node;//链接cur node;//更新cur指针}} }❄️ 某搜题软件上的答案 大题2 ❄️ 答案解析 在写代码前我们还是画图来分析以下删除链表结点是如何删除的 代码示例(C语言实现) LinkList deleteodd(LinkList L) {LinkList pre L;//pre是当前遍历位置的前一个结点指针LinkList cur L-next;//cur变量是当前遍历位置的结点指针while (cur ! NULL)//cur为空就停止循环{if (cur-data % 2 0)//如果当前结点指针指向的结点的数据域是偶数,正常更新{pre cur;cur cur-next;}else//否则就删除当前结点{//先保存当前结点的下一个结点指针防止将当前结点释放后无法找到下一个结点的指针LinkList next cur-next;free(cur);pre-next next;//更新pre的nextcur next;//更新cur}}return L;//返回头节点 }栈和队列 栈和队列的基本特征栈里面的数据后进先出。队列里的数据先进先出。 它们的逻辑结构都是线性结构。可以用线性表或者单链表来实现。详细请看博主这篇博客 栈和队列作为线性结构中比较典型的两个结构应用多是很可能出一道大题的下面我们来看一道大题ZZULI往年期末题 大题1 ❄️ 题目分析 上图忘记说明一点了终态不为空也不叫满足要求需要返回false。 ❄️ 答案解析 2. 代码实现 bool is_valid(char* s) {int cnt_i 0;//统计入栈的次数int cnt_o 0;//统计出栈的次数int i 0;while (s[i] ! \0){if (s[i] O)cnt_o;elsecnt_i;if (cnt_i cnt_o){std::cout 序列非法“ std::endl;//用printf打印也可以return false; }i;}if (cnt_i cnt_o){std::cout 序列非法“ std::endl;//用printf打印也可以return false;}std::cout 序列合法 std::endl;return true; }上述代码应该是C语言实现因为C语言中没有bool这个类型。打印处使用printf也可以因为c语言兼容C语言。 ❄️ 标准答案取自某搜题软件 简答题1 题目让我们描述栈和队列的逻辑结构和特性并分别举出两个应用实例。 栈和队列的逻辑结构都是线性结构栈具有后进先出的特性意思是后面入栈的元素在进行出栈操作时会先出去。 队列具有先进先出的特性意思是先入队列的元素在进行出队列操作时会先出去。 应用示例栈递归、后缀表达式求值。队列二叉树的层次遍历、图的广度优先搜索。 简答题2 首先来回答第一个问题 什么是循环队列 循环队列是队列的一种普通的队列如果采用数组的方式存储的话为了不挪动数据删除队列元素时我们可能会直接将队列首元素的下标后移这样就会造成一个问题就是队列的空间在减少继续入队列尾插如果数组的空间满了这个时候如果进行过出队列就会造成队列的元素小于数组实际的大小的情况。循环队列就是为了解决这种问题让空间的利用大大提高。我们只需要把一个数组逻辑上想象成首尾相接即可。 用文字描述可能很抽象我们画图来解释 其次就是循环队列的判空和判满问题。 先说结论 front rear时为空 (rear1)%n front时为满n为数组的大小。我们画图来分析一下为什么是这样:
贴一个 标准答案 在顺序队列中由于数组空间不够而产生的溢出叫真溢出顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进入队列操作的溢出称为假溢出。 假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的。其解决办法有二一是将队列元素向前“平移”(占用0至rearfront1)二是将队列看成首尾相连即循环队列[0…m1]。在循环队列下仍定义。frontrear时为队空而判断队满则用两种办法: 一是用“牺牲一个单元”即rear1front(准确记是(rear1)mfrontm是队列容量)时为队满。 另一种解法是“设标记”方法如设标记tag,tag等于0的情况下若删除时导致fronttear为队空tag1的情况下若因插入导致frontrear则为队满。 树 如果你对二叉树什么都不了解可以看博主这篇博客 二叉树的定义、性质和应用 定义 二叉树是一种特殊的树它的每个结点至多有两个子树它的子树是有顺序的即使一个结点只有一个子树你也要指明是左子树还是右子树。
2性质 3应用 二叉树的先序、中序遍历和后序遍历 这里在上述博客链接里面的文章里我们也有详细的叙述这里我们在简单的画图叙述一下 已知遍历序列构造二叉树 一般都是给一个中序遍历序列、后序和前序遍历序列给一个让你构造二叉树。 中序遍历序列的作用是划分某个结点的左子树和右子树。 后序或者前序遍历序列的作用是确定当前根结点。 ❄️ 大题1 我们通过题目来讲解 二叉树如何转换成森林 二叉树如何转换成树 要学会二叉树转换成森林我们首先要学会将一棵二叉树转化成树。 我们画图来详细说明其步骤 将二叉树如何转换成森林 很简单一共有两步 删除当前二叉树根节点与其右孩子结点的连线使其独立成一个新的二叉树然后看这个新的二叉树有没有右孩子结点如果有继续删除连线。将上述独立出来的所有二叉树都转化为树。 下面我们演示一下我们本题二叉树转化为森林的过程 标准答案出自某搜题软件 ❄️ 大题2 答案解析 本题看着没有什么头绪只要让根结点存运算符然后得到它的左子树和右子树求得的值(后序遍历)然后做运算即可得到整个表达式的值。 代码: typedef int DataType;typedef struct node {DataType data;//存储数据char op;//存储运算符可能有些结点只有运算符或者只有数据struct node* left;struct node* right; }*Pnode;float PostOrder(Pnode root)//假设对于是值的结点其运算符是一个特殊符号 {if (!root)//如果root为空return 0;float left_val, right_val 0;//创建两个临时变量用来保存左边子树和右边子树的值float val root-data;//返回值,如果当前结点没有左子树和右子树就证明其应该是一个值而不是运算符left_val PostOrder(root-left);//先去得到左边子树的值right_val PostOrder(root-right);//再得到右边子树的值switch (root-op){case :val left_val right_val;break;case -:val left_val - right_val;break;case *:val left_val * right_val;break;case /: val left_val / right_val;break;default: break;//如果这个}return val;//返回结果 }标准答案 ❄️ 大题3 答案 此题和上面一道有重复我们熟练之后可 以不用那么详细照着先序遍历序列和中序遍历序列直接画出二叉树即可就是要注意不要看错了。 标准答案 ❄️ 简答题1 标准答案 ❄️ 简答题2 答案 链域就是指针域每个结点有四个指针域。 标准答案 ❄️ 简答题3 答案解析 标准答案 标准答案的边界值对应下图两种情况 森林的先序遍历和中序遍历可能出选择题 考的不多不需要作为重点重点应该放在二叉树的遍历上。 树转化为二叉树以及森林转化成二叉树 我们前面以及介绍过了将二叉树转化成树和将二叉树转化成森林现在我们来介绍一下将树转化成二叉树以及将森林转化成二叉树 将树转化成二叉树 2. 将一棵森林转变成二叉树 哈夫曼树和哈弗曼编码这里肯定会出大题 知识点 大题1 这种题比较简单基本上掌握一下基本套路就完事了。 ❄️ 答案解析 线索二叉树 线索二叉树就是将一个二叉树线索化的过程。 二叉树中有些左指针和右指针是空的我们线索化的时候可以把它们利用起来。 无论是前序遍历中序遍历还是后序遍历如果一个节点没有左子树就让他的左指针指向他的前驱节点前面一个要访问的结点如果一个节点没有右子树就让他的右指针指向他的后继节点后面一个要访问的结点。比较简单我们不再举例子。 图 图的连通性问题 出度和入度 出度某个顶点指向的顶点有几个它的出度就是几。 入度某个顶点被多少个顶点指向它的入度就是几。 带权无向图的最小生成树Prim、KrusKal算法 这两个算法都可以求最小生成树我们只介绍Prim算法。 生成树首先只有连通图才有生成树。生成树是所有顶点都连接在一起但不存在回路的图。因为树就是不存在回路的。 最小生成树所有生成树中使得各边权值总和最小的那棵生成树叫做最小生成树。 Prim算法的原理从某一个顶点开始构建生成树每次将代价最小到原先的生成树权值 最小的顶点加入这个生成树中构成新的生成树。(后面我们会用具体的题目来演示) KrusKal算法的原理Prime算法更倾向于点之间的关系所以又叫做加点法。而KrusKal算法更倾向于边它先将所有边按照权值的大小升序排列然后依次按照边权值的大小开始建立最小生成树如果加入当前权值最小的边时会导致出现回路就舍弃知道我们加入了n-1条边为止。 有向无环图、拓扑排序 在图论中如果一个有向图无法从某个顶点出发经过若干条边回到该点则这个图是一个有向无环图DAG图。 拓扑排序的定义 在有向无环图中我们将全部活动顶点和边的关系排列成一个线性序列使得这个图中中有弧i,j存在 则在这个序列中i 一定排在j的前面 具有这种线性序列称为拓扑有序序列相应的拓扑有序排序的算法称为拓扑排序。 拓扑排序的方法 大题1 下面题目涉及拓扑序列和最小生成树的构建比较重要一定得掌握 ❄️ 答案解析 大题2 1G1最多有n-1n-2n-3…1 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2。G1最少有n-1条边不成环但是连通。 (2)和3 ❄️ 标准答案 关键路径和关键活动 关键路径这块的概念比较多。 AOE网在一个表示工程的带权有向图中顶点表示事件用边来表示活动边上的权值叫做活动持续的时间这个有向图就是活动的网。 源点在这个AOE网中入度为0的点叫做源点。 终点在这个AOE网出度为0的点叫做终点。 AOE网的两个性质 只有这个顶点的入度的活动都已经结束这个顶点表示的事件才会开始。只有这个顶点的事件开始后从这个顶点出发的活动才会开始。 由于到达终点前所有指向这个终点边上的活动都必须结束所以完成整个工程的最短时间必须是那个源点到终点的最大长度这个最大长度叫做关键路径。关键路径上的活动叫做关键活动。 事件的最早发生时间ve(i): 从源点出发假设开始是0该顶点的入度的各个活动中的最长时间只有这个活动完成了这个事件才能发生。 事件的最晚发生时间vl(i):从终点出发要在保证不耽误工期的情况下关键路径也就是最短顶点对应的事件完成的时间在终点的最晚发生时间一定的条件下倒推其它点的最晚发生时间。如果一个点有两个出度推出了两个最晚发生时间要取最小的那个取更大的那个就有一个事件就不能完成了工程最晚完成时间就要推迟。 终点的事件最晚发生时间 最早发生时间。 活动的最早发生时间ee(i):某个活动开始的前提是那个顶点表示的时间开始了所以这个值和这个活动所在边的起点的事件最早发生事件相等。 活动的最晚发生时间el(i):只有这个顶点的入度的活动都已经结束这个顶点表示的事件才会开始所以我们知道这个顶点的最晚发生时间减去入度的活动的权值就是对应的该活动的最晚发生时间。 el(i) ee(i)的活动叫做关键活动关键活动所连成的源点到终点路径叫做关键路径可能有多条。证明省略。 下面我们通过题来演示一下 ❄️ 大题2 答案解析 画两个表格照着带权有向图直接写时间即可只要了解了这四个概念所代表的意思及其如何来求。 标准答案 图的遍历广度优先和深度优先 我们先介绍思想大题三会有具体的题目来演示操作 广度优先遍历类似于树的广度优先遍历也就是层序遍历它的基本思想是这样的 先任选一个顶点开始遍历。依次遍历这个顶点的邻接顶点。按照刚刚遍历的顺序去遍历邻接顶点的邻接点。如果图中还有顶点没有访问完任选一个没有被访问的顶点按照上面的步骤直到所有顶点被访问完。 深度优先遍历类似于树的先序遍历是其在图上的推广它的基本思想如下 先选一个顶点开始遍历。再从这个刚刚访问的顶点vi出发去访问它的第一个邻接点重复本步骤直到当前顶点没有邻接点。返回刚刚访问过的且还有未被访问邻接点的顶点找出并访问该顶点未被访问的邻接点执行步骤2。重复执行以上步骤直到所有顶点被访问完。 最短路径 最短路径有四种算法可以求详细原理可以看博主这篇博客。 ❄️ 大题3 答案解析 标准答案 答案的深度优先遍历序列是错误的。 查找 静态查找表顺序查找、折半查找 顺序查找按照顺序在表一般是数组中依次查找时间复杂度是 O ( N ) O(N) O(N)。一般不用。 折半查找即我们所说的二分查找算法。这个算法的前提是表已经有序。时间复杂度是 O ( l o g N ) O(logN) O(logN)。 ❄️ 大题1 答案解析 标准答案 . 动态查找表: 二叉排序树、二叉平衡树、m阶B树 ❄️ 二叉排序树 请看博主这篇博客 这个很简单考的不多重点看二叉平衡树和m阶B树。 ❄️ 二叉平衡树 二叉树平衡树上课只介绍了AVL树。 AVL树是平衡搜索二叉树的一种它是为了解决普通二叉搜索树不平衡的问题它通过保持每个结点的左右两棵子树的高度差不超过1来维持查找效率。 AVL树有以下性质满足以下性质的二叉树也叫做高度平衡 左右子树的高度差不超过1-101。左右子树也为AVL树 我们这里的左右子树的高度均为左右子树的最长路径的结点个数。 如果一棵二叉树是高度平衡的那么它就是平衡二叉树它的高度是 O ( l o g N ) O(logN) O(logN),搜索的效率也在 O ( l o g N ) O(logN) O(logN)量级。 我们重点来看一下AVL树的插入调整 左单旋 在当前高度较高的某节点的右子树的右边插入了一个新结点引发了不平衡需要右单旋。 右单旋 在当前高度较高的某节点的左子树的左边插入了一个新结点引发的不平衡需要左单旋。 左右双旋 当前高度较高的某节点的左子树的右子树插入了一个结点引发了不平衡需要先左单旋再右单旋转。 右左双旋 当前高度较高的某节点的右子树的左子树插入了一个结点引发了不平衡需要先右单旋再左单旋转。
我们用具体的题目来演示如何旋转 ❄️ 大题1 答案解析 标准答案 这个答案有点问题最后一个数据65插入的它没写命名的话博主是按照旋转的方向命名这个答案是按照插入的方向命名。 B树 B树是多路平衡二叉树。 B树的性质 2. B树的插入和删除 我们用下面的题目来演示如果你没有搞懂请自行去B站上学习。 ❄️ 大题2 答案解析 哈希表 ❄️ 哈希表的长度、哈希表的装填因子等 哈希表的长度是指的是哈希表可以存储的最大元素数量。 哈希表的装填因子是指的是当前已经存储的元素的数量桶的数量/ 哈希表的长度 ❄️ 常用的构造哈希函数的方法 除留余数法 除留取余法是将关键字除以一个不大于哈希表长度的正整数p一般是小于哈希表长度的最大质数并将所得余数作为地址。 具体而言除留取余法的步骤如下 1、选择一个不大于哈希表长度的正整数p一般是小于哈希表长度的最大质数作为模。 2、将关键字对p取模作为哈希表的索引地址。 直接定址法 直接定址法就是将关键字作为索引地址关键字就是下标要求关键字范围小且连续否则会造成空间浪费。 ❄️ 处理冲突的方法 开放寻址法 原理是当发生冲突时是以当前地址为基准去通过寻址找到下一个地址。 常用的寻址方法 线性探测发生冲突时从当前地址开始往后面去找空地址如果到达表尾就回到表头继续找直到找到或者已经遍历全表。二次探测(平方探测)发生冲突时从当前地址开始左右跳跃di 1 2 , − 1 2 , 2 2 , − 2 2 , 3 2 , − 3 2 … … 1^2,-1^2,2^2,-2^2,3^2,-3^2…… 12,−12,22,−22,32,−32……直到找到为止。
2.链地址法 又叫做拉链法这个方法是把哈希表的每个位置看成一个桶每个桶里面都是一个链表然后如果发生冲突了就把新的结点尾插到这个位置桶的尾部。 我们通过下面的题目来演示 ❄️ 大题3 答案解析