软考-软件设计师：查找算法-错题集 作者：马育民 • 2025-05-11 21:42 • 阅读：10001 # 题 折半查找在有序数组A中查找特定的记录K：通过比较K和数组中的中间元素A[mid]进行，如果相等，则算法结束；如果K小于A[mid]，则对数组的前半部分进行折半查找；否则对数组的后半部分进行折半查找。根据上述描述，折半查找算法采用了（）算法设计策略。对有序数组（3，14，27，39，42，55，70，85，93，98），成功查找和失败查找所需要的平均比较次数分别是（(假设查找每个元素的概率是相同的) 问题1 A.分治 B.动态规划 C.贪心 D.回溯 问题2 A.29/10和29/11 B.30/10和30/11 C.29/10和39/11 D.30/10和40/11 ### 分析 构造对应的折半查找判定树如下： [](https://www.malaoshi.top/upload/0/0/1GW16hCNWovZ.png) - 根为42，即：第5个元素，算法：`(1 + 10) / 2 = 5` - 第二层结点： - 第2个元素14，算法：`(1+4)/2 = 2` - 第8个元素85，算法：`(6+10)/2 = 8` - 第三层结点： - 第1个元素3 - 第3个元素27，算法：`(3+4)/2 = 3` - 第6个元素55，算法：`(6+7)/2 = 6` - 第9个元素93，算法：`(9+10)/2 = 9` - 第四层结点： - 39 - 70 - 98 ##### 成功查找次数 - 41：在第一层，所以比较1次就能找到 - 14、85：在第二层，所以比较2次能找到 - 3、27、55、98：在第三层，所以比较3次能找到 - 39、70、98：在第四层，所以比较4次能找到 总共查找次数：`1+2*2+3*4+4*3 = 29` 平均查找次数：`29次/10个` ##### 失败查找次数 折半查找失败的过程，可以理解为对处于这10个元素之前的间隔位置的数进行了查找，对各个元素间隔进行编号依次为1、2、3、.….、11，此时： - 1号间隔位于3的左侧（要查找的数字比3还小），此时需要分别与元素42、14、3比较后才会查找失败，比较次数为3; - 2号位置位于3和14之间（要查找的数字在3-14之间），此时需要分别与元素42、14、3比较后才会查找失败，比较次数为3; - 3号位置位于14和27之间，此时需要分别与元素42、14、27比较后才会查找失败，比较次数为3； - 4号位置位于27和39之间，此时需要分别与元素42、14、27、39比较后才会查找失败，比较次数为4; - 5号位置位于39和42之间，此时需要分别与元素42、14、27、39比较后才会查找失败，比较次数为4; - 6号位置位于42和55之间，此时需要分别与元素42、85、55比较后才会查找失败，比较次数为3； - 7号位置位于55和77之间，此时需要分别与元素42、85、55、77比较后才会查找失败，比较次数为4; - 8号位置位于77和85之间，此时需要分别与元素42、85、55、77比较后才会查找失败，比较次数为4; - 9号位置位于85和93之间，此时需要分别与元素42、85、93比较后才会查找失败，比较次数为3； - 10号位置位于93和98之间，此时需要分别与元素42、85、93、98比较后才会查找失败，比较次数为4; - 11号位置位于98右侧（要查找的数字比98还大），此时需要分别与元素42、85、93、98比较后才会查找失败，比较次数为4; 此时平均查找次数为 `（3*5+4*6）/11=39/11` 因此第二问选择C选项。 # 题 n个关键码构成的序列[k1,k2,..Kn}当且仅当满足下列关系时称其为堆。 [](https://www.malaoshi.top/upload/0/0/1GW16xl4SaCZ.png) 以下关键码序列中，（）不是堆。 A.15,25,21,53,73, 65,33 B.15,25,21,33,73,65,53 C.73,65,25,21,15,53,33 D.73,65,25,33,53,15,21 ### 答案 C 根据顺序应该是大很多，如下： [](https://www.malaoshi.top/upload/0/0/1GW16xlX9zEf.png) 25 比左孩子小，不符合 # 题 对数组A=(2,8,7,1,3,5,6,4)构建大顶堆为 （ ）（用数组表示）。 A.(1,2,3,4,5,6,7,8) B.(1,2,5,4,3,7,6,8) C.(8,4,7,2,3,5,6,1) D.(8,7,6,5,4,3,2,1) ### 答案 C 过程如下： 将待排序的关键字分到一棵 完全二叉树 的各个结点中： - 根是第1个元素 - 第2层是 第 2、3 元素 - 第3层是 第 4-7 元素 - …以此类推 [](https://www.malaoshi.top/upload/0/0/1GW176cEemiz.png) 如果 父元素比子元素小，就交换位置，过程如下图： [](https://www.malaoshi.top/upload/0/0/1GW176caFD14.png) [](https://www.malaoshi.top/upload/0/0/1GW176coy437.png) 最终结果： [](https://www.malaoshi.top/upload/0/0/1GW176d37irA.png) 原文出处：http://malaoshi.top/show_1GW16hc4oLUa.html