數(shù)據(jù)結(jié)構(gòu)基礎知識07.-高考信息技術一輪二輪復習數(shù)據(jù)結(jié)構(gòu)基礎知識（浙教版2019）

數(shù)據(jù)結(jié)構(gòu)基礎知識（七）【知識要點】1.查找的概念和基本方法（1）查找的概念：查找又稱檢索，計算機根據(jù)所給條件查找出滿足條件的對象，即在存儲的一批數(shù)據(jù)內(nèi)尋找出一個特定的數(shù)據(jù)，或者確定在該批數(shù)據(jù)內(nèi)是否存在這樣的數(shù)據(jù)。若沒有找到滿足條件的對象，則返回特定值，表明查找失??；若查找到滿足條件的對象，則表明查找成功，一般要求返回該對象的存儲位置或?qū)ο笾当旧?。查找是一種查詢數(shù)據(jù)的技術，其目標是能以較少的步驟或在較短的時間內(nèi)找到所需的對象。程序?qū)凑詹檎业慕Y(jié)果（找到或未找到）來決定接下來應執(zhí)行的步驟。（2）查找的基本方法：查找的方法很多，對不同的數(shù)據(jù)結(jié)構(gòu)有不同的查找方法。例如，對已排好序的數(shù)據(jù)序列，可采用對分查找；對樹形結(jié)構(gòu)數(shù)據(jù)，可采用樹形查找；無論數(shù)據(jù)序列是否有序，都可采用順序查找。2.順序查找算法的基本思想順序查找的基本思想是從第一個數(shù)據(jù)開始，按順序逐個將數(shù)據(jù)與給定的數(shù)據(jù)（查找鍵）進行比較，若某個數(shù)據(jù)和查找鍵相等，則查找成功，輸出所查數(shù)據(jù)的位置；反之，輸出未找到。3.順序查找算法的代碼實現(xiàn)（1）順序查找本質(zhì)上是一種枚舉算法思想，順序查找程序就是用循環(huán)來枚舉所有要查找的對象，然后在循環(huán)體內(nèi)用條件判斷當前枚舉出的對象是否等于查找對象。（2）假設n個數(shù)據(jù)依次存儲在長度為n的數(shù)組a中，查找鍵為key，自定義函seq_search(a,key)返回數(shù)組a中首個值為key的元素下標，若找不到key則返回1defseq_search(a,key):foriinrange(len(a)):ifa[i]==key:returnielse:return14.二分查找算法的基本思想（1）二分查找又稱對分查找，是一種效率很高的查找方法但被查找的數(shù)據(jù)序列必須是有序的。（2）首先將查找鍵與有序數(shù)組內(nèi)處于中間位置的元素進行比較，如果二者相等，則查找成功；否則根據(jù)數(shù)組元素的有序性，確定應該在數(shù)組的前半部分還是后半部分繼續(xù)查找。在新確定的范圍內(nèi)，繼續(xù)按上述方法進行查找，直到查找成功或確定找不到（查找空間為空）。5.二分查找算法的代碼實現(xiàn)（1）假設n個遞增數(shù)據(jù)依次存儲在長度為n的數(shù)組a中，查找鍵為key，自定義函數(shù)binary_search(a,key)返回數(shù)組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)二分查找算法也可以使用遞歸函數(shù)bsearch(a,L,R,key)來實現(xiàn),其中L和R分別表示查找區(qū)間的左、右邊界,參考代碼如下: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.二分查找最優(yōu)解問題（1）問題特征被查找的數(shù)據(jù)（滿足條件的解）必須是有序的；不僅僅要找到滿足條件的解，而且要找到最優(yōu)解，因此不能中途跳出循環(huán)，而是要等到循環(huán)正常結(jié)束后才能確認找到的解為最優(yōu)解。根據(jù)最優(yōu)解在序列中的位置，可分為查找滿足條件的最小值或最大值問題。（2）基本模型①已知數(shù)組a[0:n]為非遞減有序序列，輸出第一個不小于key的元素下標，若a[n1]<key，則輸出n?？赏茝V到求滿足條件的最小值問題。②已知數(shù)組a[0:n]為非遞減有序序列，輸出最后一個不大于key的元素下標，若a[0]>key，則輸出1?？赏茝V到求滿足條件的最大值問題。7.二叉排序樹（1）二叉排序樹也稱為二叉查找樹，這種結(jié)構(gòu)的二叉樹既能實現(xiàn)排序功能，也能實現(xiàn)查找功能。（2）二叉排序樹的特性①若它的左子樹非空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值。②若它的右子樹非空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值。③左，右子樹本身又各是一棵二叉排序樹。（3）典型的二叉排序樹圖示在該二叉排序樹的基礎上插入數(shù)據(jù)值為6的新節(jié)點,則得到新的二叉排序樹如圖?！纠}剖析】例1：在數(shù)組a中存儲的數(shù)據(jù)依次為“3，6，5，11，15，20，13，32”。現(xiàn)使用順序查找算法在數(shù)組a中查找數(shù)據(jù)20，共需查找的次數(shù)為()A.5次B.6次C.7次 D.8次答案B解析本題主要考查的是順序查找的算法思想。20位于數(shù)組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，輸出結(jié)果為()A.未找到B.找到，索引位置：1C.找到，索引位置：5 D.找到，索引位置：15答案B解析本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本程序的功能是只找到第一個滿足條件的值就結(jié)束查找，即找到第1個9時(索引位置為1)就結(jié)束查找，因此，答案為B。例3.有100個英語單詞已按升序排序并存儲在列表Listb中，現(xiàn)要使用二分查找算法在列表listb中查找某個單詞，則最多的查找次數(shù)為()A.5次B.6次C.7次 D.8次答案C解析本題主要考查的計算二分查找的查找次數(shù)。N個數(shù)據(jù)，使用二分查找，查找次數(shù)最多為log2(n)取整加1，現(xiàn)共有100個單詞，因此最多次數(shù)為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)程序執(zhí)行時，輸入key的值為55，則輸出的結(jié)果為()A.RRLB.RLRC.RRLR D.RRLM答案A解析：本題主要考查的是二分查找時方向問題。本題的功能是求使用二分查找在降序序列中查找數(shù)據(jù)55的過程，如果找到，則記為“M”，如果要查找的數(shù)據(jù)在序列的右邊區(qū)間中，則記為“R”，否則記錄為“L”?！玖曨}鞏固】1.在數(shù)組d中存儲的數(shù)據(jù)依次為"if"，"for"，"range"，"while"，"def"，"True"，"False"，"print"，"input"?，F(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)"false"，共需查找的次數(shù)為()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，輸出結(jié)果為()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＋"←"執(zhí)行該程序段，變量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])程序執(zhí)行后，下列說法正確的是()A.變量c的值為4B.程序輸出的結(jié)果為LettuceC.變量left的值為2D.變量right的值為35.有如下Python程序段:k,p=5,0foriinrange(1,len(a)):ifa[i]>kanda[i]<=a[p]:p=i若數(shù)組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個整數(shù)構(gòu)成的順序表,假定表中的元素已經(jīng)按升序排列,采用二分查找算法定位一個元素。若要確定是否存在所查找的元素,則需要比較的次數(shù)最多是()A.11次B.12次C.13次D.14次8.某數(shù)組元素a[0]到a[9]中,其數(shù)據(jù)依次為89,81,74,66,53,40,32,21,14,3。使用二分查找,設定查找鍵key,若第二個被訪問到的數(shù)據(jù)為74,則第三個被訪問到的數(shù)據(jù)是()A.81或53B.89或40C.21或3D.81或669.某二分查找算法的Python程序段如下:a=[8,17,24,30,36,40,55,58,61,66]key=int(input("請輸人要查找的數(shù)據(jù):"))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)執(zhí)行該程序段,當輸入的值為30時,程序輸出結(jié)果為()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”,運行結(jié)束后下列說法不正確的是()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],執(zhí)行該程序段后,輸出的值不可能是()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],執(zhí)行該程序段后,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。則該程序段執(zhí)行后,下列表達式正確的是()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)執(zhí)行程序后,當輸入的key值為83時,輸出的結(jié)果是()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)執(zhí)行程序后,輸出的結(jié)果不可能是()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"已知數(shù)組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，程序運行結(jié)束后，下列描述不正確的是()A.m的值是7B.s的值是3C.L的值是8D.R的值是719.有如下Python程序段：a=[99,85,74,68,53,42,34,27,20,13]key=int(input("請輸入一個整數(shù)："))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)執(zhí)行該程序段后，下列說法正確的是A．該程序段既能用于升序序列的查找，也能用于降序序列的查找B．若輸出k的值為2，則c的值一定為YC．若輸入key的值為74，程序執(zhí)行后變量i和j的值分別為0和4D．輸入兩位任意正整數(shù)，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數(shù)組a中的元素為“58,69,78,80,83,84,90,90,95”，則執(zhí)行該程序段后，數(shù)組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]，該程序段執(zhí)行后，下列說法不正確的是A.i的值為j+1B.i的值可能是8C.j的值可能是5D.c的值一定是322.下列Python程序段功能為:在非降序排序列表L中，采用二分查找的方式查找某數(shù)值，若能找到則輸出該數(shù)值在列表L中的起始和結(jié)束位置，否則輸出“未找到”。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上述程序執(zhí)行完以后，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)執(zhí)行該程序段后，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中的元素，且輸出的結(jié)果為3，則輸入的key不可能為（）A.1 B.49 C.64 D.7326.數(shù)組a中存儲的是左右交替上升的n個正整數(shù)，如下表表示：a[0]a[1]a[2]…a[n－3]a[n－2]a[n－1]2815…23105依據(jù)二分查找思想在數(shù)組a中查找數(shù)據(jù)key，實現(xiàn)程序如下，請在劃線處填入合適的代碼。n＝len(a)－1key＝int(input(″請輸入待查數(shù)據(jù)：″))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(″數(shù)組元素a[″＋str(m)＋″]即為所求！″)else：print(″未找到″)27.列表a中存儲了若千個各不相同且無序的整數(shù),為了在列表a中查找第k大(1≤k≤n)的整數(shù),李陽借鑒二分查找的思想,編寫的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大的整數(shù)是:",high)28.編寫Python程序,實現(xiàn)在一個升序排列的列表中查找絕對值最小的元素。已知列表元素由正數(shù)、負數(shù)或0構(gòu)成。例如:列表中元素為[80,65,55,40,20,4,5,8,10,15,20,30],該數(shù)組中絕對值最小的數(shù)為4。程序運行示例如下圖所示。defdmin(x,y):ifabs(x)<abs(y):dmin=xelse:dmin=yreturndmin#生成n個由正數(shù)、負數(shù)或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: