国二计算机考试线性结构知识点思维导图
简单介绍国二计算机考试线性结构知识点内容
树图思维导图提供 国二计算机考试线性结构知识点思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 国二计算机考试线性结构知识点思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：2e03ee08e5fcad77bd95ee7391f637af
思维导图大纲
线性结构思维导图模板大纲
顺序查找
查找效率
有序表
ASL（成功）=（n+1）/2
ASL（失败）=n/2+n/(n+1)
因为n+1种失败情况，查找长度为1+2+...+n+n
无序表
ASL（成功）=（n+1）/2
ASL（失败）=n+1
特点
可以是顺序表或者链表
折半查找
折半查找判定树
一定是平衡二叉树
根据mid向上或向下取整，X个元素对应的判定树是唯一的
倒数第二层是满的，最下层的叶子结点从左向右先填左子树或从右向左先填右子树
查找效率
判定树高度：h=log2(n+1)向上取整
查找成功：次数<h
查找失败：次数=h或h-1（查找失败共n+1种情况）
特点
只适合有序的顺序表
查找条件：while(low<=high),high=mid-1或者low=mid+1
分块查找
特点
块内无序，块间有序
把长度为n的查找表分为b个s个记录的块
先折半后顺序
ASL=log2(n+1)+(s+1)/2
两次顺序查找
ASL=(b+1+s+1)/2
s=根号n，ASL取最小值
块内只能顺序查找，索引表查找可以顺序或折半
折半查找索引表，若未在索引表查到，最终low>high，并在low所zhi指向的分块中查找
相关思维导图模板
树图思维导图提供 作业帮思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 作业帮思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0fa2dfe58ee459432166d72cafc50675
树图思维导图提供 比亚迪产业链层级结构 在线思维导图免费制作，点击“编辑”按钮，可对 比亚迪产业链层级结构 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：72df0ee3a99356b9b8e1b41a677ed502
沪公网安备 31011502019485号
上海工商