高中信息技術(shù) （高考復(fù)習）專題八數(shù)據(jù)結(jié)構(gòu)與算法（習題部分）

第第頁專題八數(shù)據(jù)結(jié)構(gòu)與算法考點集訓考點一數(shù)據(jù)結(jié)構(gòu)與算法效率1.下列有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系的描述中,錯誤的是()A.數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系可表示為:程序+數(shù)據(jù)結(jié)構(gòu)=算法B.算法設(shè)計必須考慮到數(shù)據(jù)結(jié)構(gòu),算法設(shè)計不可能獨立于數(shù)據(jù)結(jié)構(gòu)C.算法的設(shè)計同時伴有數(shù)據(jù)結(jié)構(gòu)的設(shè)計,兩者都是為最終解決問題服務(wù)的D.數(shù)據(jù)結(jié)構(gòu)是編程思想,算法則是這些思想的邏輯基礎(chǔ)答案D2.某手機APP為了增加熱度,采用“簽到換積分得獎品”的形式來吸引用戶。簽到積分的規(guī)則為:第1天簽到得1分,第2天簽到得2分,第3天簽到得3分,……第n天簽到得n分。統(tǒng)計連續(xù)簽到n天可以獲得的總積分。通過分析可知總積分為1+2+3+…+n,利用程序?qū)崿F(xiàn)計算總積分,時間復(fù)雜度最低的是()A.O(1)B.O(log2n)C.O(n)D.O(n2)答案A3.常見算法時間復(fù)雜度函數(shù)的增長率如圖所示。則當問題規(guī)模n=100時,下列時間復(fù)雜度中效率最高的是()A.O(nlog2n)B.O(log2n)C.O(n)D.O(n3)答案B4.有如下Python程序代碼:n=int(input("n="))ans1=ans2=0foriinrange(0,n,2):forjinrange(n):ans1=ans1+1ans2=ans2+ans1print("ans1=",ans1,"ans2=",ans2)則該算法的時間復(fù)雜度為()A.O(1)B.O(n)C.O(n2)D.O(2n)答案C5.分析以下程序段的時間復(fù)雜度。a=b=c=1foriinrange(3,n+1):c=a+ba=bb=c答案時間復(fù)雜度為O(n)6.有以下Python程序段:defjishu(n):s=0whilen>0:s+=n%2n//=2returnsn=int(input("輸入一個正整數(shù):"))ans=jishu(n)print(ans)閱讀上述代碼,回答以下問題。(1)該程序運行后,輸入整數(shù)23,輸出結(jié)果為。

(2)若輸入整數(shù)23,則程序中自定義函數(shù)jishu()中語句“s+=n%2”執(zhí)行的次數(shù)是。

(3)函數(shù)jishu()的時間復(fù)雜度為(單選:A.O(n)B.O(log2n))。

答案(1)4(2)5(3)B考點二迭代與遞歸1.從微信1.0版本到微信8.0版本不斷更新的過程可以看出,一款產(chǎn)品從上市到最終框架的成型,是不斷試錯、不斷根據(jù)用戶體驗反饋快速調(diào)整和完善得到的結(jié)果。這個例子體現(xiàn)的算法思想是()A.枚舉B.遞歸C.解析D.迭代答案D2.通過函數(shù)調(diào)用把大問題分解為更小規(guī)模且相同的問題的組合,并對最小規(guī)模的問題給出簡單解,這種解決問題的方法稱為()A.枚舉B.遞歸C.解析D.迭代答案B3.在計算機內(nèi)實現(xiàn)遞歸算法時所需的數(shù)據(jù)結(jié)構(gòu)是()A.數(shù)組B.棧C.隊列D.鏈表答案B4.(2022紹興諸暨期中,10)某Python程序段如下:importrandomfibo=[1]*11foriinrange(2,11):fibo[i]=fibo[i-1]+fibo[i-2]n=random.randint(1,10)print(fibo[n])運行該程序段,輸出結(jié)果不可能是()A.1B.21C.35D.89答案C5.(2022紹興諸暨期中,12)下列Python程序的功能是使用迭代算法求s的值。n=int(input("pleaseinputn:"))s=0foriinrange(1,n):ifi%3==0:s=s+iprint("s=",s)程序執(zhí)行時,輸入n的值為25,則輸出的結(jié)果為()A.s=84B.s=118C.s=108D.s=105答案C6.(2022衢州期末,11)某Python程序段如下:defdoit(x):ifx>=6:ans=1else:ans=3*doit(x+1)+2*doit(x+2)returnansprint(doit(3))程序運行后,輸出的結(jié)果為()A.17B.21C.61D.62答案C7.(2023浙江1月選考,11,2分)定義如下函數(shù):defrf(n):ifn<3:returnnreturnrf(n-1)+rf(n-3)執(zhí)行語句v=rf(5),函數(shù)rf被調(diào)用的次數(shù)是()A.1B.5C.7D.15答案C考點三數(shù)據(jù)排序1.利用冒泡排序按從后至前的比較順序給數(shù)組[15,63,88,23,69,71,20,53]排序,第三遍冒泡加工之后的數(shù)組結(jié)果是()A.[15,20,23,53,63,69,88,71]B.[88,71,15,63,69,23,53,20]C.[88,71,69,63,15,53,23,20]D.[15,20,23,53,63,88,69,71]答案D2.(2022紹興諸暨期中,11)有如下Python程序段:b=[56,80,10,31,24,52,66,49]n=len(b)foriinrange(1,3):forjinrange(0,n-i):ifb[j]>b[j+1]:b[j],b[j+1]=b[j+1],b[j]經(jīng)過該程序段“加工”后,列表b中的元素為()A.[10,24,31,49,52,56,66,80]B.[10,31,24,52,56,49,66,80]C.[56,10,31,24,52,66,49,80]D.[10,24,31,52,49,56,66,80]答案B3.(2022紹興柯橋期末,11)對一組數(shù)據(jù)采用冒泡排序算法進行排序,若第一趟排序完成后的數(shù)據(jù)序列為31,24,23,15,20,10,則該數(shù)據(jù)序列的原始順序不可能是()A.24,23,15,31,10,20B.24,23,15,20,31,10C.24,31,23,15,10,20D.23,24,15,20,31,10答案D4.(2022臺州玉環(huán)月考,12)有如下Python程序段:a=[1]*6b=[96,88,84,91,99,80]foriinrange(6):forjinrange(i+1,6):ifb[j]>b[i]:a[i]+=1else:a[j]+=1print(a)該程序段運行后,列表a的值為()A.[5,3,2,4,6,1]B.[2,4,5,3,1,6]C.[10,6,4,8,12,2]D.[4,8,10,6,2,12]答案B5.(2022諸暨海亮高中月考,11)有如下程序段:a=[92,22,11,98,96,71]n=len(a)foriinrange(n):forjinrange():

ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]print(a)為實現(xiàn)n個數(shù)的升序排序,劃線處應(yīng)填()A.range(i-1)B.range(n-2,i-1,-1)C.range(i,n)D.range(n-1,n-i-2,-1)答案B6.(2023浙江1月選考,10,2分)列表s包含8個互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下Python程序段:n=8foriinrange(1,n-1):forjinrange(1,n-i-1):ifs[j]>s[j-1]:s[j],s[j-1]=s[j-1],s[j]該程序段實現(xiàn)的是()A.s[0]到s[5]的降序排列B.s[1]到s[6]的降序排列C.s[1]到s[7]的升序排列D.s[2]到s[6]的升序排列答案A7.(2022紹興諸暨期中,17)有如下Python程序段:importrandomn=6a=[9,4,3,4,7,6]foriinrange(n-1,0,-1):forjinrange(0,i):ifa[i]<a[j]:a[i],a[j]=a[j],a[i]print(a)排序后,數(shù)組a=。

答案[3,4,4,6,7,9]考點四數(shù)據(jù)查找1.(2022Z20名校聯(lián)盟聯(lián)考,9)某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=m-1else:i=m+1數(shù)組a中的元素為“58,69,78,80,83,84,90,90,95”,則執(zhí)行該程序段后,數(shù)組s中的元素不可能為()A.83,90,95B.83,78,80C.83,90,90,84D.83,78,69,58答案D2.(2022百校聯(lián)考,12)某程序段如下:a=[9,15,19,20,23,36,78,87,96,100]ans=[];i=0;j=9key=int(input("請輸入待查數(shù)據(jù):"))flag=Falsewhilei<=jandnotflag:m=(i+j)//2ans.append(a[m])ifa[m]==key:flag=Trueelifa[m]>key:j=m-1else:i=m+1print(ans)執(zhí)行該程序后,當輸入的key值為15時,輸出的結(jié)果是()A.[23,15]B.[23,19,15]C.[20,15]D.[20,19,15]答案A3.(2022名校協(xié)作體聯(lián)考,12)某算法的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=m-1c+=1列表a=[23,21,19,18,16,15,14,11],該程序段執(zhí)行后,下列說法不正確的是()A.i的值為j+1B.i的值可能是8C.j的值可能是5D.c的值一定是3答案B4.(2022諸暨海亮高中月考,12)下列程序?qū)崿F(xiàn)了輸入k,找出大于k的數(shù)據(jù)的起始索引位置并顯示。a=[1,3,3,5,5,7,10,11,12,15]n=10k=int(input())i=-1j=

whilei<j:m=(i+j+1)//2ifk<a[m]:j=

else:i=mL=

print(">",k,"的數(shù)據(jù)索引起始位置為",L)上述程序段橫線處語句依次為()A.nm-1iB.n-1m-1i+1C.nm+1iD.n-1m+1i+1答案B5.(2022紹興諸暨期中,15)某二分查找算法的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的值為3答案B6.(2022諸暨期末,12)有如下二分查找程序段:#列表a存放整數(shù)升序數(shù)據(jù),代碼略key=int(input())f=[0]*9i=0j=8whilei<=j:m=(i+j)//2f[m]=1ifa[m]>key:j=m-1else:i=m+1print(f)輸入待查找數(shù)據(jù),執(zhí)行該程序段后,下列選項中,列表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]答案C專題集訓1.(2023屆十校聯(lián)盟10月聯(lián)考,9)有如下Python程序段:deftrans(m,n):ifm!=0:r=m%nreturntrans(m//n,n)+str(r)else:return"0"a=int(input("a="))b=int(input("b="))print(trans(a,b))執(zhí)行該程序段,依次輸入11和2,則輸出的結(jié)果是()A.1011B.1101C.01011D.11010答案C3.(2023屆浙南名校聯(lián)盟10月聯(lián)考,8)小王走樓梯,每次走1個臺階或2個臺階,問小王走n個臺階時,有多少種不同的走法?現(xiàn)編寫代碼如下:defupstairs(n):ifn==0orn==1:return1else:returnupstairs(n-1)+upstairs(n-2)n=int(input('請輸入樓梯有幾個臺階:'))way=upstairs(n)print(way)當輸入的樓梯有10個臺階時,請問有多少種走樓梯的方法()A.88B.89C.90D.91答案B4.(2022麗水質(zhì)量監(jiān)控,12)某二分查找算法的Python程序段如下:key=int(input("請輸入待查數(shù)據(jù)值:"))d=[17,18,20,23,24,25,28,32,34,35]f=False;s=""i=0;j=len(d)-1whilei<=j:m=(i+j)//2s=s+","+str(d[m])ifd[m]==key:f=Truebreakifkey<d[m]:j=m-1else:i=m+1iff==True:print("查找成功!遍歷的數(shù)據(jù)"+s)else:print("沒有找到!")輸入待查數(shù)據(jù)值為23,執(zhí)行該程序段,則輸出的結(jié)果是()A.25,20,24,23B.24,18,20,23C.25,20,23D.24,20,23答案B5.(2022衢州期末,12)某二分查找算法的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=m-1else:L=m+1若輸入key的值為22,程序運行結(jié)束后,下列描述不正確的是()A.m的值是7B.s的值是3C.L的值是8D.R的值是7答案A6.(2022寧波九校聯(lián)考期末,12)某二分查找算法的Python程序段如下,運行該段代碼后,輸出的結(jié)果不可能是()importrandoma=[10,20,30,40,50,60,70,80]key=random.choice(a);i,j=0,len(a)-1s=""whilei<=j:m=(i+j)//2ifkey==a[m]:s=s+"M";breakelifkey<a[m]:j=m-1;s=s+"L"else:i=m+1;s=s+"R"print(s)A.LLMB.LRMC.RRRMD.RRLM答案D7.(2022浙江開學考,12)峰值元素指數(shù)組中其值大于左右相鄰值的元素,如序列3、8、4、1中8為峰值元素。一個數(shù)組r包含多個峰值元素,現(xiàn)需要找出其中一個峰值元素所在的位置(默認第一個數(shù)的左側(cè)和最后一個數(shù)的右側(cè)為0,即序列1、2、3中3也為峰值元素)?，F(xiàn)有實現(xiàn)該功能的Python程序如下:i=0;j=6whilei<j:m=(i+j)//2ifa[m+1]>a[m]:i=m+1else:j=mprint("峰值位置是",i)數(shù)組a=[10,2,25,17,20,21,9],執(zhí)行該程序后,輸出的值為()A.0B.2c.5D.8答案C8.有如下Python程序段:a=[2,1,9,8,6,3]cnt=0foriinrange(len(a)-1,0,-1):flag=Falseforjinrange(i):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]flag=Truecnt+=1ifnotflag:break則程序運行結(jié)束后,變量cnt的值為 ()A.3B.4C.5D.6答案B9.有如下程序段: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.014567D.0145678答案C10.某二分查找算法的Python程序段如下:a=[125,117,115,108,102,95,88,63,51,36]key=108i,j=0,len(a)-1ss=""whilei<=j:m=int((i+j)/2+0.5)ss=ss+str(m)ifkey==a[m]:breakifkey<a[m]:i=m+1ss=ss+">>"else:j=m-1ss=ss+"<<"print(ss)執(zhí)行該程序段,輸出的內(nèi)容為()A.4<<1>>2>>3B.5<<2<<4>>3C.5<<2>>4<<3D.5<<2>>4>>3答案C11.(2022諸暨期末,15)火車調(diào)度臺是實現(xiàn)火車車廂整理的平臺,當相鄰2節(jié)車廂序號不符合整理要求時,可以對調(diào)2節(jié)車廂,實現(xiàn)序號順序調(diào)整。相鄰2節(jié)車廂進行符合目標的交換,和我們學習的冒泡排序思想一致,所以這個調(diào)度過程可以用冒泡排序?qū)崿F(xiàn)。為了提高效率,對冒泡排序做了優(yōu)化,請完善下列代碼:nums=[3,1,2,4,5,6]①

k=n-1foriinrange(n-1):②

forjinrange(k):ifnums[j]>nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]③

ex_flag=Trueifex_flag:breakprint(nums)答案①n=len(nums)②ex_flag=False③k=j12.下列Python程序的功能是:輸入n的值(n≥5),用迭代法求1+(1*2)+(1*2*3)+…+(1*2*…*n)的值。程序運行效果如下所示,請在程序劃線處填入合適的代碼。PleaseinputnPleaseinputn:101+(1*2)+(1*2*3)+…+(1*2*…*10)=4037913n=int(input("Pleaseinputn:"))s1=1s2=0i=1while①:

s1=s1*i②

i+=1print("1+(1*2)+(1*2*3)+…+(1*2*…*",n,")=",s2)答案①i<=n②s2=s2+s113.(2022紹興諸暨期中,20)編寫一個Python程序,功能為:輸入關(guān)鍵字后,在書目清單列表中查找書名中包含關(guān)鍵字的書,并統(tǒng)計數(shù)量,然后在所有找到的書目中找出價格最貴的書。書目清單存儲在列表book中,每本書包含三個內(nèi)容:書名、作者和價格。程序運行示例如下:書目清單為:['Python編程從入門到實踐','埃里克·馬瑟斯',89.0]['C語言程序設(shè)計入門教程','史蒂芬·普拉達',187.0]['Javascript高級程序設(shè)計',馬特·弗里斯比',129.0]['R語言實戰(zhàn)','卡巴科弗',99.0]['Java核心技術(shù)卷Ⅰ','凱·S·霍斯特曼',149.0]['Python基礎(chǔ)教程','MagnusLieHetland',99.0]['零基礎(chǔ)學C++','明日科技',79.8]['Python學習手冊','馬克·盧茨',219.0]['Python數(shù)據(jù)結(jié)構(gòu)與算法分析','布拉德利·米勒',79.0]請輸入關(guān)鍵詞:Python符合要求的書單為:['Python編程從入門到實踐','埃里克·馬瑟斯',89.0]['Python基礎(chǔ)教程','MagnusLieHetland',99.0]['Python學習手冊','馬克·盧茨',219.0]['Python數(shù)據(jù)結(jié)構(gòu)與算法分析','布拉德利·米勒',79.0]共找到4本價格最貴的是:['Python學習手冊','馬克·盧茨',219.0](1)觀察運行結(jié)果,如果希望在書目清單列表中查找書名中包含關(guān)鍵字的書,比較合適的方法是(選填:“順序查找”或“二分查找”)。

(2)實現(xiàn)上述功能的Python程序如下,請在程序劃線處填入合適的代碼。#列表book中存儲了書的信息,內(nèi)容略n=len(book)print("書目清單為:")foriinrange(0,n,3):print(book[i:i+3])keyword=input("請輸入關(guān)鍵詞:")print("符合要求的書單為:")count,maxprice,posi=0,0,-1①

whilei<=n-3:if②:

print(book[i:i+3])count+=1ifmaxprice<book[i+2]:maxprice=book[i+2]③

i=i+3print("共找到",count,"本")ifposi==-1:print("對不起,沒有找到你要的書!")else:print("價格最貴的是:",book[posi:posi+3])答案(1)順序查找(2)①i=0②keywordinbook[i]③posi=i14.(2022紹興諸暨期中,19)小明學了排序和查找算法后,編寫了一個處理成績的程序,功能如下:程序運行時,首先從Excel文件中讀取n個學生的技術(shù)成績存儲在列表a中,并對列表中的數(shù)據(jù)按升序進行排序;輸入成績key,統(tǒng)計并輸出共有多少位同學的成績大于該成績。實現(xiàn)上述功能的Python程序如下,請在程序劃線處填入合適的代碼。#從Excel文件中讀取n個學生的技術(shù)成績存儲在列表a中,代碼略#對列表a中的元素進行升序排序n=len(a)foriinrange(n-1):forjinrange(0,n-i-1):if①:

a[j],a[j+1]=a[j+1],a[j]print(a)#輸入成績key,統(tǒng)計并輸出共有多少位同學的成績大于該成績key=int(input("pleaseinputkey:"))i,j=0,n-1whilei<=j:m=(i+j)//2if②:

j=m-1else:i=m+1print("共有"③+"位同學大于等于該成績。")

答案①a[j]>a[j+1]②key<a[m]③str(n-i)15.計算組合數(shù)Cnk。已知Cnk=Cn?1k+Cn?1k?1,我們可以把Cn(1)若采用遞歸算法計算組合數(shù)公式Cnk=Cn?1k+Cn?1k?1,當滿足邊界條件(2)實現(xiàn)該算法的程序如下:defC(n,k):if①:

return1else:return②

n,k=map(int,input().split())ans=C(n,k)print(ans)完善上述代碼。在劃線處填入合適的代碼語句:①;②。

答案(1)k=0或n=k(2)①k==0orn==k②C(n-1,k)+C(n-1,k-1)16.漢諾塔游戲的裝置是一塊銅板,上面有三根柱子,其中最左側(cè)一根柱子上放著從大到小的n個圓盤。游戲的目標是把所有圓盤從最左側(cè)一根柱子上移動到最右側(cè)一柱子針上,中間一個柱子作為過渡。游戲規(guī)定每次只能移動一個圓盤,并且大盤子不能壓在小盤子上面。漢諾塔游戲可以抽象為如圖所示的模型:從左到右有A、B、C三根柱子,其中A柱子上面放著從大到小的n個圓盤,現(xiàn)要求按一定規(guī)則,將A柱子上的圓盤移到C柱子上去。抽象后的漢諾塔模型例如,當n=2時,一個可行的移動方案為:先將A柱上端盤子移到B柱,然后再將A柱上端盤子移到C柱,最后將B柱上端盤子移到C柱。用符號表示為:A→B,A→C,B→C。(1)當n=3時,用符號表示3個圓盤的移動情況是。

(2)下列程序能夠使用符號表示n個圓盤的移動過程,程序運行后界面如下所示。請在劃線處填入合適的代碼。2個圓盤的移動過程2個圓盤的移動過程:A→B,A→C,B→C4個圓盤的移動過程:A→B,A→C,B→C,A→B,C→A,C→B,A→B,A→C,B→C,B→A,C→A,B→C,A→B,A→C,B→Cdefhanoi(n,a,b,c):ifn==1:#如果只有一個盤,直接將其從A柱移動到C柱print(a,"→",c,end=",")else:hanoi(①)#利用C柱中轉(zhuǎn),將n-1個盤從A柱移動到B柱

print(a,"→",c,end=",")#將第n個盤從A柱移動到C柱hanoi(②)#利用A柱中轉(zhuǎn),將n-1個盤從B柱移動到C柱

#主函數(shù)部分print("2個圓盤的移動過程:")hanoi(2,"A","B","C")#利用B柱中轉(zhuǎn),將n個盤從A柱移動到C柱print()print("4個圓盤的移動過程:")hanoi(4,"A","B","C")#利用B柱中轉(zhuǎn),將n個盤從A柱移動到C柱答案(1)A→C,A→B,C→B,A→C,B→A,B→C,A→C(2)①n-1,a,c,b②n-1,b,a,c17.謝爾賓斯基三角形(Sierpinskitriangle)是一種分形,由波蘭數(shù)學家謝爾賓斯基在1915年提出,它是一種典型的自相似集。其生成過程為:1)取一個實心的三角形(多數(shù)使用等邊三角形)。2)三邊中點的連線,將它分成四個小三角形。3)去掉中間的那一個小三角形。4)對其余三個小三角形重復(fù)上述步驟。可以設(shè)計如下算法:先繪制一個大的綠色正三角形做底版,然后調(diào)用遞歸函數(shù)split()繪制謝爾賓斯基三角形。函數(shù)split()先找到三角形三條邊的中點,將其等分成4個全等三角形,將中間的正三角形填充為白色,再遞歸處理另外3個綠色三角形,直到三角形的邊長小于某個特定值(例如40)為止。能夠?qū)崿F(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。importturtleastt#構(gòu)造三角形,并為其填充顏色cdeftriangle(x1,y1,x2,y2,x3,y3,c):tt.penup();tt.goto(x1,y1)tt.pendown()tt.colour(c)tt.begin_fill()tt.goto(x2,y2);tt.goto(x3,y3);tt.goto(x1,y1)tt.end_fill()defsplit(x1,y1,x2,y2,x3,y3):ifabs(x1-x2)>=40:x4,y4=(x1+x2)/2,(y1+y2)/2x5,y5=(x2+x3)/2,(y2+y3)/2x6,y6=①

triangle(②)

split(x1,y1,x4,y4,x6,y6)split(x4,y4,x2,y2,x5,y5)split(③)

#先繪制最大的三角形做底版,三點坐標定位(x1,y1),(x2,y2),(x3,y3)x1,y1=-200,0x2,y2=200,0x3,y3=0,(400*400-200*200)**0.5triangle(x1,y1,x2,y2,x3,y3,"green")split(x1,y1,x2,y2,x3,y3)tt.done()答案①(x3+x1)/2,(y3+y1)/2②x5,y5,x6,y6,x4,y4,"white"③x6,y6,x5,y5,x3,y318.二叉排序樹也稱為二叉查找樹,它具有如下特性:(1)若它的左子樹非空,則左子樹上所有節(jié)點的值均小于根節(jié)點的值。(2)若它的右子樹非空,則右子樹上所有節(jié)點的值均大于根節(jié)點的值。(3)左、右子樹本身又各是一棵二叉排序樹。如圖所示,就是一棵典型的二叉排序樹。阿福編寫了一個二叉排序樹類,基本實現(xiàn)了二叉排序樹的插入節(jié)點、輸出節(jié)點和查找節(jié)點功能。程序代碼如下所示,請根據(jù)代碼注釋,在劃線處填入合適的代碼。classBTNode:#二叉樹節(jié)點類def_init_(self,data=None,left=None,right=None):self.data=dataself.left=leftself.right=right#二叉排序樹類classSBTree:def_init_(self,root=None):self.root=rootdefinsert(self,root,data):#插入新節(jié)點ifself.rootisNone:#空樹self.root=BTNode(data)elifdata<root.data:#比根節(jié)點小則插入到左子樹中ifroot.leftisNone:①

else:self.insert(root.left,data)else:#否則插入到右子樹中ifroot.rightisNone:root.right=BTNode(data)else:②

#按非遞減次序(即中序遍歷)輸出節(jié)點definorder(self,root):ifrootisNone:return③

print(root.data,end=",")④

#二分查找數(shù)據(jù)值為key的節(jié)點defsearch(self,root,key):ifrootisNoneorroot.data==key:returnrootelifkey<root.data:#比root小則到左子樹中尋找return⑤

else:return⑥

if_name_=="_main_":a=[3,5,2,6,4,1]print(a)sbt=SBTree()foriina:sbt.insert(sbt.root,i)sbt.inorder(sbt.root)print()k=int(input())p=sbt.search(sbt.root,k)ifpisnotNone:print(k,p.data)else:print(k,p)答案①root.left=BTNode(data)②self.insert(root,right,data)③self.inorder(root,left)④self.inorder(root,right)⑤self.search(root,left,key)⑥self.search(root,right,key)19.(2022名校協(xié)作體,16)某會務(wù)組根據(jù)參會者到達指定上車點的時間和每位參會者可以等待的時間信息,安排車輛接送參會者去賓館(不考慮車子座位數(shù)量)。參會者到達上車點的時間和可以等待的時間用長度為7的字符串表示,例如“08:152”表示參會者當天8點15分到達上車點,最多等待2分鐘(每個人的等待時間都小于10),那么該參會者最晚8點17分出發(fā)去賓館(若有8點17分剛到的參會者也一同出發(fā))。編寫Python程序,統(tǒng)計接送n個參會者所需的最少車輛數(shù)。運行程序,顯示所有參會者提交的信息,按到達時間先后排列,再顯示所需的最少車輛數(shù),程序運行結(jié)果如圖所示。(1)若將圖中第4行“08:154”數(shù)據(jù)改為“08:151”,程序輸出的結(jié)果是否會發(fā)生改變(A.會改變B.不會改變)。

(2)實現(xiàn)上述功能的部分Python程序如下,請在劃線處填入合適的代碼。a=['08:154','08:143','08:234','08:152','08:122','08:171','08:173','08:194','08:214','08:171']deftran(str1):ss=int(str1[:2])*60+int(str1[3:6])returnssforiinrange(len(a)-1):forjinrange(len(a)-1,i,-1):ifa[j]<a[j-1]:a[j],a[j-1]=a[j-1],a[j]n=len(a)b=[]c=[]foriinrange(n):b.append(tran(a[i][:5]))c.append(b[-1]+int(a[i][6:]))forjinrange(i,0,-1):①

ifc[k]>c[j]:b[k],b[j]=b[j],b[k]c[k],c[j]=c[j],c[k]else:breaksum=0flag=[Falseforiinrange(n)]foriinrange(n):ifflag[i]==False:forjinrange(i,n):if②:

flag[j]=True③

print('接送所有參會者最少需要%d輛車'%sum)答案(1)A(2)①k=j-1②b[j]<=c[i]或flag==Falseandb[j]<=c[i]③sum+=120.(2023屆十校聯(lián)盟10月聯(lián)考,15)小丁是一位電影發(fā)燒友,尤其鐘愛喜劇片和動作片。他設(shè)計了一個程序,根據(jù)某部電影的鏡頭數(shù)據(jù)預(yù)測出類型,這類操作可利用k-近鄰分類算法來實現(xiàn),該算法核心思想是:一個樣本在特征空間中的k個最相鄰的樣本中的大多數(shù)屬于某一類別,則該樣本也屬于這個類別。小丁讀取“movie.csv”數(shù)據(jù)集文件,如圖a所示,內(nèi)容是一些電影的搞笑鏡頭和打斗鏡頭數(shù)目及類型。現(xiàn)要實現(xiàn)如下功能:輸入某部電影的搞笑鏡頭和打斗鏡頭數(shù)目后,輸出可能的類型,如圖c所示,并繪制該數(shù)據(jù)集文件和輸入的電影在平面坐標系的分布特點圖,如圖b所示。例如:輸入搞笑鏡頭40和打斗鏡頭40,判斷屬于哪類,通過如下步驟實現(xiàn):①計算點(40,40)和其余所有點的距離(兩點間的距離計算公式:d12=(x②將所有樣本按照距離升序排序;③假設(shè)k=3,取前k個距離的樣本;④統(tǒng)計出在前k個距離中,出現(xiàn)頻次最多的類別,則(40,40)就屬于該類別,可能是喜劇片。請輸入搞笑鏡頭:40[[83,26,(1)若輸入的搞笑鏡頭為20,輸入的打斗鏡頭為80,則該影片可能是(選填:喜劇片/動作片)。

(2)實現(xiàn)上述功能的Python代碼如下,請在劃線處填入合適的代碼。importpandasaspdimportnumpyasnpfrommathimportsqrtmovie=pd.read_csv("movie.csv")x=int(input("請輸入搞笑鏡頭:"))y=int(input("請輸入打斗鏡頭:"))dist=[]foriinrange(len(movie)):d=sqrt((x-movie.funny[i])**2+①)

dist.append(d)movie["dis"]=distmovie_list=np.array(movie).tolist()#將df對象轉(zhuǎn)成列表,如圖d所示,k=3foriinrange(k):forjinrange(len(movie_list)-1,i,-1):if②:

movie_list[j],movie_list[j-1]=movie_list[j-1],movie_list[j]funny=0;action=0foriinrange(k):if③:

funny+=1else:action+=1iffunny>action:print("該影片可能是喜劇片")else:print("該影片可能是動作片")#繪圖代碼略答案(1)動作片(2)①(y-movie.action[i])**2或(y-movie["action"][i])**2或(y-movie.at[i,"action"])**2②movie_list[j][3]<movie_list[j-1][3]或movie_list[j][-1]<movie_list[j-1][-1]③movie_list[i][2]=="喜劇片"或"喜劇片"inmovie_list[i]21.(2023屆浙南名校聯(lián)盟10月聯(lián)考,15)插補查找算法又稱為插值查找,它是二分查找算法的改進版。插補查找是按照數(shù)據(jù)的分布,利用公式預(yù)測鍵值所在的位置,快速縮小鍵值所在序列的范圍,慢慢逼近,直到查找到數(shù)據(jù)為止。它類似于平常查字典的方法。例如,我們在翻字典查一個發(fā)音以字母B開頭的文字時,不會使用二分查找法找字典的中間部分,因為根據(jù)字典的順序可知,發(fā)音以B開頭的文字應(yīng)該在字典較前的部分,所以可以從字典前部的某處開始查找。插補查找算法的所謂中間位置鍵值索引計算方式如下:middle=low+(target-data[low])/(data[high]-data[low])*(high-low)參數(shù)說明:data:數(shù)據(jù)列表middle:當前需要比對的數(shù)據(jù)索引low:最左側(cè)數(shù)據(jù)的索引high:最右側(cè)數(shù)據(jù)的索引target:查找的目標數(shù)據(jù)現(xiàn)有150位學生(編號從1到150)參加軍訓拉練,從中隨機選取9位同學作為旗手,如:[12,'薛丁'],[45,'李強'],[56,'徐梓'],[66,'鮑杰'],[77,'黃怡'],[80,'余澍'],[97,'金維'],[101,'方茹'],[120,'陳昀'],現(xiàn)在某位家長想知道方茹同學是否被選到,如果選到又是第幾個旗手,為了解決這個問題,可以使用插補查找算法。例如:查找方茹,需要輸入101進行查找,具體如圖所示:旗手如下旗手如下:(編號:12)[薛丁](編號:45)[李強](編號:56)[徐梓](編號:66)[鮑杰](編號:77)[黃怡](編號:80)[余澍](編號:97)[金維](編號:101)[方茹](編號:120)[陳昀]請輸入需要查找的學生編號:101正在查找正在查看第7個旗手[[97,'金維']]正在查看第8個旗手[[101,'方茹']]方茹同學是第8個旗手(1)在題目所示案例中,若使用插補查找算法查找45號旗手,則該過程中訪問到的數(shù)據(jù)依次為。

(2)實現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。defsearch(data,num):#定義查找函數(shù),參數(shù)是原數(shù)列data和鍵值numlow=0#定義變量用來表示低位high=len(data)-1#定義變量用來表示高位print("正在查找")#提示語whilelow<=highandnum!=-1:left=data[low][0]mid=low+(num-left)*(high-low)①#請將表達式補充完整

print(f"正在查看第{mid+1}個旗手[{data[mid]}]")ifnum<data[mid][0]:high=mid-1elifnum>data[mid][0]:low=mid+1else:②

return-1num=0#定義變量,用來輸入鍵值students=[[12,'薛丁'],[45,'李強'],[56,'徐梓'],[66,'鮑杰'],[77,'黃怡'],[80,'余澍'],[97,'金維'],[101,'方茹'],[120,'陳昀']]