数据结构基础知识07.-高考信息技术一轮二轮复习数据结构基础知识（浙教版2019）

数据结构基础知识（七）【知识要点】1.查找的概念和基本方法（1）查找的概念：查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象值本身。查找是一种查询数据的技术，其目标是能以较少的步骤或在较短的时间内找到所需的对象。程序将按照查找的结果（找到或未找到）来决定接下来应执行的步骤。（2）查找的基本方法：查找的方法很多，对不同的数据结构有不同的查找方法。例如，对已排好序的数据序列，可采用对分查找；对树形结构数据，可采用树形查找；无论数据序列是否有序，都可采用顺序查找。2.顺序查找算法的基本思想顺序查找的基本思想是从第一个数据开始，按顺序逐个将数据与给定的数据（查找键）进行比较，若某个数据和查找键相等，则查找成功，输出所查数据的位置；反之，输出未找到。3.顺序查找算法的代码实现（1）顺序查找本质上是一种枚举算法思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。（2）假设n个数据依次存储在长度为n的数组a中，查找键为key，自定义函seq_search(a,key)返回数组a中首个值为key的元素下标，若找不到key则返回1defseq_search(a,key):foriinrange(len(a)):ifa[i]==key:returnielse:return14.二分查找算法的基本思想（1）二分查找又称对分查找，是一种效率很高的查找方法但被查找的数据序列必须是有序的。（2）首先将查找键与有序数组内处于中间位置的元素进行比较，如果二者相等，则查找成功；否则根据数组元素的有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法进行查找，直到查找成功或确定找不到（查找空间为空）。5.二分查找算法的代码实现（1）假设n个递增数据依次存储在长度为n的数组a中，查找键为key，自定义函数binary_search(a,key)返回数组a中某个值为key的元素下标，若找不到key则返回1。defbinary_search(a,key):L,R=O,len(a)1whileL<=R:m=(L+R)//2#左偏#m=(L+R+1)//2#右偏也可ifkey==a[m]:returnmelifkey<a[m]:R=m1else:L=m+1return1(2)二分查找算法也可以使用递归函数bsearch(a,L,R,key)来实现,其中L和R分别表示查找区间的左、右边界,参考代码如下:defbscarch(a,L,R,key):ifL>R:returnlm=(L+R)//2#左偏#m=(L+R+1)//2#右偏也可ifkey==a[m]:returnmelifkey<a[m]:returnbsearch(a,L,m1,key)else:returnbsearch(a,m+1,R,key)6.二分查找最优解问题（1）问题特征被查找的数据（满足条件的解）必须是有序的；不仅仅要找到满足条件的解，而且要找到最优解，因此不能中途跳出循环，而是要等到循环正常结束后才能确认找到的解为最优解。根据最优解在序列中的位置，可分为查找满足条件的最小值或最大值问题。（2）基本模型①已知数组a[0:n]为非递减有序序列，输出第一个不小于key的元素下标，若a[n1]<key，则输出n。可推广到求满足条件的最小值问题。②已知数组a[0:n]为非递减有序序列，输出最后一个不大于key的元素下标，若a[0]>key，则输出1。可推广到求满足条件的最大值问题。7.二叉排序树（1）二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。（2）二叉排序树的特性①若它的左子树非空，则左子树上所有节点的值均小于它的根节点的值。②若它的右子树非空，则右子树上所有节点的值均大于它的根节点的值。③左，右子树本身又各是一棵二叉排序树。（3）典型的二叉排序树图示在该二叉排序树的基础上插入数据值为6的新节点,则得到新的二叉排序树如图。【例题剖析】例1：在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据20，共需查找的次数为()A.5次B.6次C.7次 D.8次答案B解析本题主要考查的是顺序查找的算法思想。20位于数组d中第6个位置(索引号为5)，因此共查找6次，答案为B。例2.有如下Python程序段：d＝[3，9，1，2，6，9，0]n＝len(d)key＝int(input("pleaseinputkey："))flag＝Truei＝0whilei<＝n－1andflag：ifkey＝＝d[i]：pos＝iflag＝Falseelse：i＝i＋1ifi＝＝n：print("未找到")else：print("找到，索引位置："，pos)程序运行时，输入key的值为9，输出结果为()A.未找到B.找到，索引位置：1C.找到，索引位置：5 D.找到，索引位置：15答案B解析本题主要考查的是顺序查找的程序实现。本程序的功能是只找到第一个满足条件的值就结束查找，即找到第1个9时(索引位置为1)就结束查找，因此，答案为B。例3.有100个英语单词已按升序排序并存储在列表Listb中，现要使用二分查找算法在列表listb中查找某个单词，则最多的查找次数为()A.5次B.6次C.7次 D.8次答案C解析本题主要考查的计算二分查找的查找次数。N个数据，使用二分查找，查找次数最多为log2(n)取整加1，现共有100个单词，因此最多次数为7次，答案为C。例4.某二分查找算法的Python程序段如下：b＝[98，86，81，77，66，60，48，20]key＝int(input("key＝"))i，j＝0，len(b)－1s＝""whilei<＝j：m＝(i＋j)//2ifb[m]＝＝key：s＝s＋"M"breakifkey<b[m]：i＝m＋1s＝s＋"R"else：j＝m－1s＝s＋"L"print(s)程序执行时，输入key的值为55，则输出的结果为()A.RRLB.RLRC.RRLR D.RRLM答案A解析：本题主要考查的是二分查找时方向问题。本题的功能是求使用二分查找在降序序列中查找数据55的过程，如果找到，则记为“M”，如果要查找的数据在序列的右边区间中，则记为“R”，否则记录为“L”。【习题巩固】1.在数组d中存储的数据依次为"if"，"for"，"range"，"while"，"def"，"True"，"False"，"print"，"input"。现使用顺序查找算法在数组d中查找数据"false"，共需查找的次数为()A.0次B.7次C.9次 D.10次2..有如下python程序段：d＝["len"，"str"，"abs"，"chr"，"min"，"ord"，"int"，"max"]n＝len(d)key＝input("pleaseinputkey：")ans＝0i＝0s＝""whilei<＝n－1：ifd[i]>key：s＝s＋str(i)i＝i＋1print(s)程序运行时，输入float，输出结果为()A.12567B.125678C.014567 D.01456783.某对分查找算法的Python程序段如下：a＝[85，74，70，65，54，36，30，28，26，12]t＝""i，j＝0，9key＝30f＝Falsewhilei<＝jandnotf：m＝(i＋j)//2t＋＝str(m)ifa[m]＝＝key：f＝Trueelifa[m]>key：i＝m＋1t＝t＋"→"else：j＝m－1t＝t＋"←"执行该程序段，变量t的值是()A."4→7←5→"B."4→7←5→6→"C."4→7←5→6" D."4→7→5→6→"4.某二分查找算法的Python程序段如下：list1＝['Carrot','Celery','Garlic','Lettuce','Mooli','Onion','Potato','Tomato']key＝list1[2]left，right＝0，len(list1)－1c＝0whileleft<＝right：m＝(left＋right)//2c＝c＋1iflist1[m]>key：right＝m－1else：left＝m＋1print(list1[left])程序执行后，下列说法正确的是()A.变量c的值为4B.程序输出的结果为LettuceC.变量left的值为2D.变量right的值为35.有如下Python程序段:k,p=5,0foriinrange(1,len(a)):ifa[i]>kanda[i]<=a[p]:p=i若数组a=[9,3,5,6,8,4,6],运行该段代码后,变量p的值为()A.0B.3C.6D.76.有如下Python程序段:p,q=0,1ifa[p]<a[q]:P,q=q,pforiinrange(2,len(a)):ifa[i]>a[p]:q=pp=ielifa[i]>a[q]:q=i则当a=[9,1,6,8,7,4]时,变量p和q的值分别为()A.9和8B.8和9C.3和0D.0和37.有一个由4000个整数构成的顺序表,假定表中的元素已经按升序排列,采用二分查找算法定位一个元素。若要确定是否存在所查找的元素,则需要比较的次数最多是()A.11次B.12次C.13次D.14次8.某数组元素a[0]到a[9]中,其数据依次为89,81,74,66,53,40,32,21,14,3。使用二分查找,设定查找键key,若第二个被访问到的数据为74,则第三个被访问到的数据是()A.81或53B.89或40C.21或3D.81或669.某二分查找算法的Python程序段如下:a=[8,17,24,30,36,40,55,58,61,66]key=int(input("请输人要查找的数据:"))i.j=0,9res=[]whilei<=j:m=(i+j+1)//2ifkey==a[m]:breakelifkey<a[m]:j=m1else:i=m+1res.append(a[m])print(res)执行该程序段,当输入的值为30时,程序输出结果为()A.[40,24]B.[40,24,36]C.[24,36]D.[36,17,24]10某二分查找算法的Python程序段如下:importrandoma=[2,5,8,14,17,23,25]key=random.randint(1,30)i,j=0,6whilei<=j:m=(i+j)//2ifkey==a[m]:breakelifkey<a[m]:j=m1else:i=m+1运行上述程序段后﹐下列条件表达式肯定不成立的是()A.ij=0B.ij=1C.ij=2D.ji=211.某二分查找算法的Python程序段如下:d=[11,19,25,33,47,58]i=0;j=5f=Falsekey=int(input("key="))whilei<=jandf==False:m=(i+j)//2ifkey==d[m]:f=Trueifkey<d[m]:j=m1else:i=m+1运行该程序后输入key值为“33”,运行结束后下列说法不正确的是()A.变量f的值为TrueB.变量i的值为4C.变量j的值为4D.变量m的值为312.有Python程序段如下:importrandomkey=random.randint(0,99)+0.5i=0;j=7;k=0whilei<=j:m=(i+j)//2ifkey==a[m]:breakelifkey<a[m]:j=m1k=k1else:i=m+1k=k+1print(str(k))列表a=[3,18,20,24,45,56,67,88],执行该程序段后,输出的值不可能是()A.3,1B.1,1C.1,2D.2,313.某二分查找算法的Python程序段如下:importrandomkey=random.randint(0,49)*2+1s=0;i=0;j=9whilei<=j:m=(i+j)//2ifkey=a[m]:breakelifkey<a[m]:j=m1s=2*selse:i=m+1s=2*s+1print(s)列表a=[2,6,7,15,20,24,27,43,52,63],执行该程序段后,s的值不可能为()A.2B.3C.5D.1514.某二分查找算法的Python程序段如下:i,j=0,6;flag=False;n=0whilei<=jandnotflag:m=(i+j)//2ifkey==a[m]:flag=Trueelifkey<a[m]:j=m1else:i=m+1n+=1已知列表a=[3,12,30,46,69,72,84],key的值为84。则该程序段执行后,下列表达式正确的是()A.i=5B.j=i+1C.m=6D.n=215.某Python程序段如下:a=[88,83,78,62,60,58,51,41,32,26]b=[];i=0;j=9;flag=Falsekey=int(input("key="))whilei<=jandnotflag:m=(i+j+1)//2b.append(a[m])ifa[m]==key:flag=Trueelifa[m]<key:j=m1else:i=m+1print(b)执行程序后,当输入的key值为83时,输出的结果是()A.[58,83]B.[58,78,83]C.[58,62,83]D.[60,78,83]16.有如下Python程序段:importrandoma=[5,22,31,36,45,49,62,78,83,90]s="";flag=False;i=0;j=9key=random.randint(1,100)whilei<=jandflag==False:m=(i+j)//2ifkey==a[m]:s=s+"M"flag=Trueifkey<a[m]:j=m1;s=s+"L"else:i=m+1;s=s+"R"print(s)执行程序后,输出的结果不可能是()A.LLRRB.RLRMC.LRLD.M17．有如下Python程序段k=int(input());s=""left,right=0,len(a)1whileleft<=right:m=(left+right)//2ifa[m]<k:left=m+1;s=s+"R"else:right=m1;s=s+"L"已知数组a中的值为[10,15,32,32,45,53,53,65,77,98]，程序运行后，变量s的值可能是A."LR"B."LRL"C."LRR"D."RLR"18.某二分查找算法的Python程序段如下：a=[14,17,18,19,19,22,22,22,28,28]s=0key=int(input("key:"))L,R=0,len(a)1whileL<=R:m=(L+R)//2s+=1ifa[m]>key:R=m1else:L=m+1当输入key的值为22，程序运行结束后，下列描述不正确的是()A.m的值是7B.s的值是3C.L的值是8D.R的值是719.有如下Python程序段：a=[99,85,74,68,53,42,34,27,20,13]key=int(input("请输入一个整数："))i,j,k,c,flag=0,9,0,"N",Falsewhilei<=jandflag==False:m=(i+j+1)//2k=k+1ifkey==a[m]:c="Y"flag=Trueifkey>a[m]:j=m1else:i=m+1print(c,k)执行该程序段后，下列说法正确的是A．该程序段既能用于升序序列的查找，也能用于降序序列的查找B．若输出k的值为2，则c的值一定为YC．若输入key的值为74，程序执行后变量i和j的值分别为0和4D．输入两位任意正整数，k的值介于1和3之间20．某Python程序如下：importrandomkey=random.randint(35,45)*2i=0;j=len(a)1;s=[]whilei<=j:m=(i+j+1)//2s.append(a[m])ifkey<a[m]:j=m1else: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,5821.某算法的python程序段如下:key=randint(0,3)*2+13i,j,c=0,len(a)1,0whilei<=j:m=(i+j+1)//2ifa[m]>=key: i=m+1else: j=m1c+=1列表a=[23,21,19,18,16,15,14,11]，该程序段执行后，下列说法不正确的是A.i的值为j+1B.i的值可能是8C.j的值可能是5D.c的值一定是322.下列Python程序段功能为:在非降序排序列表L中，采用二分查找的方式查找某数值，若能找到则输出该数值在列表L中的起始和结束位置，否则输出“未找到”。key=int(input("key="))i=0;j=9whilei<=j:m=(i+j)//2if___①______:j=m1else:i=m+1ifL[j]!=key:print("找不到")else:sl=jwhilekey==L[j]andj>=1:j=j1______②_________print(str(s2),"",str(sl))以上两空中填入的正确代码为A.①key<L[m]②s2=jB.①key<L[m]②s2=j+1C.①key<=L[m]②s2=jD.①key<=L[m]②s2=j23.如下Python程序段：importrandomasrda=[10,11,13,16,16,21]key=rd.randint(11,16)i,j=0,len(a)1;c=1whilei<=j:m=(i+j)//2ifkey>a[m]:i=m+1c=c+1else:j=m1c=2*c上述程序执行完以后，c的值有多少种可能？()A.1 B.2 C.3 D.424．某二分查找算法的Python程序段如下：importrandomkey=random.randint(0,4)*2+5n=10;ans=0;i=0;j=n1a=[4,5,5,8,9,11,11,13,15,17]whilei<=j:m=(i+j)//2ifa[m]<=key:i=m+1else:j=m1ans+=a[m]print(ans)执行该程序段后，ans的值不可能是A．19 B．27 C．37 D．4425.有Python代码如下p=[1,25,36,49,64,71,73,77,84,90]t=i=0;j=len(p)key=int(input())whilei<j:m=(i+j)//2ifp[m]==key:breakelifp[m]>key:j=melse:i=m+1t+=1print(t)若输入的key必定是列表p中的元素，且输出的结果为3，则输入的key不可能为（）A.1 B.49 C.64 D.7326.数组a中存储的是左右交替上升的n个正整数，如下表表示：a[0]a[1]a[2]…a[n－3]a[n－2]a[n－1]2815…23105依据二分查找思想在数组a中查找数据key，实现程序如下，请在划线处填入合适的代码。n＝len(a)－1key＝int(input(″请输入待查数据：″))i＝0；j＝n//2；flag＝Falsewhile____①____：m＝(i＋j)//2ifkey＝＝a[m]：flag＝Trueelif____②____：j＝m－1else：i＝m＋1ifnotflagandj>＝0：____③____ifkey＝＝a[m]：flag＝Trueifflag：print(″数组元素a[″＋str(m)＋″]即为所求！″)else：print(″未找到″)27.列表a中存储了若千个各不相同且无序的整数,为了在列表a中查找第k大(1≤k≤n)的整数,李阳借鉴二分查找的思想,编写的Python程序段如下,请在程序划线处填入合适的代码。k=int(input("请输入k:"))low=high=a[0]foriinrange(1,n):ifa[i]<low:low=a[i]ifa[i]>high:high=a[i]while①:m=(low+high)//2cnt=0foriinrange(O,n):ifa[i]>m:②ifcnt>=k:③else:high=mprint("第k大的整数是:",high)28.编写Python程序,实现在一个升序排列的列表中查找绝对值最小的元素。已知列表元素由正数、负数或0构成。例如:列表中元素为[80,65,55,40,20,4,5,8,10,15,20,30],该数组中绝对值最小的数为4。程序运行示例如下图所示。defdmin(x,y):ifabs(x)<abs(y):dmin=xelse:dmin=yreturndmin#生成n个由正数、负数或0,存储在列表a中,并升序排列,代码略a=[80,65,55,40,20,4,5,8,10,15,20,30]n=len(a);flag=False;i=0;j=n1whilei<=j:m=(i+j)//2ifa[m]==0:①absmin=a[m]breakelifa[m]>0:if②:j=m1else:flag=Trueabsmin=dmin(a[m1],a[m])else:ifa[m+1]<0:i=m+1else: