注本文为博主学习408相关知识所撰写的学习笔记内容如有雷同纯属巧合。考点1 线性表的查找①顺序查找①顺序查找可以用于顺序/链式存储且不要求元素有序②算法简单但ASL平均查找长度较大查找效率不高③当查找表规模比较大时不适合使用顺序查找有序优化判定树②折半查找①折半查找只适用于顺序存储需要借助随机访问特性来快速定位元素且要求元素必须有序②mid的选取必须保证整体一致默认左右选左向下取整③折半查找可将时间复杂度优化到O()查找效率较高④折半查找的最多比较次数 折半查找判定树的树高 相同结点数量的完全二叉树的高度 ③分块查找①索引表中的每个元素含有各块的最大关键字和各块中第一个元素的地址②块内元素可以无序但块间必须有序③索引表是有序表可以进行顺序/折半查找查找表块内是无序的只能进行顺序查找④如果既要保证查找效率又要能满足表中元素动态变化的需求首选分块查找设有b块每块s个记录则如下典型真题2010年真题该题求采用折半查找中不存在的元素的比较次数由于我们知道折半查找的查找树高h即查找失败的比较次数树高5选择选项B。2015年真题该题折半查找判定树和二叉排序树是一样的必须保证左小于根小于右的序列对于A选项我们将判定树画出来即可发现180在200的右子树上但180比200小不可能在200右边无法构成折半查找关键字比较序列选择选项A。2024年真题该题折半查找只有两个要求即顺序存储随机访问和有序则可以观察4个选项发现都无法同时符合两个要求则选择选项D。2013年真题考点2 BST——二叉排序树①查找②插入1.若BST非空则将待插入结点的关键字和根结点的关键字比较遵循左根右的原则将结点插入合适的位置2.插入基于查找所以新插入的结点一定是叶子结点并且是查找不成功时查找路径上访问的最后一个结点的左或右孩子③删除删除叶子结点直接删除删除结点有左/右孩子删除后左/右孩子上位删除结有左右孩子将删除结点的中序前驱/后继与删除结点交转换为删除叶子结点的情况典型真题2013年真题该题题目给出删除二叉排序树T1中的某结点v后形成T2再将v插入形成T3首先我们知道二叉排序树的删除有三种情况即v在叶节点v有一个结点和v有两个结点的情况先看Ⅰ和Ⅱ若v是T1的叶节点则直接删除再插入结点v时T1和T3相同所以Ⅰ错误Ⅱ正确再看Ⅲ和Ⅳv不是T1叶结点时删除v再插入v的情况得到的T3与T1结构不同所以Ⅳ错误Ⅲ正确选择选项C。考点3 AVL——平衡二叉树①查找②插入离插入结点最近且平衡因子绝对值超过1的祖先结点以该结点为根的子树称为最小不平衡子树插入后导致AVL不平衡则调整范围就是最小不平衡子树左旋右子结点变为旋转结点的父节点右子结点的左子结点变为旋转结点的右子结点右旋左子结点变为旋转结点的父节点左子结点的右子结点变为旋转结点的左子结点③删除④性质h12345678124712203354①假设以表示深度为h的平衡二叉树中含有的最少结点数所有非叶结点的平衡因子均为1则1②n个结点的AVL的最小高度为③若AVL的高度为h则树中最多有个结点插入的关键字有序时典型真题2009年真题该题我们首先注意平衡二叉树同样满足左根右的关系我们需要检查选项中每个结点是否满足平衡因子的绝对值小于等于1A选项左子树高度为2右子树高度为0平衡因子为2不满足排除A选项B选项每一个结点都满足左右子树高度差值小于等于1选择选项BC选项对于根的右子树的结点来说平衡因子为2不满足排除C选项同理D选项也不满足。2010年真题该题考察平衡二叉树的插入在插入关键字48后得到新的平衡二叉树48很明显先插入37的右子树插入后发现不平衡属于RL型先让53进行右旋再将不平衡结点24左旋得到如下所示平衡二叉树则37所在结点的左、右子结点中保存的关键字分别是24、53选择选项C。2015年真题该题我们知道平衡二叉树肯定是一颗平衡二叉排序树而在二叉排序树中有一个性质是对它进行中序遍历时可以得到一个升序的序列题目中对该AVL进行中序遍历得到一个降序序列则我们可以知道该AVL的关键字大小规则为左根右则很明显选项A为错误选项选项B中若根结点无右子树则最小元素可以是根节点选项B错误选项C中在平衡二叉树插入的元素若不平衡则需要进行旋转旋转后插入的元素不一定是叶节点选项C错误所以选择选项D。考点4 B树和B树①结点结构n为结点内关键字的个数一般省略k为关键字为指向子树根结点的指针②性质B树B树关键字和子树的关系n个关键字对应n1棵子树n个关键字对应n棵子树根节点子树[2,m][2,m]根节点关键字[1,m-1]非根结点子树[,m][,m]非根节点关键字[,m-1]叶子结点/失败结点/终端结点所有叶子结点都在同一层且不带信息可类比折半查找判定树的失败结点叶子结点中包含了所有关键字信息以及指向含这些关键字记录的指针叶子结点本身按照关键字大小从小到大顺序链接查找方式随机查找随机查找和顺序查找高度注m为B树或B树的阶即这颗B树或B树的结点最多能有多少个孩子③查找B树B树优化减少IO次数④插入B树①插入后结点关键字个数≤m-1直接插入②插入后结点关键字个数m-1结点插入后的第个关键字进入父节点原结点一分为二B树①插入后结点关键字个数≤m直接插入②插入后结点关键字个数m从第个关键字开始原结点一分为二插入过程中要时刻注意是否需要修改索引中的关键字⑤删除B树①被删关键字不在终端结点用被删关键字的前驱/后继关键字代替被删关键字的位置转换为删除终端结点关键字的情况②被删关键字在终端结点删除后关键字个数≥直接删除删除后关键字且兄弟够借父下子上删除后关键字且兄弟不够借父下与子合并B树①被删关键字在终端结点删除后关键字个数≥直接删除删除后关键字且兄弟够借兄弟结点的关键字进入当前结点删除后关键字且兄弟不够借当前结点与兄弟结点合并删除过程中要时刻保持终端结点关键字和非终端结点关键字的一致性典型真题2009年真题该题A选项根节点子树范围为[2,m]所以A选项正确B选项B树的叶子结点都在同一层B选项正确C选项B树关键字默认为升序也可以强制要求降序C选项正确所以选择D选项B树中叶节点之间才通过指针链接。2012年真题该题考察B树的删除对于B树非根的关键字范围为[,m-1]即[1,2],则删除关键字78后最右叶节点为空1且左边兄弟够借则父下子上关键字65替代78的位置62替代65的位置则选择选项D。2017年真题该题我们需要记住B树的一个优化就是在于上面的结点可以索引不去存储关键字的信息减少磁盘IO次数即B树突出一个作用就是索引所以选择选项 B。2018年真题该题给出3阶B树则根结点关键字[1,2]非根结点关键字[1,2]由于高度为5且含有关键字最少则每个结点只有一个关键字我们可以发现会得到一个满二叉树的结构则关键字个数至少为选择选项B。考点5 散列表①名词区分同义词具有相同散列函数值的关键字非同义词具有不同散列函数值的关键字冲突/碰撞不同的关键字映射到了同一散列地址的现象堆积/二次聚集用线性探测法处理同义词的冲突过程中又添加了非同义词的冲突装填因子装填因子ɑ n/m 表中关键字个数/散列表长度注影响散列表的查找效率的因素装填因子、处理冲突的方法、散列函数构造散列函数的方法直接定址法除留余数法数字分析法平方取中法处理冲突的方法开放定址法线性探测法(Hi(H(key)di)%M)平方探测法(步长为平方)双散列法伪随机序列法链地址法(映射到同一地址的值将它们链在一起)②处理冲突的方法线性探测法①冲突发生时顺序查看表中下一个单元直到找出一个空闲单元或遍历全表②探测到表尾时下一个探测地址是表头③处理同义词的冲突过程中可能又添加了非同义词的冲突④不可以直接删除散列表中关键字仅做删除标记平方探测法①%m②散列表长度m必须是一个可以表示成4k3的素数③可以避免堆积但无法探测到散列表上的所有单元④不可以直接删除散列表中关键字仅做删除标记链地址法①将所有的同义词存储在一个链表中这个链表由其散列地址唯一标识②可以直接删除关键字③影响查找效率的因素①装填因子ɑa.ɑ n/m 表中关键字个数 / 散列表长度b.ɑ定义了一个散列表的装满程度ɑ越大产生冲突可能性越大c.平均查找长度ASL与n或m无直接关系而是依赖于装填因子ɑ②散列函数散列函数设计得越好关键字分布越均匀产生冲突可能性越小③处理冲突的方法决定了发生冲突后查找的效率有些方法可能还会引入新的冲突造成查找距离变长典型真题2024年真题考点6 红黑树①定义与性质①结点是红色或黑色根节点和叶子结点必是黑色②每个红节点必须有两个黑色的子节点即不能出现两个连续的红结点③从任一结点到每个叶子结点的所有路径都包含相同数目的黑色结点④从某结点出发不含该结点到达任一叶子结点包含叶节点的路径上的黑结点总数即为黑高bh此处挖坑待填补...
【408学习】数据结构——查找
注本文为博主学习408相关知识所撰写的学习笔记内容如有雷同纯属巧合。考点1 线性表的查找①顺序查找①顺序查找可以用于顺序/链式存储且不要求元素有序②算法简单但ASL平均查找长度较大查找效率不高③当查找表规模比较大时不适合使用顺序查找有序优化判定树②折半查找①折半查找只适用于顺序存储需要借助随机访问特性来快速定位元素且要求元素必须有序②mid的选取必须保证整体一致默认左右选左向下取整③折半查找可将时间复杂度优化到O()查找效率较高④折半查找的最多比较次数 折半查找判定树的树高 相同结点数量的完全二叉树的高度 ③分块查找①索引表中的每个元素含有各块的最大关键字和各块中第一个元素的地址②块内元素可以无序但块间必须有序③索引表是有序表可以进行顺序/折半查找查找表块内是无序的只能进行顺序查找④如果既要保证查找效率又要能满足表中元素动态变化的需求首选分块查找设有b块每块s个记录则如下典型真题2010年真题该题求采用折半查找中不存在的元素的比较次数由于我们知道折半查找的查找树高h即查找失败的比较次数树高5选择选项B。2015年真题该题折半查找判定树和二叉排序树是一样的必须保证左小于根小于右的序列对于A选项我们将判定树画出来即可发现180在200的右子树上但180比200小不可能在200右边无法构成折半查找关键字比较序列选择选项A。2024年真题该题折半查找只有两个要求即顺序存储随机访问和有序则可以观察4个选项发现都无法同时符合两个要求则选择选项D。2013年真题考点2 BST——二叉排序树①查找②插入1.若BST非空则将待插入结点的关键字和根结点的关键字比较遵循左根右的原则将结点插入合适的位置2.插入基于查找所以新插入的结点一定是叶子结点并且是查找不成功时查找路径上访问的最后一个结点的左或右孩子③删除删除叶子结点直接删除删除结点有左/右孩子删除后左/右孩子上位删除结有左右孩子将删除结点的中序前驱/后继与删除结点交转换为删除叶子结点的情况典型真题2013年真题该题题目给出删除二叉排序树T1中的某结点v后形成T2再将v插入形成T3首先我们知道二叉排序树的删除有三种情况即v在叶节点v有一个结点和v有两个结点的情况先看Ⅰ和Ⅱ若v是T1的叶节点则直接删除再插入结点v时T1和T3相同所以Ⅰ错误Ⅱ正确再看Ⅲ和Ⅳv不是T1叶结点时删除v再插入v的情况得到的T3与T1结构不同所以Ⅳ错误Ⅲ正确选择选项C。考点3 AVL——平衡二叉树①查找②插入离插入结点最近且平衡因子绝对值超过1的祖先结点以该结点为根的子树称为最小不平衡子树插入后导致AVL不平衡则调整范围就是最小不平衡子树左旋右子结点变为旋转结点的父节点右子结点的左子结点变为旋转结点的右子结点右旋左子结点变为旋转结点的父节点左子结点的右子结点变为旋转结点的左子结点③删除④性质h12345678124712203354①假设以表示深度为h的平衡二叉树中含有的最少结点数所有非叶结点的平衡因子均为1则1②n个结点的AVL的最小高度为③若AVL的高度为h则树中最多有个结点插入的关键字有序时典型真题2009年真题该题我们首先注意平衡二叉树同样满足左根右的关系我们需要检查选项中每个结点是否满足平衡因子的绝对值小于等于1A选项左子树高度为2右子树高度为0平衡因子为2不满足排除A选项B选项每一个结点都满足左右子树高度差值小于等于1选择选项BC选项对于根的右子树的结点来说平衡因子为2不满足排除C选项同理D选项也不满足。2010年真题该题考察平衡二叉树的插入在插入关键字48后得到新的平衡二叉树48很明显先插入37的右子树插入后发现不平衡属于RL型先让53进行右旋再将不平衡结点24左旋得到如下所示平衡二叉树则37所在结点的左、右子结点中保存的关键字分别是24、53选择选项C。2015年真题该题我们知道平衡二叉树肯定是一颗平衡二叉排序树而在二叉排序树中有一个性质是对它进行中序遍历时可以得到一个升序的序列题目中对该AVL进行中序遍历得到一个降序序列则我们可以知道该AVL的关键字大小规则为左根右则很明显选项A为错误选项选项B中若根结点无右子树则最小元素可以是根节点选项B错误选项C中在平衡二叉树插入的元素若不平衡则需要进行旋转旋转后插入的元素不一定是叶节点选项C错误所以选择选项D。考点4 B树和B树①结点结构n为结点内关键字的个数一般省略k为关键字为指向子树根结点的指针②性质B树B树关键字和子树的关系n个关键字对应n1棵子树n个关键字对应n棵子树根节点子树[2,m][2,m]根节点关键字[1,m-1]非根结点子树[,m][,m]非根节点关键字[,m-1]叶子结点/失败结点/终端结点所有叶子结点都在同一层且不带信息可类比折半查找判定树的失败结点叶子结点中包含了所有关键字信息以及指向含这些关键字记录的指针叶子结点本身按照关键字大小从小到大顺序链接查找方式随机查找随机查找和顺序查找高度注m为B树或B树的阶即这颗B树或B树的结点最多能有多少个孩子③查找B树B树优化减少IO次数④插入B树①插入后结点关键字个数≤m-1直接插入②插入后结点关键字个数m-1结点插入后的第个关键字进入父节点原结点一分为二B树①插入后结点关键字个数≤m直接插入②插入后结点关键字个数m从第个关键字开始原结点一分为二插入过程中要时刻注意是否需要修改索引中的关键字⑤删除B树①被删关键字不在终端结点用被删关键字的前驱/后继关键字代替被删关键字的位置转换为删除终端结点关键字的情况②被删关键字在终端结点删除后关键字个数≥直接删除删除后关键字且兄弟够借父下子上删除后关键字且兄弟不够借父下与子合并B树①被删关键字在终端结点删除后关键字个数≥直接删除删除后关键字且兄弟够借兄弟结点的关键字进入当前结点删除后关键字且兄弟不够借当前结点与兄弟结点合并删除过程中要时刻保持终端结点关键字和非终端结点关键字的一致性典型真题2009年真题该题A选项根节点子树范围为[2,m]所以A选项正确B选项B树的叶子结点都在同一层B选项正确C选项B树关键字默认为升序也可以强制要求降序C选项正确所以选择D选项B树中叶节点之间才通过指针链接。2012年真题该题考察B树的删除对于B树非根的关键字范围为[,m-1]即[1,2],则删除关键字78后最右叶节点为空1且左边兄弟够借则父下子上关键字65替代78的位置62替代65的位置则选择选项D。2017年真题该题我们需要记住B树的一个优化就是在于上面的结点可以索引不去存储关键字的信息减少磁盘IO次数即B树突出一个作用就是索引所以选择选项 B。2018年真题该题给出3阶B树则根结点关键字[1,2]非根结点关键字[1,2]由于高度为5且含有关键字最少则每个结点只有一个关键字我们可以发现会得到一个满二叉树的结构则关键字个数至少为选择选项B。考点5 散列表①名词区分同义词具有相同散列函数值的关键字非同义词具有不同散列函数值的关键字冲突/碰撞不同的关键字映射到了同一散列地址的现象堆积/二次聚集用线性探测法处理同义词的冲突过程中又添加了非同义词的冲突装填因子装填因子ɑ n/m 表中关键字个数/散列表长度注影响散列表的查找效率的因素装填因子、处理冲突的方法、散列函数构造散列函数的方法直接定址法除留余数法数字分析法平方取中法处理冲突的方法开放定址法线性探测法(Hi(H(key)di)%M)平方探测法(步长为平方)双散列法伪随机序列法链地址法(映射到同一地址的值将它们链在一起)②处理冲突的方法线性探测法①冲突发生时顺序查看表中下一个单元直到找出一个空闲单元或遍历全表②探测到表尾时下一个探测地址是表头③处理同义词的冲突过程中可能又添加了非同义词的冲突④不可以直接删除散列表中关键字仅做删除标记平方探测法①%m②散列表长度m必须是一个可以表示成4k3的素数③可以避免堆积但无法探测到散列表上的所有单元④不可以直接删除散列表中关键字仅做删除标记链地址法①将所有的同义词存储在一个链表中这个链表由其散列地址唯一标识②可以直接删除关键字③影响查找效率的因素①装填因子ɑa.ɑ n/m 表中关键字个数 / 散列表长度b.ɑ定义了一个散列表的装满程度ɑ越大产生冲突可能性越大c.平均查找长度ASL与n或m无直接关系而是依赖于装填因子ɑ②散列函数散列函数设计得越好关键字分布越均匀产生冲突可能性越小③处理冲突的方法决定了发生冲突后查找的效率有些方法可能还会引入新的冲突造成查找距离变长典型真题2024年真题考点6 红黑树①定义与性质①结点是红色或黑色根节点和叶子结点必是黑色②每个红节点必须有两个黑色的子节点即不能出现两个连续的红结点③从任一结点到每个叶子结点的所有路径都包含相同数目的黑色结点④从某结点出发不含该结点到达任一叶子结点包含叶节点的路径上的黑结点总数即为黑高bh此处挖坑待填补...
