高效作业18 第18课 数据查找1——查找算法基础-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

高效作业18[第18课　数据查找1——查找算法基础](见学生用书P246) 【A级　新教材落实与巩固】 1．在存有n 个元素的数组中进行顺序查找，其查找不成功的比较次数是(　D　) A．(n＋1)/2　　　　B．n/2＋1 C．n/2 D．n 【解析】 若所有元素都比较完毕仍找不到，则表明查找失败，选项D正确。 2． 对具有15个元素的有序数组做二分查找，若查找失败，则至少需要比较的次数是(　C　) A．15次　　B．3次　　C．4次　　D．5次 【解析】 对15个数据查找，最多查找次数为int(log215)＋1＝4，选项C正确。 3． 在一个元素有序的数组内进行二分查找，若中间位置的元素小于查找的键值，就将查找范围确定在数组的前半部分，则该数组的排序方式是(　B　) A．降序 B．升序 C．无序 D．无法确定 【解析】 查找的键值比中间位置小，而下一次的查找范围是前半部分，说明前半部分比后半部分数据要小，因此数据是升序排序的，选项B正确。 4． 有如下Python 程序段： import random key＝random.randint(35，45)*2 i＝0；j＝len(a)－1；s＝[] while i<＝j： m＝(i＋j＋1)//2 s．append(a[m]) if key<a[m]： j＝m－1 else： i＝m＋1 数组a 中的元素为“58，69，78，80，83，84，90，90，95”，则执行该程序段后，数组 s 中的元素不可能为(　D　) A．83，90，95 B． 83，78，80 C．83，90，90，84 D．83，78，69，58 【解析】 分析对分代码，4 个选项都没有问题。但是考虑到查找数key 的范围[70，90]，与a[1](69)比较之后，i＝1＋1＝2，a[0](58)已经不在查找区间了。所以选项D符合题意。 5． 有如下Python程序段： a＝[9，15，19，20，23，36，78，87，96，100] ans＝[]；i＝0；j＝9 key＝int(input(”请输入待查数据：　”)) flag＝False while i<＝j and not flag： m＝(i＋j)//2 ans.append(a[m]) if a[m]＝＝key： 　flag＝True elif a[m]>key： j＝m－1 else： i＝m＋1 print(ans) 执行该程序后，当输入key 的值为15 时，输出的结果是(　A　) A．[23，15] B． [23，19，15] C． [20，15] D．[20，19，15] 【解析】 查找过程如下。执行该程序后，当输入的key 值为15 时，输出的结果是[23，15]，选项A正确。 ans i j m [m] 23 0 9 4 23 23，15 3 1 15 6．2023·乐清中学检测有如下Python 程序段： import random as rd a＝[10，11，13，16，16，21] key＝rd.randint(11，16) i，j＝0，len(a)－1 c＝1 while i<＝j： m＝(i＋j)//2 if key>a[m]： i＝m＋1 c＝c＋1 else： j＝m－1 c＝2*c 执行上述程序段后，c 的值有多少种可能(　C　) A．1 B． 2 C． 3 D．4 【解析】 key的值为11时，c的值为6；key的值为[12，13]时，c的值为4；key的值为[14，16]时，c的值为8。有3种可能，选项C正确。 7．某二分查找算法的Python 程序段如下： import random key＝random.randint(0，4)*2＋5 n＝10；ans＝0 a＝[4，5，5，8，9，11，11，13，15，17] i＝0；j＝n－1 while i<＝j： m＝(i＋j)//2 if a[m]<＝key： 　i＝m＋1 else： j＝m－1 ans＋＝a[m] print(ans) 执行该程序段后，ans的值不可能是(　A　) A．19 B．27 C．37 D．44 【解析】 key 的值有五种可能5，7，9，11，13，画出二分查找树，如图所示：注意找到后不退出，遇到相同的会往右找。ans 记录的是路径中所有数的和。 当key＝5，ans 为9＋5＋5＋8＝27； 当key＝7，ans 为9＋5＋5＋8＝27； 当key＝9，ans 为9＋13＋11＝33； 当key＝11，ans 为9＋13＋11＋11＝44； 当key＝13，ans 为9＋13＋15＝37。 19没有可能，选项A符合题意。 8．有如下Python 程序段： d＝[88，77，53，47，39，28] i，j，n＝0，len(d)－1，0 key＝int(input(”请输入要查找的数字：　”)) while i<＝j： m＝(i＋j)//2；n＋＝1 if key＝＝d[m]： break if key>d[m]： j＝m－1 else： i＝m＋1 print(i，j，m，n) 执行该程序段后，下列说法正确的是(　C　) A．无论key值是否在列表d中出现，输出i 的值都比j 大 B．当输入key 的值大于d[0]时，输出j 的值为0 C．当输入key 的值为40时，输出n 的值为3 D．当输入key 的值为40时，输出m 的值为5 【解析】 程序实现在降序序列中进行二分查找。选项A，当key的值在列表d中出现时，i＜＝j，即有可能跳出循环，选项错误；选项B，当key值大于d[0]时，j＝m－1＝－l, 选项错误；选项C、D，当查找的key为40时，查找过程如下： i＝0，j＝5，m＝(i＋j)//2＝2，n＝l→ i＝m＋1＝3 i＝3，j＝5，m＝(i＋j)//2＝4，n＝2 →j＝m－1＝3 i＝3，j＝3，m＝(i＋j)//2＝3，n＝3→i＝m＋1＝4 由此可知选项C正确、选项D错误。 9．2023·诸暨中学检测有如下Python程序段： import random a＝[10，11，13，16，16，21] key＝random .randint(0，30) i＝0 j＝len(a)－1 n＝0 while i<＝j： m＝(i＋j)//2 n＋＝l if key>a[m]： i＝m＋l else： j＝m－1 print(n) 执行该程序段后，n的值有多少种可能？(　B　) A．1 B．2 C．3 D．4 【解析】 程序中，key的取值范围为[0，30]。根据程序可画出如下查找二叉树。查找过程中，找到数据也不会立即退出循环，循环结束的条件为i＝j＋1。结合该题对应的查找二叉树可以看出，当待查找数据小于等于10时，查找次数为2: 当待查数据大于10时，查找次数均为3，故n可能有两个不同的值，选项B正确。 10．有如下Python程序段： def search(i，j)： while i<＝j： m＝(i＋j)//2 if a[m]>a[m－1] and a[m]<a[m＋l]： 　i＝m＋l elif a[m]<a[m－l] and a[m]>a[m＋l]： j＝m－1 else： return m a＝[3，11，20，25，30，36，50，49，37，16] print(a[search(0，9)]) 执行该程序段后，输出的结果是(　A　) A． 50 B． 6 C． 7 D．49 【解析】 本题是在找数组的拐点。根据if语句的条件。观察数组元素， 50处于上升和下降的拐点处。选项A正确。 11．有如下Python程序段： key＝int(input(”请输入任意一个整数：　”)) a＝[12，18，22，27，36，45] ans＝0 i＝0；j＝len(a)－1 while i<＝j： m＝(i＋j＋1)//2 if a[m]<＝key： i＝m＋1 else： j＝m－1 ans＋＝a[m] print(ans) 执行该程序段时，若输入任意的key值，则ans的值不可能是(　A　) A．45 B．57 C．67 D．72 【解析】 需要注意三个点。(1)该程序段找到key后并不结束循环：(2)对分点m＝(i＋j＋1 )//2，每次对分点会右偏；(3)第一个分支对应的条件为a[m]<＝key。结合以上三点，再通过构建二叉查找判定树的方式即可解题。如下图所示： 选项B，输入小于12的key值，查找路径为27→18→12, 此时ans的值为57；选项C，输入[18，27)范围的key值，查找路径为27→18→22, 此时ans的值为67；选项D，输入大于45的key值，查找路径为27→45，此时ans的值为72，选项A符合题意。 12．2023·余姚中学检测有如下Python 程序段，在无序的序列中利用对分查找算法求第k 个大的数： k＝3 a＝[8，4，6，7，5，6，2，4] low，high＝min(a)，max(a) while low<＝high： m＝(low＋high)//2 cnt＝0 for i in a： if i>m： cnt＋＝1 if cnt>＝k： low＝m＋1 else： high＝m－1 执行该程序段后，下列说法不正确的是(　D　) A．第k 大数是low B．low>high C．m 的值为6 D．cnt 的值为3 【解析】 选项A, 第3 大的数是6，选项正确；选项B, low＝6，high＝5，选项正确；选项C, m＝6，选项正确；选项D, cnt 的值为2，选项错误。 13． 有如下Python 程序段： import random a＝[1，3，5，7，9，11，13，15] key＝random.randint(1，8)*2 i，j＝0，len(a)－1 s＝0 while i<＝j： m＝(i＋j＋1)//2 if a[m]＝＝key： break if a[m]>key： j＝m－1；s－＝1 else： i＝m＋1；s＋＝1 print(s) 执行该程序段后，s 的值有多少种可能？(　A　) A．4 种 B．5 种 C．7 种 D．8 种 【解析】 列表a 中的元素为1～15 中的奇数，查找的key 为2－16 中的偶数，所以查找的结果不存在a[m]＝＝key 也就是找到的情况，break 不会被执行。查找的过程如下： 所以，s 的值可能为－2，－1，1，3，共4 种。选项A正确。 14．2023·温州中学检测某二分查找算法的Python程序段如下： i，j＝0，9；n＝0；flag＝True key＝int(input().strip()) while i<＝j and flag： m＝(i＋j)//2 if a[m]＝＝key： flag＝False elif a[m]<key： i＝m＋1 n＝n＋1 else： j＝m－1 n＝n－1 若列表a中的元素依次是5，11，18，23，27，33，34，41，45，69，程序执行后变量n的值是2，则输入的整数key的值不可能是(　B　) A．25 B．34 C．45 D．60 【解析】 本题考查二分查找算法。用二叉搜索树画出各个元素的搜索顺序，图中各个左子树方向可以让n自减，右子树方向可以让n自增。选项A，若key＝25，则从节点23的右侧出循环，此时n的值是3－1＝2；同理key＝45或key＝60都会让n＝2；选项B，key＝34，则从节点34处结束循环，此时n＝2－1＝1，选项B符合题意。 【B级　素养形成与评价】 15．有如下Python程序段： import random a＝[4，2，6，5，4，2，9，7] k＝random.randint(1，10) i＝0；j＝len(a)－1；x＝”” while i<＝j： m＝(i＋j)//2 if k<＝a[m]： j＝m－1；x＝x＋”L” else： i＝m＋1；x＝x＋”R” print(x) 执行该程序段后，输出的结果不可能是(　C　) A．LLL B．LRL C．RLR D．RRRR 【解析】 输入的内容可分为四种情况，(－∞，2]，[3，5]，[6，9][10，＋∞)，故可能产生四种不同的s的值['LLL', 'LRL', 'RRL', 'RRRR']，则d中不可能出现的是RLR。选项C符合题意。 16．峰值元素指数组中其值大于左右相邻值的元素，如序列3、8、4、1 中，8 为峰值元素。一个数组中可能包含多个峰值元素，现需要找出其中一个峰值元素所在的位置(默认第一个数的左侧和最后一个数的右侧值为0，即序列1、2、3 中，3 也为峰值元素)。实现该功能的Python 程序段如下： i＝0；j＝6 while i<j： m＝(i＋j)//2 if a[m＋1]>a[m]： i＝m＋1 else： j＝m print(”峰值位置是”，i) 数组a＝[10，2，25，17，20，21，9]，执行该程序后，峰值位置为(　C　) A．0 B．2 C．5 D．8 【解析】 程序过程如下表： i j m a[m＋1]>a[m] 1 0 6 3 True 2 4 6 5 False 3 4 5 4 True 5 5 选项C正确。 17．2023·平阳中学检测有如下对分查找程序，a为按非降序排序的整型数组。 importrandom key＝random.randint(0，4)2＋20 a＝[12，14，15，15，19，x，20，24，y，26] i＝0；j＝n－1；c＝0；n＝10；ans＝0 while i＜＝j： m＝(i＋j)//2 if a[m]＜＝key： i＝m＋1 else： j＝m－1 c＋＝1 测试所有可能的key值，程序执行后，c均等于4，则x、y的值可以为(　D　) A．19，25 B．20，26 C．20，25 D．20，24 【解析】 由c始终等于4可知，查找次数必定为4次，该对分查找并没有找到即break结束循环得语句，所以可以把该对分查找程序看作不断排除的过程，即i＞j表示排除完所有的数据节点，则程序结束，即对应的二叉排序树根据条件遍历到叶子节点为止。根据随机函数产生的key最小为20，若x为19，key＝20，则c等于3，排除选项A；若y是26，key＝24，则c为3，排除选项B；若y是25，key＝24，则c为3，排除选项C。选项D正确。 18．有如下Python程序段： import random a＝[1，3，3，8，8，10，10，14，16，17] key＝random.randint(0，9)*2 ans＝－1；f＝0 L＝0；R＝9 while L<＝R： m＝(L＋R＋1)//2 if a[m]＝＝key： ans＝m break if a[m]>key： R＝m－1 f－＝1 else： L＝m＋1 f＋＝1 执行该程序段后，下列关于f和ans的结果的说法中，正确的是(　D　) A． f可能的最小值为－3 B． f的值可能为－1 C． ans的值可能为1 D．ans的值不可能为3 【解析】 由代码可知，在二分查找树中，每往左一步f减1，往右走一步f加1, 找到时退出循环，而且key的取值范围是[0，18]中的偶数。画出对应二叉树， 如图所示： 选项A，f要取得最小值，必须走到二叉树的最左侧，比如找0, 最后得到的f值为－4，选项错误；选项B，f的值不可能是－1，因为要使得f为－1，必然要往左走一步，而左子树的根不是偶数，所以不可能为－1，选项错误；选项C，ans的值不可能是1, 因为当ans为l时，意味着在数值3的位置结束循环，选项错误；选项D，ans的值不可能是3因为处于第四层的最右没有偶数，选项正确。 19．有如下Python 程序段： a＝[5，14，3，12，6，7，3，9，20，1] l＝min(a)；r＝max(a) #min 取列表最小值，max 取列表最大值 maxi＝3 while l<＝r： mid＝(l＋r)//2 cnt＝0 for i in a： if mid<i： cnt＋＝1 if cnt<maxi： r＝mid－1 else： l＝mid＋1 执行上述程序段后，下列说法正确的是(　C　) A．a 列表中第3 大的数r B．cnt 的值为2 C．l 的值为12 D．mid＝(l＋r)//2 代码执行3 次 【解析】 本题中mid 取出了l 和r 的中间值，通过循环语句，找出了列表中比mid值大的元素个数并用cnt 进行记录，若cnt<maxi，代表列表a 中比mid 大的元素还未达到maxi 个，执行r＝mid－1，向前缩减范围。当cnt＝＝maxi，代表列表a 比mid 大的元素已经达到或超过maxi 个，执行l＝mid＋1，向后缩减范围。当l>r 时，循环结束，此时的r 值应为列表a 中第maxi＋1 大的元素，因为列表a 中比r 大元素有maxi 个。结束时r 的值为11，l 的值为12，选项C正确。 20．有如下Python 程序段： import random a＝[2，3，5，8，10，10，10，17，19，20] key＝random.randint(1，30) # 随机生成[1，30]范围内的整数 i，j＝0，9 while i<＝j： m＝(i＋j)//2 if a[m]>key： 　j＝m－1 else： i＝m＋1 print(j) 执行该程序段，下列说法正确的是(　B　) A．若key 的值为10，则输出的值为3 B．若输出的值为8，则key 的值一定为19 C．对于任意key 值，语句“m＝(i＋j)//2”最少执行1 次 D．对于任意key 值，语句“m＝(i＋j)//2”最多执行3 次 【解析】 二分查找的关键代码中，没有提前终止循环的语句。列表a 的元素个数是10 个，介于7～15 之间，查找次数最少3次，最多4 次。m＝(i＋j)//2 语句对应的其实就是查找次数，所以选项C、D 均错误。这段代码是二分查找中的边界查找。根据条件if a[m]>key，当key＝10 时，i＝7，j＝6，选项A 错误；j＝8，i＝9，对应的元素分别是19，20，19＝<key<20，key 又是一个整数，那只能是19，选项B 正确。 21．2023·北仑中学检测为完善功能，某软件版本号由1 更新至n(整数)。公司新开发的测试程序检测出版本n 存在bug，为查找最早出现bug 的版本号，编写Python 程序，部分代码如下： Left，Right＝1，n while Left<Right： mid＝(Left＋Right)//2 if judge(mid): #judge() 函数功能为判断是否有bug，若有则返回True else： Left＝mid＋1 print('最早出现bug 的版本号为：'＋str( )) 上述程序段中加框处可选的代码有： ①Right＝mid　②Right＝mid－1　③Left ④Left＋1 下列选项中，代码顺序正确的是(　A　) A．①③ B．②③ C．①④ D．②④ 【解析】 本题考查二分查找算法的变形。由于代码中二分查找的模板是Left < Right，而不是教材中的Left <＝Right 的模式。因此若(1)处选择代码②，则由于不能遍历所有的数组元素，此时将导致错误，因此(1)处应该选择代码①，即Left 可以排除中点mid，而另外一边Right 则不能排除中点mid。至于(2)处代码，可以用1、2、3、4 进行模拟，若版本3 有bug，则二分查找后，最终Left 为3，Right 和m 也为3，故选③。综上，选项A正确。 22． 有如下Python 程序段，实现输入key 的值，输出列表a 中大于key 的第一个数的索引。 a＝[1，1，2，2，2，3] print(a) key＝int(input('请输入一个整数：　')) i＝0 while i<j： if key>＝a[m]： else： if j＝＝len(a)： print(f”>{key} 的数不存在”) else： print(f”>{key} 的第一个数的索引是{j}”) 上述程序段中，加框处代码有误，修改后得到正确的运行结果如下： 加框处代码错误的个数为(　B　) A． 4 B．3 C．2 D．1 【解析】 本程序要查找第一个大于待查找数值的索引位置。根据输入3 时的运行结果可知j 可以取到len(a)，又根据对分查找的基本思想，j 为查找的右边界，不可能增大，所以j 的初值应为len(a)。当前状态下，输入2 时，i，j 的值变化如表1，可以发现由于将m－1 赋值给j，循环结束后，j 的值为最后一个与待查找数值相等的位置，可见j＝m－1 应更改为j＝m。更改后，输入2 时，i，j 的值变化如表2，可以发现由于m 取i 和j 平均数时向上取整，会让程序陷入死循环，可见m＝(i＋j＋1)//2 应更改为m＝(i＋j)//2。综上，有三处错误，选项B正确。 23．2023·台州中学检测列表a 和列表b 均有5 个从小到大排列的整数元素，且列表a 的最后一个元素大于列表b 的最后一个元素。有如下Python 程序段： i＝0；j＝len(a)－1；c＝0 for key in b： while i<＝j： m＝(i＋j)//2；c＋＝1 if key<a[m]： j＝m－1 else： i＝m＋1 a＝a[：i]＋[key]＋a[i：] i＋＝1；j＝len(a)－1 执行该程序段后，c 的值至少是(　B　) A．5 B．6 C．10 D．20 【解析】 本题考查二分查找及插入算法的变形知识。分析代码可知，外循环共进行5 轮，且列表a 的元素的数值一直变大。而内循环中的二分查找，都是找到key 值不退出的模式，必须直到i>j 为止才会结束。和普通的二分查找不同的是，本代码中每次查找左边界i 的值只能增加，不能减少。分析第一次二分查找，若想查找次数最少，则key 值应该介于列表a 的第三、四两个数中间，这样二分查找次数只需要2 次即可。然后将key 插入i 的后面，然后更新i 和j 的值继续下一次插入。根据分析，插入的key 值继续保持在倒数第3 位，此时的查找次数只需要一次，后续也是如此。例如，a＝[1，2，3，9，10]，b＝[4，5，6，7，8]，这样总共只需要6 次查找即可完成插入。选项B正确。 学科网（北京）股份有限公司 $$