资源简介

六、 查找算法及程序实现
1. 某二分查找算法的Python程序段如下:
key = int(input())
s = "" ; i = 0 ; j = 9
while i<=j:
　　m = (i ＋ j)// 2:
　　if a[m] == key:
　　　　break
　　if key < a[m]:
　　　　j = m － 1 ; s = s ＋ "L"
　　else:
　　　　i = m ＋ 1 ; s = s ＋ "R"
若按非降序排序的整型列表a=[11,23,31,39,44,52,60,x,69,89],输入key值为66,执行该程序段后,s值为“RRL”,则x的可能值的个数为(　D　)
A. 3 B. 4
C. 5 D. 6
【解析】 本题考查二分查找知识。根据非降序排序(允许存在相同数据的升序序列)的整型列表可知, x的取值范围应该是60~69。再考虑到要查找的key值为66,执行该程序段后s值为"RRL",因此可以判断出查找的中值m的顺序分别为5、8、9,而x的位置是8,也就是说,以key=66为关键字进行第二次查找后继续右偏,这说明x的值肯定比66小(不可能等于66,若等于66则退出查找),因此可以将x的取值范围缩小为60~65之间的整数,即60、61、62、63、64、65这6个整数,D正确。
2. 某二分查找算法的Python程序段如下:
a=[12,14,15,15,17,18,20,20,23,25]
n=0
i=0
j=len(a)－1
k=int(input("请输入要查找的数"))
while i<=j:
　　m=(i＋j)//2
　　n=n＋1
　　if a[m]>k:
　　　　j=m－1
　　else:
　　　　i=m＋1
当输入的k值为20,程序运行结束后,下列说法中,错误的是(　A　)
A. m的值是7 B. i的值是8
C. j的值是m－1 D. n的值是3
【解析】 本题考查二分查找。该二分查找算法程序中,找到key的时候不退出,而是继续往下查找,循环结束时,i=8,j=7,m=8,n=3,A符合题意。
3. 某二分查找算法的Python程序段如下:
f=[0]*9
key = int(input())
i = 0;j = 8
while i <= j:
　　　m = (i ＋ j)// 2
　　　f[m] = 1
　　　if a[m] == key:
　　　　　break
　　　elif a[m] > key:
　　　　　j = m － 1
　　　else:
　　　　　i = m ＋ 1
整型列表元素a[0]到a[8]为升序序列,输入待查找的数key,执行该程序段后,下列选项中,f[0]到f[8]各元素值不可能的是(　C　)
A. 1,1,0,0,1,0,0,0,0
B. 0,0,0,0,1,0,0,0,0
C. 0,0,0,0,1,1,1,1,0
D. 0,1,1,1,1,0,0,0,0
【解析】 本题考查二分查找算法。选项A可以查找的数key与列表元素a[0]相等、比列表元素a[0]小或者比列表元素a[0]大但比列表元素a[1]小的数,不符合题意。选项B要查找的key与列表元素a[4]相等,不符合题意。选项C查找完中间元素a[4]后,往右侧下一个要查找的中间元素是a[6],接下来要么比列表元素a[6]大,要么比列表元素a[6]小,所以a[5]与a[7]不可能都为1,符合题意。选项D可以查找的数key与列表元素a[3]相等、比列表元素a[3]大但比a[4]小或者比列表元素a[2]大但比列表元素a[3]小的数,不符合题意。
4. 某二分查找算法的Python程序段如下:
key = int(input())
s = ""
i = 0;j = 9
while i <= j:
　　m = (i ＋ j)// 2
　　s = s ＋ str(a[m])
　　if a[m] > key:
　　　　j = m － 1
　　else:
　　　　i = m ＋ 1
print(s)
列表元素a[0]到a[9]的值依次为“2,3,5,8,9,10,13,17,19,20”。输入待查找的数key,执行该程序段,则s显示的内容可能是(　B　)
A. 9　3 B. 9　3　5
C. 9　17　19　13 D. 9　3　5　8　19
【解析】 本题考查二分查找。由代码可知,查找到数据key后不退出,直到满足条件i>j才退出循环。由于3个选项都涉及9和3,因此可以先检查左半区。第一次循环,m=4,查找到数据“9”;若key值小于9,则更新j的值为3,此时m=1,查找到数据“3”;若key值大于3,则更新i=2,下一次查找m=2,查找到数据“5”;若key值小于5,则下一次查找更新j=1,此时i > j,循环终止,因此字符串s记录的值为“9 3 5”,B正确。因为此时i<=j,循环还要继续进行,A错误。9 、17、19后面不可能出现13,C错误。当数据量n为10时,最多查找4次就会退出,D错误。
5. 某二分查找算法的 Python 程序段如下:
i = 0; j =9; c = 0
key = int(input())
while i <= j:
　　m = (i ＋ j)// 2
　　c = c ＋ 1
　　if key < a[m]:
　　　　j = m － 1 　
　　else:
　　　　i = m ＋ 1
print(j)
已知列表a为[1,5,5,7,9,9,9,11,16,18],下列说法中,错误的是(　B　)
A. 若输入10,程序运行后输出的值j是6
B. 程序运行后,a[i]的值可能等于key
C. 程序的功能是输出列表中最后一个小于等于key的元素所在的位置
D. 对于不同的输入值key,程序运行后c的值一定大于2
【解析】 本题考查二分查找中key值的边界问题。核心问题是确定二分结束时的区间变量i、j的位置,即查找key的边界问题。通过模拟可以发现本题程序查询key值的右边界,二分结束时j ＋ 1=i,所以输出j的含义为“小于等于key的元素个数”,即“最后一个小于等于key的元素位置”,C不符合题意。同理,当key=10时,j=6,A不符合题意。而变量i的位置在j之后,变量i的含义是“大于key的最小值的位置”,a[i]的值不可能等于key,而a[j]的值可能等于key,B符合题意。通过模拟可知,10个元素的二叉查找树深度为4,不可能在第2层结束,查找次数肯定大于等于3,最多查找4次,D不符合题意。
6. 有如下Python程序段:
a=[5,6,18,22,27,28,55,70,80]
i = 0; j = 8; f = False
L = 0; R = 0
key = int(input())
while i <= j and f == False:
　　m = (i ＋ j)// 2
　　if key == a[m]:
　　　　f = True
　　if key < a[m]:
　　　　j = m － 1; L = L ＋ 1
　　else:
　　　　i = m ＋ 1; R = R ＋ 1
程序运行后,L、R的值分别为2、1,则输入的关键字key可能是(　A　)
A. 5 B. 6
C. 18 D. 28
【解析】 本题考查二叉树。由于找到key值之后f=False,因此查询成功后不会立即跳出,而是在查询成功后会多一次偏移。key=5则L=2,R=1;key=6则L=1,R=1;key=18则L=1,R=2;key=28则L=1,R=2。A正确。
7. 有如下Python程序段:
key = int(input()); s=""
i,j = 0,len(a)－1
while i<=j:
　　m = (i＋j)//2
　　if a[m]　　　　i = m ＋ 1
　　　　s = s ＋ "R"
　　else:
　　　　j = m － 1
　　　　s = s ＋ "L"
print(s)
已知数组a的值为[10,15,32,32,45,53,53,65,77,98],程序运行后,变量s的值可能是(　B　)
A. LR B. LRL
C. LRR D. RLR
【解析】 本题考查二分查找算法。由代码可知,本题找到key值后并不退出。模拟后可知当输入的key值为16~32时,s的输出值为“LRL”。B正确。
8. 有如下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　　　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符合题意。
9. 有如下 Python 程序段:
a= [5,7,12,12,15,20,25,27]
low = 0; high = 7
key = int(input("key="))
while low <= high:
　　m = (low ＋ high)// 2
　　if a[m] >= key:
　　　　high = m － 1
　　else:
　　　　low = m ＋ 1
执行该程序段后,变量low的值为 2,则输入的值不可能是(　D　)
A. 10 B. 11
C. 12 D. 13
【解析】 由low值为3,得出结束时high值为 2,据判断条件 a[m]>=key 时 high=m － 1,由于a[low]10. 有如下Python程序段:
key = int(input())
s = 0; i = 0; j = 6
while i <= j:
　　m = (i ＋ j)//2
　　s = s ＋ m
　　if a[m] > key :
　　　j = m － 1
　　else:
　　　i = m ＋ 1
print(s)
已知列表a为[2,5,8,10,10,10,19], 执行该程序段,输入待查找数key,则输出的值不可能是(　C　)
A. 4 B. 6
C. 12 D. 14
【解析】 本题考查二分查找算法。本题可以采用二分查找法对二叉树直接进行分析。由于程序段的查找结构是二选一,相等时还会继续查找,直到i>j,所以查找任意一个值都会走到第三层下的叶子节点上,理论上有4条查找路径,其路径位置累加之和分别为4、6、12、14。但由于有3个相同的数据10,故12不可能,C符合题意。
11. 有如下Python程序段:
key = int(input())
i = 0; j = 9
while i <= j:
　　m = (i ＋ j)// 2
　　if a[m] < key:
　　　　i = m ＋ 1
　　else:
　　　　j = m － 1
列表a存放着非降序排列的数字,执行上述程序段后,下列说法中,错误的是(　C　)
A. a[i]可能大于key
B. a[i ＋ 1]可能等于key
C. a[j － 1]可能等于key
D. i可能等于10
【解析】 本题考查二分查找,其实质是二分答案(涉及边界条件和最优解)。根据循环条件可知,当循环结束时,i>j。而If语句的分支条件中,等于key值的分支由下标j指向,因此若a[m]=key时,j将一直向左移动,直到越过i指针(等于key值区域)为止。故若该序列中存在多个等于key值的数据,则i指向第一个等于key值数的下标,而j指针指向的数据值肯定小于key,C符合题意,B不符合题意(有序序列中值相同的数据肯定相邻)。而如果序列中不存在key值的数据,A不符合题意。如果key值大于序列中的所有值,则i的终值大于10,D不符合题意。
12. 某二分查找算法的Python程序段如下:
n=int(input());c=0;d=[1,2,3,4,5,6]
for k in range(0,len(d),n):
　　i=0;j=len(d)－1
　　key=d[k]
　　while i<=j:
　　　　m=(i＋j)//2
　　　　c＋=1
　　　　if key==d[m]:
　　　　 　break
　　　　elif key　　　　 　j=m－1
　　　　else:
　　　　 　i=m＋1
print(c)
执行程序段后,输入以下不同的n值,输出结果与其他三个不同的是(　C　)
A. 2 B. 3
C. 4 D. 5
【解析】 本题考查二分查找算法知识。c为查找次数的累加和。对应的二叉查找树及各选项的查找过程,如表所示:
选项 n m key c
A 2 0,2,4 1,3,5 2＋1＋2=5
B 3 0,3 1,4 2＋3=5
C 4 0,4 1,5 2＋2=4
D 5 0,5 1,6 2＋3=5
综上,C正确。
13. 某对分查找的Python程序段如下:
L = R = n = 0
i = 0; j = 7
key=int(input())
while i <= j:
　　n = n ＋ 1
　　m = (i ＋ j)// 2
　　if a[m] > key:
　　　　i = m ＋ 1; R = R ＋ 1
　　else:
　　　　j = m － 1; L = L ＋ 1
已知整数列表a为[92,84,81,76,69,53,24,5],程序执行后,下列说法中,正确的是(　D　)
A. i的值可能小于等于j
B. n的值一定是3
C. m的值可能为3
D. 可能出现L的值是1、R的值为3的情况
【解析】 本题考查对分查找的相关知识。本题考查二分查找的基本概念,可以先画出查找二叉树:
本题考查二分查找,由代码可知,找到并不退出,而是继续向左,查找任何数都是从叶子节点走出。退出循环时i>j,A错误。n为查找次数,从二叉树可以看出,向左找n=3,向右找n可能等于4,B错误。由于找到后并不退出而是从左子树的叶子节点走出,故退出后m不可能为3,C错误。若key=6,则查找方向是右右右左,从上图虚线处走出,即为L=1,R=3的情况,D正确。
14. 某二分查找算法的Python程序段如下:
#列表a存放整数升序数据,代码略
key=int(input())
f=[0]*9; i=0; j=8
while i<=j:
　　　m=(i＋j)//2
　　　f[m]=1
　　　if a[m]>key:
　　　　　j=m－1
　　　else:
　　　　　i=m＋1
print(f)
输入待查找数据key,执行该程序段后,下列选项中,列表f的值不可能是(　C　)
A. [0, 0, 0, 0, 1, 1, 1, 0, 0]
B. [1, 1, 0, 0, 1, 0, 0, 0, 0]
C. [0, 1, 0, 0, 1, 0, 1, 0, 0]
D. [0, 0, 0, 0, 1, 0, 1, 1, 0]
【解析】 本题考查对分查找算法。变量m是依次查找的下标索引值,第一次循环,m=4,f[4]=1,根据二叉树查找规则,往后查找只会在m=4的左边或右边进行查找,不会出现f[1]和f[6]同时为1的情况,C符合题意。
15. 有如下Python程序段:
a=[3,5,8,11,13,15,16,20,25,30]
i,j,x=0,9,20
while i<=j:
　　m=(i＋j)//2
　　if x==a[m]:
　　　　break
　　if x < a[m]:
　　　　j=m－1
　　else:
　　　　i=m＋1
该程序段运行后,下列表达式中,输出值为True的是(　C　)
A. i=m＋1 B. j=m－1
C. j>m＋1 D. i=m－1
【解析】 本题考查二分查找算法。该查找过程用二叉树表示,如图所示。当查找到20时,m=7,i=5,j=9,满足j>m＋1,C正确。(共33张PPT)
六、 查找算法及程序实现
第五章　数据结构与算法
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 某二分查找算法的Python程序段如下:
key = int(input())
s = "" ; i = 0 ; j = 9
while i<=j:
　　m = (i ＋ j)// 2:
　　if a[m] == key:
　　　　break
　　if key < a[m]:
　　　　j = m － 1 ; s = s ＋ "L"
　　else:
　　　　i = m ＋ 1 ; s = s ＋ "R"
若按非降序排序的整型列表a=[11,23,31,39,44,52,60,x,69,89],输入key值为66,执行
该程序段后,s值为“RRL”,则x的可能值的个数为(　　)
A. 3 B. 4
C. 5 D. 6
【解析】 本题考查二分查找知识。根据非降序排序(允许存在相同数据的升序序列)的整型列表可知, x的取值范围应该是60~69。再考虑到要查找的key值为66,执行该程序段后s值为"RRL",因此可以判断出查找的中值m的顺序分别为5、8、9,而x的位置是8,也就是说,以key=66为关键字进行第二次查找后继续右偏,这说明x的值肯定比66小(不可能等于66,若等于66则退出查找),因此可以将x的取值范围缩小为60~65之间的整数,即60、61、62、63、64、65这6个整数,D正确。
D
2. 某二分查找算法的Python程序段如下:
a=[12,14,15,15,17,18,20,20,23,25]
n=0
i=0
j=len(a)－1
k=int(input("请输入要查找的数"))
while i<=j:
　　m=(i＋j)//2
　　n=n＋1
　　if a[m]>k:
　　　　j=m－1
　　else:
　　　　i=m＋1
当输入的k值为20,程序运行结束后,下列说法中,错. 误. 的是(　　)
A. m的值是7 B. i的值是8
C. j的值是m－1 D. n的值是3
【解析】 本题考查二分查找。该二分查找算法程序中,找到key的时候不退出,而是继续往下查找,循环结束时,i=8,j=7,m=8,n=3,A符合题意。
A
3. 某二分查找算法的Python程序段如下:
f=[0]*9
key = int(input())
i = 0;j = 8
while i <= j:
　　　m = (i ＋ j)// 2
　　　f[m] = 1
　　　if a[m] == key:
　　　　　break
　　　elif a[m] > key:
　　　　　j = m － 1
　　　else:
　　　　　i = m ＋ 1
整型列表元素a[0]到a[8]为升序序列,输入待查找的数key,执行该程序段后,下列选项中,
f[0]到f[8]各元素值不. 可. 能. 的是(　　)
A. 1,1,0,0,1,0,0,0,0
B. 0,0,0,0,1,0,0,0,0
C. 0,0,0,0,1,1,1,1,0
D. 0,1,1,1,1,0,0,0,0
【解析】 本题考查二分查找算法。选项A可以查找的数key与列表元素a[0]相等、比列表元素a[0]小或者比列表元素a[0]大但比列表元素a[1]小的数,不符合题意。选项B要查找的key与列表元素a[4]相等,不符合题意。选项C查找完中间元素a[4]后,往右侧下一个要查找的中间元素是a[6],接下来要么比列表元素a[6]大,要么比列表元素a[6]小,所以a[5]与a[7]不可能都为1,符合题意。选项D可以查找的数key与列表元素a[3]相等、比列表元素a[3]大但比a[4]小或者比列表元素a[2]大但比列表元素a[3]小的数,不符合题意。
C
4. 某二分查找算法的Python程序段如下:
key = int(input())
s = ""
i = 0;j = 9
while i <= j:
　　m = (i ＋ j)// 2
　　s = s ＋ str(a[m])
　　if a[m] > key:
　　　　j = m － 1
　　else:
　　　　i = m ＋ 1
print(s)
列表元素a[0]到a[9]的值依次为“2,3,5,8,9,10,13,17,19,20”。输入待查找的数key,
执行该程序段,则s显示的内容可能是(　　)
A. 9　3 B. 9　3　5
C. 9　17　19　13 D. 9　3　5　8　19
【解析】 本题考查二分查找。由代码可知,查找到数据key后不退出,直到满足条件i>j才退出循环。由于3个选项都涉及9和3,因此可以先检查左半区。第一次循环,m=4,查找到数据“9”;若key值小于9,则更新j的值为3,此时m=1,查找到数据“3”;若key值大于3,则更新i=2,下一次查找m=2,查找到数据“5”;若key值小于5,则下一次查找更新j=1,此时i > j,循环终止,因此字符串s记录的值为“9 3 5”,B正确。因为此时i<=j,循环还要继续进行,A错误。9 、17、19后面不可能出现13,C错误。当数据量n为10时,最多查找4次就会退出,D错误。
B
5. 某二分查找算法的 Python 程序段如下:
i = 0; j =9; c = 0
key = int(input())
while i <= j:
　　m = (i ＋ j)// 2
　　c = c ＋ 1
　　if key < a[m]:
　　　　j = m － 1 　
　　else:
　　　　i = m ＋ 1
print(j)
已知列表a为[1,5,5,7,9,9,9,11,16,18],下列说法中,错. 误. 的是(　　)
A. 若输入10,程序运行后输出的值j是6
B. 程序运行后,a[i]的值可能等于key
C. 程序的功能是输出列表中最后一个小于等于key的元素所在的位置
D. 对于不同的输入值key,程序运行后c的值一定大于2
【解析】 本题考查二分查找中key值的边界问题。核心问题是确定二分结束时的区间变量i、j的位置,即查找key的边界问题。通过模拟可以发现本题程序查询key值的右边界,二分结束时j ＋ 1=i,所以输出j的含义为“小于等于key的元素个数”,即“最后一个小于等于key的元素位置”,C不符合题意。同理,当key=10时,j=6,A不符合题意。而变量i的位置在j之后,变量i的含义是“大于key的最小值的位置”,a[i]的值不可能等于key,而a[j]的值可能等于key,B符合题意。通过模拟可知,10个元素的二叉查找树深度为4,不可能在第2层结束,查找次数肯定大于等于3,最多查找4次,D不符合题意。
B
6. 有如下Python程序段:
a=[5,6,18,22,27,28,55,70,80]
i = 0; j = 8; f = False
L = 0; R = 0
key = int(input())
while i <= j and f == False:
　　m = (i ＋ j)// 2
　　if key == a[m]:
　　　　f = True
　　if key < a[m]:
　　　　j = m － 1; L = L ＋ 1
　　else:
　　　　i = m ＋ 1; R = R ＋ 1
程序运行后,L、R的值分别为2、1,则输入的关键字key可能是(　　)
A. 5 B. 6
C. 18 D. 28
【解析】 本题考查二叉树。由于找到key值之后f=False,因此查询成功后不会立即跳出,而是在查询成功后会多一次偏移。key=5则L=2,R=1;key=6则L=1,R=1;key=18则L=1,R=2;key=28则L=1,R=2。A正确。
A
7. 有如下Python程序段:
key = int(input()); s=""
i,j = 0,len(a)－1
while i<=j:
　　m = (i＋j)//2
　　if a[m]　　　　i = m ＋ 1
　　　　s = s ＋ "R"
　　else:
　　　　j = m － 1
　　　　s = s ＋ "L"
print(s)
已知数组a的值为[10,15,32,32,45,53,53,65,77,98],程序运行后,变量s的值可能是
(　　)
A. LR B. LRL
C. LRR D. RLR
【解析】 本题考查二分查找算法。由代码可知,本题找到key值后并不退出。模拟后可知当输入的key值为16~32时,s的输出值为“LRL”。B正确。
B
8. 有如下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　　　j=m－1
　　else:
　　　　i=m＋1
数组a中的元素为“58,69,78,80,83,84,90,90,95”,则执行该程序段后,数组s中的元素
不. 可. 能. 为(　　)
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符合题意。
D
关键能力练
9. 有如下 Python 程序段:
a= [5,7,12,12,15,20,25,27]
low = 0; high = 7
key = int(input("key="))
while low <= high:
　　m = (low ＋ high)// 2
　　if a[m] >= key:
　　　　high = m － 1
　　else:
　　　　low = m ＋ 1
执行该程序段后,变量low的值为 2,则输入的值不. 可. 能. 是(　　)
A. 10 B. 11
C. 12 D. 13
【解析】 由low值为3,得出结束时high值为 2,据判断条件 a[m]>=key 时 high=m － 1,由于a[low]D
10. 有如下Python程序段:
key = int(input())
s = 0; i = 0; j = 6
while i <= j:
　　m = (i ＋ j)//2
　　s = s ＋ m
　　if a[m] > key :
　　　j = m － 1
　　else:
　　　i = m ＋ 1
print(s)
已知列表a为[2,5,8,10,10,10,19], 执行该程序段,输入待查找数key,则输出的值不. 可. 能. 是(　　)
A. 4 B. 6
C. 12 D. 14
【解析】 本题考查二分查找算法。本题可以采用二分查找法对二叉树直接进行分析。由于程序段的查找结构是二选一,相等时还会继续查找,直到i>j,所以查找任意一个值都会走到第三层下的叶子节点上,理论上有4条查找路径,其路径位置累加之和分别为4、6、12、14。但由于有3个相同的数据10,故12不可能,C符合题意。
C
11. 有如下Python程序段:
key = int(input())
i = 0; j = 9
while i <= j:
　　m = (i ＋ j)// 2
　　if a[m] < key:
　　　　i = m ＋ 1
　　else:
　　　　j = m － 1
列表a存放着非降序排列的数字,执行上述程序段后,下列说法中,错. 误. 的是(　　)
A. a[i]可能大于key B. a[i ＋ 1]可能等于key
C. a[j － 1]可能等于key D. i可能等于10
【解析】 本题考查二分查找,其实质是二分答案(涉及边界条件和最优解)。根据循环条件可知,当循环结束时,i>j。而If语句的分支条件中,等于key值的分支由下标j指向,因此若a[m]=key时,j将一直向左移动,直到越过i指针(等于key值区域)为止。故若该序列中存在多个等于key值的数据,则i指向第一个等于key值数的下标,而j指针指向的数据值肯定小于key,C符合题意,B不符合题意(有序序列中值相同的数据肯定相邻)。而如果序列中不存在key值的数据,A不符合题意。如果key值大于序列中的所有值,则i的终值大于10,D不符合题意。
C
12. 某二分查找算法的Python程序段如下:
n=int(input());c=0;d=[1,2,3,4,5,6]
for k in range(0,len(d),n):
　　i=0;j=len(d)－1
　　key=d[k]
　　while i<=j:
　　　　m=(i＋j)//2
　　　　c＋=1
　　　　if key==d[m]:
　　　　 　break
　　　　elif key　　　　 　j=m－1
　　　　else:
　　　　 　i=m＋1
print(c)
执行程序段后,输入以下不同的n值,输出结果与其他三个不同的是(　　)
A. 2 B. 3
C. 4 D. 5
【解析】 本题考查二分查找算法知识。c为查找次数的累加和。对应的二叉查找树及各选项的查找过程,如表所示:
选项 n m key c
A 2 0,2,4 1,3,5 2＋1＋2=5 B 3 0,3 1,4 2＋3=5 C 4 0,4 1,5 2＋2=4 D 5 0,5 1,6 2＋3=5 综上,C正确。
C
13. 某对分查找的Python程序段如下:
L = R = n = 0
i = 0; j = 7
key=int(input())
while i <= j:
　　n = n ＋ 1
　　m = (i ＋ j)// 2
　　if a[m] > key:
　　　　i = m ＋ 1; R = R ＋ 1
　　else:
　　　　j = m － 1; L = L ＋ 1
已知整数列表a为[92,84,81,76,69,53,24,5],程序执行后,下列说法中,正确的是(　　)
A. i的值可能小于等于j B. n的值一定是3
C. m的值可能为3 D. 可能出现L的值是1、R的值为3的情况
【解析】 本题考查对分查找的相关知识。本题考查二分查找
的基本概念,可以先画出查找二叉树:
本题考查二分查找,由代码可知,找到并不退出,而是继续向左,
查找任何数都是从叶子节点走出。退出循环时i>j,A错误。
n为查找次数,从二叉树可以看出,向左找n=3,向右找n可能等
于4,B错误。由于找到后并不退出而是从左子树的叶子节点走
出,故退出后m不可能为3,C错误。若key=6,则查找方向是右
右右左,从上图虚线处走出,即为L=1,R=3的情况,D正确。
D
14. 某二分查找算法的Python程序段如下:
#列表a存放整数升序数据,代码略
key=int(input())
f=[0]*9; i=0; j=8
while i<=j:
　　　m=(i＋j)//2
　　　f[m]=1
　　　if a[m]>key:
　　　　　j=m－1
　　　else:
　　　　　i=m＋1
print(f)
输入待查找数据key,执行该程序段后,下列选项中,列表f的值不. 可. 能. 是(　　)
A. [0, 0, 0, 0, 1, 1, 1, 0, 0]
B. [1, 1, 0, 0, 1, 0, 0, 0, 0]
C. [0, 1, 0, 0, 1, 0, 1, 0, 0]
D. [0, 0, 0, 0, 1, 0, 1, 1, 0]
【解析】 本题考查对分查找算法。变量m是依次查找的下标索引值,第一次循环, m=4,f[4]=1,根据二叉树查找规则,往后查找只会在m=4的左边或右边进行查找,不会出现f[1]和f[6]同时为1的情况,C符合题意。
C
15. 有如下Python程序段:
a=[3,5,8,11,13,15,16,20,25,30]
i,j,x=0,9,20
while i<=j:
　　m=(i＋j)//2
　　if x==a[m]:
　　　　break
　　if x < a[m]:
　　　　j=m－1
　　else:
　　　　i=m＋1
该程序段运行后,下列表达式中,输出值为True的是(　　)
A. i=m＋1 B. j=m－1
C. j>m＋1 D. i=m－1
【解析】 本题考查二分查找算法。该查找过程用二叉树表示,如图所示。当查找到20时,m=7,i=5,j=9,满足j>m＋1,C正确。
C

展开更多......

收起↑