微信与与网站建设,常德论坛网,精准营销的营销方式,wordpress 原创 转载目录 一、选择填空判断题题型一#xff08;顺序、二分查找的概念#xff09;题型二#xff08;分块查找的概念#xff09;题型三#xff08;关键字比较次数#xff09; 二、应用题题型一#xff08;二分查找判定树#xff09; 一、选择填空判断题
题型一#xff08;顺… 目录 一、选择填空判断题题型一顺序、二分查找的概念题型二分块查找的概念题型三关键字比较次数 二、应用题题型一二分查找判定树 一、选择填空判断题
题型一顺序、二分查找的概念 1、顺序查找适用于存储结构为的线性表。 A、顺序存储结构或者链式存储结构 B、散列存储结构 C、索引存储结构 D、压缩存储结构 解析A 顺序查找属于线性查找从线性表的一端开始依次检查所给定的关键字是否满足条件若找到符合条件的元素则查找成功否则查找失败。
由于线性表有顺序存储和链式存储两种存储方式顺序查找对这两种存储方式都适用若对于顺序表则通过数组的下标依次查找对于链表则通过指针依次查找在链表中只能进行顺序查找。 2、使用二分查找方法时对线性表的存储结构及特性的要求是。 A、元素的链表 B、有序的链表 C、无序的顺序表 D、有序的顺序表 解析D 二分查找折半查找属于线性查找每次取中间元素进行比较一直缩小范围继续进行查找直到查找到相关元素为止找到即查找成功否则查找失败。
二分查找只适用于有序的顺序表它要求线性表具有随机存取前提是查找表中必须是按关键字大小有序排列。 3、在一个顺序存储的有序线性表上查找一个数据时既可以采用折半查找也可以采用顺序查找但前者比后者的查找速度。 A、必然快 B、取决于表是递增还是递减 C、在大部分情况下要块 D、必然不快 解析C 顺序查找的优点是对元素的存储没有要求可以顺序存储和链式存储且对表内的有序性也没有要求但其缺点是当n较大时ASL较大导致效率低。在平均情况下折半查找比顺序查找的效率高。
题型二分块查找的概念 1、填空长度为7225的有序表采用分块查找进行查找为了提高顺序查找索引表和顺序查找相应块的效率则应将有序表分成_________块每块长度为_________此时平均查找长度是_________。 解析85、85、86 分块查找的平均查找长度等于索引查找和块内查找的平均查找长度之和即ASLASL索引表ASL子表。若查找表长度为n被均匀地分为b块且每块有s个记录则在等概率的情况下若对块内和索引表内都采用顺序查找的平均查找长度为ASLASL索引表ASL子表(b1)/2(s1)/2(s22sn)/2s且每块有记录为s √n。
所以被分为85块每块的最佳长度应该为√722585最合适为每个块建立索引索引表中索引项的个数为85即每块长度为85从85个块中进行顺序查找即(b1)/2(851)/243在每个块中进行顺序查找即(s1)/2(851)/243故平均查找长度为434386。
题型三关键字比较次数 1、已知有序表131824354750628390115134当二分查找值为90的元素时查找成功的比较次数为。 A、1 B、2 C、4 D、6 解析B low指针一开始指向13high指针一开始指向134所以mid指向50第一次比较9015所以low1high指针不变此时low指针指向62high指针指向134即mid指向90即第二次比较时找到目标元素查找成功的比较次数为2。 2、已知一个长度为16的顺序表L其元素按关键字有序排列若采用折半查找法查找一个L中不存在的元素则关键字的比较次数最多为。 A、4 B、5 C、6 D、7 解析B 对于顺序查找查找成功或不成功关键字的比较次数始终是n1次当定位至第i个元素时关键字的比较次数为n-i1。默认代码中采用监视哨若不采用监视哨关键字的比较次数为n
对于折半查找查找成功和查找失败的最多比较次数相同均为⌈log2(n1)⌉由于折半判定树不是一棵满二叉树其各分支高度相差为0或1且由于最多相差为1所以查找失败的最少次数为⌈log2(n1)⌉-1。故题中关键字的比较次数最多为⌈log2(n1)⌉⌈log2(161)⌉⌈log2(17)⌉ 4.087…取大于等于该值的最小整数向上取整即5。 3、为提高查找效率对有65025个元素的有序顺序表建立索引顺序结构在最好情况下查找列表中已有元素最多需要执行次关键字比较。 A、10 B、14 C、16 D、21 解析C 每个索引块的大小为 √65025255为每个块建立索引索引表中索引项的个数为255当对索引表和块内都采用折半查找时查找效率最高即ASLASL索引表ASL子表⌈log2(b1)⌉⌈log2(b1)⌉2⌈log2(b1)⌉2×816。
二、应用题
题型一二分查找判定树 1、若一个有序顺序表表长为12 1画出对其进行二分查找的二分查找判定树 2在等概率假定条件下计算对该表进行二分查找时查找成功和查找失败的平均查找长度。 解析1二分查找判定树的求法 ①确定根结点取low1high12mid向下取整小于等于这个数的最大整数即mid⌊(lowhigh)/2 ⌋⌊6.5⌋6即元素6为判定树的根结点如下 ②从mid的左右子表开始进行查找。 ③mid左子表查找
【左子树】此时low1不变high变为mid-1mid6即highmid-16-15改变后的mid⌊(lowhigh)/2⌋⌊6/2⌋⌊3⌋3所以根结点6的左子树为3如下 继续探索左子树low1不变high变为mid-1mid3即highmid-13-12改变后的mid⌊(lowhigh)/2 ⌋⌊3/2⌋⌊1.5⌋1所以结点3的左子树为1如下 若继续探索左子树易知结点1无左子树。从结点1开始探索右子树high2不变low为mid1mid1即lowmid1112改变后的mid⌊(lowhigh)/2 ⌋⌊4/2⌋⌊2⌋2所以结点1的右子树为2如下 【右子树】此时从结点3开始探索右子树high5不变low为mid1mid3即lowmid1314改变后的mid⌊(lowhigh)/2 ⌋⌊9/2⌋⌊4.5⌋4所以结点3的右子树为4如下 若继续探索左子树易知结点4无左子树。此时从结点4开始探索右子树high5不变low为mid1mid4即lowmid1415改变后的mid⌊(lowhigh)/2 ⌋⌊10/2⌋⌊5⌋5所以结点4的右子树为5如下 ④mid右子表查找此时high12不变low为mid1mid6即lowmid1617改变后的mid⌊(lowhigh)/2 ⌋⌊19/2⌋⌊9.5⌋9如下 此时从结点9开始探索左子树low5不变high为mid1mid9即highmid19110改变后的mid⌊(lowhigh)/2 ⌋⌊15/2⌋⌊7.5⌋7如下 …… 最后可以得到如下
2查找成功ASL1×12×24×35×4/1237/12。 查找失败判定树中将其补全第四行失败的叶结点有3个第五行失败的叶结点有10个如下 ASL3×34×10/1349/13。
