查找：错题总结 以下题目为牛客网专项练习：查找算法错题总结： 1 折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中素58，则它将依次与表中哪些素比较大小，查找结果失败（20，70，30，50） 解析：10个数首先和中间值20比较，58比20大选择右边，右边5个数选择中间值70,58比70小，选择左边，左边两个数中间值30进行比较，58比30大选择右边，右边一个数50,58比50大，没有找到。 2 使用二分搜索算法在 1000 个有序素表中搜索一个特定素，在最坏情况下，搜索总共需要比较的次数为（10）。 解析：至多比较次数是⌊log2(n)⌋+1,其中⌊ ⌋表示向下取整。2^10=1024 3 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( 分块查找 )查找法。 解析：分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表素动态变化时是难以满足的。而顺序查找可以解决表素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表素动态变化的要求，则可采用分块查找的方法。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。[1] 分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。 4 查找n个素的有序表时,最有效的查找方法是( 折半查找 ) 解析：折半查找最坏的情况下，查找长度为logn，二分查找树最坏的情况为n，其他的查找算法也是n。所以折半查找是最有效的查找算法。 5 用二分法查找表 (a0,a1,a2,a3,……a16) ，需要比较 2 次才能找到的素是（a3和a12 ） 解析：第一次找中间 mid = 8 比较 第一次比较不相同 mid =(7 +0)/2=3 或 mid =(9+16)/2=13 6 用概率查找改进查找效率，是经过多次查找以后使得（查找次数越多的素查找速度越快） 7 给定的一个长度为N的字符串str,查找长度为P(P<N)的字符串在str中的出现次数.下面的说法正确的是( 存在最坏时间复杂度为O(N+P)的算法 ) 解析：朴素匹配算法 时间复杂度O（(N-P+1)*P），KMP匹配算法 时间复杂度为O（N+P） 8 一个长度为32的有序表，若采用二分查找一个不存在的素，则比较次数最多是_6_. 解析：考察完全二叉树的深度问题，比较次数也就是深度，只含有一个节点的时候深度为1，假设深度为k，则有2^k-1>=n>2^(k-1)-1,其中2^k-1对应深度为k的满二叉树。对应节点数，那么等价于2^k>=（n+1）>2^(k-1)，不等式两边同时取log，k>=log(n+1)>(k-1),此时k等于log(n+1)向上取整数，因此log（32+1）向上取整为6。 9 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为_N__. 10 设有序顺序表中有n个数据素，则利用二分查找法查找数据素X的最多比较次数不超过（log2n + 1）。 11 设顺序表的长度为n，则顺序查找的平均比较次数为（（n+1）/ 2）。 解析：顺序表查找来说，最好的就是一次就可以找到，时间复杂度是O（1），最坏是要比较n次,O(n)。如果查找不成功，要进行n+1次比较。由于关键字在任何一个位置的概率都是相同的，所以平均查找次数是（n+1）/2，时间复杂度还是O（n） 12 既希望较快的查找又便于线性表动态变化的查找方法是 ( 索引顺序查找 ) 解析：索引顺序查找又称为分块查找，效率在顺序查找和折半查找之间。 13 设顺序线性表的长度为30，分成5块，每块6个素，如果采用分块查找并且索引表和块内均采用顺序查找，则其平均查找长度为( 6.5 )。 解析：分块查找会分两部分进行, 第一步先进行索引表查找判断其在那个字表中, 第二步然后进行在字表中的查找 索引表有5个素 所以平均查找长度为:(1+5)/2=3。字表中有6个素,所以平均查找长度为:(1+6)/2=3.5。所以总的平均查找长度为3+3.5=6.5 14 顺序查找不管其是否有序，都进行逐个遍历比较，直到相等为止。所以平均情况下查找长度相同。 15 深度优先需要无路可走时按照来路往回退，正好是后进先出。（栈） 广度优先则需要保证先访问顶点的未访问邻接点先访问，恰好就是先进先出（队列） 16 查找效率最高的二叉排序树是：平衡二叉树。 解析：二叉查找树的查询速度取决于树的深度，相同结点数深度最小的是平衡二叉树。 17 采用折半查找法查找长度为 n 的线性表时，每个素的平均查找长度为：log2n 。 18 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（O（logn） ）。 19 二分查找树里查询一个关键字的最坏时间复杂度是__O（n）__. 解析：二分查找最坏的情况是退化为线性查找，时间复杂度为O(n)。 20 给定一个整数sum,从有N个有序素的数组中寻找素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是：O（n） 21 红黑树和avl树都属于自平衡二叉树；两者查找、插入、删除的时间复杂度相同；包含n个内部结点的红黑树的高度是o(logn);TreeMap是一个红黑树的实现，能保证插入的值保证排序 22 分块查找是静态查找，动态查找包括二叉排序树、平衡二叉树，B树、B+树等. 23 顺序查找，目标数据可能在序列的任意位置，平均位置是n/2.所以顺序查找平均时间是n/2 24 折半查找的时间复杂性为( O（logn）) 25 就平均查找速度而言，下列几种查找速度从慢至快的关系是___顺序 分块 折半 哈希___。 26 在长度为n的顺序线性表中顺序查找值为x的素时，查找成功时的平均查找长度（假定查找每个素的概率均相等）为（（n+1）/ 2）。 解析：长度为n的线性表顺序查找x，则查找次数可能是1,2,3,…,n次，则和sum为n*(1+n)/2，所以平均查找次数为sum/n=(n+1)/2。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/52436.html
