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

專題八數(shù)據(jù)結(jié)構(gòu)與算法

考點(diǎn)集訓(xùn)

考點(diǎn)一數(shù)據(jù)結(jié)構(gòu)與算法效率

L下列有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系的描述中,錯(cuò)誤的是()

A.數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系可表示為:程序+數(shù)據(jù)結(jié)構(gòu)=算法

B.算法設(shè)計(jì)必須考慮到數(shù)據(jù)結(jié)構(gòu),算法設(shè)計(jì)不可能獨(dú)立于數(shù)據(jù)結(jié)構(gòu)

C算法的設(shè)計(jì)同時(shí)伴有數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì),兩者都是為最終解決問(wèn)題服務(wù)的

D.數(shù)據(jù)結(jié)構(gòu)是編程思想,算法則是這些思想的邏輯基礎(chǔ)

答案D

2.某手機(jī)APP為了增加熱度,采用“簽到換積分得獎(jiǎng)品”的形式來(lái)吸引用戶。簽到積分的規(guī)

則為:第1天簽到得1分,第2天簽到得2分,第3天簽到得3分,……第n天簽到得n分。

統(tǒng)計(jì)連續(xù)簽到n天可以獲得的總積分。通過(guò)分析可知總積分為1+2+3+…+n,利用程序?qū)?/p>

現(xiàn)計(jì)算總積分,時(shí)間復(fù)雜度最低的是()

A.O(1)B.O(log2n)

C.O(n)D.O(n2)

答案A

3.常見算法時(shí)間復(fù)雜度函數(shù)的增長(zhǎng)率如圖所示。

則當(dāng)問(wèn)題規(guī)模n=100時(shí),下列時(shí)間復(fù)雜度中效率最高的是()

第1頁(yè)共45頁(yè)

A.O(nlog2∏)B.O(log2∏)

C.O(n)D.O(n3)

答案B

4.有如下Python程序代碼：

n=int(input(''n="))

ansl=ans2=0

foriinrange(0,n,2):

forjinrange(n):

ansl=ansl+l

ans2=ans2÷ans1

Print("ansl=",ans1,“ans2=",ans2)

則該算法的時(shí)間復(fù)雜度為()

A.O(1)B.O(n)C.O(n2)D.0(2n)

答案C

5.分析以下程序段的時(shí)間復(fù)雜度。

a=b=c=l

foriinrange(3zn÷l):

c=a+b

a=b

b=c

答案時(shí)間復(fù)雜度為O(n)

6.有以下Python程序段：

defjishu(n)：

s=0

第2頁(yè)共，45頁(yè)

whilen>0：

s+=n%2

n∕∕=2

returns

n=int(input(〃輸入一個(gè)正整數(shù):〃))

ans=yishu(n)

print(ans)

閱讀上述代碼,回答以下問(wèn)題。

⑴該程序運(yùn)行后,輸入整數(shù)23,輸出結(jié)果為.

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

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

答案(1)4(2)5(3)B

考點(diǎn)二迭代與遞歸

L從微信LO版本到微信8.0版本不斷更新的過(guò)程可以看出,一款產(chǎn)品從上市到最終框架

的成型,是不斷試錯(cuò)、不斷根據(jù)用戶體驗(yàn)反饋快速調(diào)整和完善得到的結(jié)果。這個(gè)例子體現(xiàn)

的算法思想是()

A枚舉B.遞歸C.解析D.迭代

答案D

2.通過(guò)函數(shù)調(diào)用把大問(wèn)題分解為更小規(guī)模且相同的問(wèn)題的組合,并對(duì)最小規(guī)模的問(wèn)題給

出簡(jiǎn)單解,這種解決問(wèn)題的方法稱為()

A.枚舉B.遞歸C.解析D.迭代

答案B

3.在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)遞歸算法時(shí)所需的數(shù)據(jù)結(jié)構(gòu)是()

第3頁(yè)共45頁(yè)

A?數(shù)組B棧C.隊(duì)列D.鏈表

答案B

4.(2022紹興諸暨期中,10)某Python程序段如下：

importrandom

fibo=[l]*l1

foriinrange(2,l1)：

fibo[i]=fibo[i-l]+fibo[i-2]

n=random.randint(1r10)

print(fibo[n])

運(yùn)行該程序段,輸出結(jié)果不可能是()

A.lB.21C.35D.89

答案C

5.(2022紹興諸暨期中,12)下列Python程序的功能是使用迭代算法求S的值。

n=int(input(,pleaseinputn："))

s=0

foriinrange(lzn):

ifi%3=0:

s=s+i

Print(〃s=〃,s)

程序執(zhí)行時(shí),輸入n的值為25則輸出的結(jié)果為()

A.s=84B.s=l18C.s=108D.s=105

答案C

6.(2022衢州期末11)某Python程序段如下：

第4頁(yè)共45頁(yè)

defdoit(x):

ifx>=6:

ans=l

else：

ans=3*doit(x÷l)÷2*doit(x+2)

returnans

print(doit(3))

程序運(yùn)行后,輸出的結(jié)果為()

A.17B.21C.61D.62

答案C

7.(2023浙江1月選考,11,2分)定義如下函數(shù)：

defrf(n):

ifn<3:

returnn

returnrf(n-l)+rf(n-3)

執(zhí)行語(yǔ)句v=rf(5),函數(shù)rf被調(diào)用的次數(shù)是()

A.lB.5C.7D.15

答案C

考點(diǎn)三數(shù)據(jù)排序

L利用冒泡排序按從后至前的比較順序給數(shù)組[15,63,88,23,69,71,20,53]排序,第三遍冒泡

加工之后的數(shù)組結(jié)果是()

A.[l5,20,23,53,63,69,88,71]

B.[88,71,15,63,69,23,53,20]

第5頁(yè)共45頁(yè)

C.[88,71,69,63,15,53,23,20]

D.[l5,20,23,53,63,88,69,71]

答案D

2.（2022紹興諸暨期中,11）有如下Python程序段：

b=[56,80,10,31,24,52,66,49]

n=len（b）

foriinrange（l,3）:

forjinrange（0,n-i）:

ifbb]>b[j+l]:

b[j],b[j+l]=b∣j+l],b∣j]

經(jīng)過(guò)該程序段“加工”后,列表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.[l0,24,31,52,49,56,66,80]

答案B

3.（2022紹興柯橋期末,11）對(duì)一組數(shù)據(jù)采用冒泡排序算法進(jìn)行排序,若第一趟排序完成后

的數(shù)據(jù)序列為31,24,23,15,20,10,則該數(shù)據(jù)序列的原始順序不可能是（）

A.24,23,15,31,10,20

B.24,23,15,20,31,10

C.24,31,23,15,10,20

D.23,24,15,20,31,10

第6頁(yè)共45頁(yè)

答案D

4.(2022臺(tái)州玉環(huán)月考,12)有如下Python程序段:

a=[l]*6

b=[96,88,84,91,99,80]

foriinrange(6):

forjinrange(i+l,6):

ifb[j]>b[i]:

a[i]+=1

else：

a[j]+=1

print(a)

該程序段運(yùn)行后,列表a的值為

A.[5,3,2,4,6,l]

B.[2,4,5,3,l,6]

C.[10,6,4,8,12,2]

D.[4,8,10,6,2,12]

答案B

5.(2022諸暨海亮高中月考,11)有如下程序段：

a=[92,22,11,98,96,71]

n=len(a)

foriinrange(n)：

forjinrange()：

第7頁(yè)共45頁(yè)

ifa[j]>a[j+l]:

a[j],a[j+l]=a[j+l],a[j]

print(a)

為實(shí)現(xiàn)n個(gè)數(shù)的升序排序,劃線處應(yīng)填()

A.range(i-1)B,range(n-2,i-l,-l)

C.range(i,n)D.range(n-l,n-i-2,-l)

答案B

6.(2023浙江1月選考,10,2分)列表S包含8個(gè)互不相等的元素,即s[0],s[l],s[2],…,S⑺,有

如下Python程序段：

n=8

foriinrange(l,n-l):

forjinrange(l,n-i-l):

ifs[j]>s∣j-l]:

s[j],s[j-l]=s∣j-l],s∣j]

該程序段實(shí)現(xiàn)的是()

A?s[0]到S⑸的降序排列

B.s[l]到S⑹的降序排列

C.s[l]到S⑺的升序排列

D.s[2]到S⑹的升序排列

答案A

7.(2022紹興諸暨期中,17)有如下Python程序段：

importrandom

n=6

第8頁(yè)共45頁(yè)

a=[9,4,3,4,7,6]

foriinrange(n-l,θ,-l)?

forjinrange(0,i)：

ifa[i]<a[j]:

a[i],a[j]=a[j],a[i]

print(a)

排序后,數(shù)組a=o

答案[3,4,4,6,7,9]

考點(diǎn)四數(shù)據(jù)查找

1.(2022Z20名校聯(lián)盟聯(lián)考⑼某Python程序如下：

importrandom

key=random.randint(35z45)*2

i=O；j=len(a)-l；s=[]

whileiv寸

m=(i+j+1)//2

s.append(a[m])

ifkey<a[m]:

j=m?l

else：

i=m+l

數(shù)組a中的元素為“58,69,78,80,83,84,90,90,95”,則執(zhí)行該程序段后,數(shù)組S中的元素不可

能為()

A.83,90,95B.83,78,80

第9頁(yè)共，45頁(yè)

C.83,90,90,84D,83,78,69,58

答案D

2.(2022百校聯(lián)考,12)某程序段如下：

a=[9,l5,19,20,23,36,78,87,96,100]

ans=[]；i=0；j=9

key=int(input(〃請(qǐng)輸入待查數(shù)據(jù):〃))

flag=False

whilei<^jandnotflag：

m=(i+j)∕∕2

ans.append(a[m])

ifa[m]==key:

Aag=True

e?ifa[m]>key:

j=m?l

else：

i=m+l

print(ans)

執(zhí)行該程序后,當(dāng)輸入的key值為15時(shí),輸出的結(jié)果是()

A.[23,15]B.[23,19,15]

C.[20,15]D.[20,19,15]

答案A

3.(2022名校協(xié)作體聯(lián)考,12)某算法的Python程序段如下：

key=randint(0,3)*2+13

第10頁(yè)共45頁(yè)

ijxc=O,len(a)-lzO

whilei<=j:

m=(i+j+l)∕∕2

ifa[in]>=key：

i=m+l

else：

j=m-l

c+=l

列表a=[23,21,19,18,16,15,14,11],該程序段執(zhí)行后,下列說(shuō)法不正碉的是()

A.i的值為j+1B.i的值可能是8

Cj的值可能是5D.c的值一定是3

答案B

4.(2022諸暨海亮高中月考,12)下列程序?qū)崿F(xiàn)了輸入k,找出大于k的數(shù)據(jù)的起始索引位置

并顯示。

a=[l,3,3,5,5,7,10,11,12,15]

n=10

k=int(input())

i=-l

j=________

whilei<j：

m=(i+j+1)//2

ifk<a[m]:

else：

第11頁(yè)共45頁(yè)

ι=m

L=____

Print（">",k,''的數(shù)據(jù)索引起始位置為",L）

上述程序段橫線處語(yǔ)句依次為（）

A.nm-1iB.n-1m-1i+1

C.nm+1iD.n-1m÷li÷l

答案B

5.（2022紹興諸暨期中,15）某二分查找算法的Python程序段如下：

IiStl=["Carrot","Celery","Garlic","Lettuce","Mooli","Onion","Potato","Tomato”]

key=listl[2]

Ieftjight=OzIen（Iistl）-I

C=O

whileleft<=right:

m=（left+right）∕∕2

c=c÷l

ifIistl[m]>key:

right=m-l

else：

left=m+l

print（listl[left]）

程序執(zhí)行后,下列說(shuō)法正確的是（）

A.變量C的值為4

B.程序輸出的結(jié)果為L(zhǎng)ettuce

C.變量left的值為2

第12頁(yè)共45頁(yè)

D.變量right的值為3

答案B

6.(2022諸暨期末,12)有如下二分查找程序段：

#列表a存放整數(shù)升序數(shù)據(jù),代碼略

key=int(input())

00]*9

i=0

j=8

whilei<=j:

m=(i÷j)∕∕2

f[m]=l

ifa[m]>key:

j=m-l

else：

i=m+l

Print⑴

輸入待查找數(shù)據(jù)執(zhí)行該程序段后,下列選項(xiàng)中,列表f的值不可能是()

A.[O,O,O,O,1,1,1,O,O]

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,l,0,l,l,0]

答案C

專題集訓(xùn)

第13頁(yè)共45頁(yè)

1.(2023屆十校聯(lián)盟10月聯(lián)考,9)有如下Python程序段：

deftrans(mzn):

ifm!=0:

r=m%n

returntrans(m//nln)+str(r)

else：

return〃0〃

a=int(input(z,a=z"))

b=int(input(zzb=/z))

print(trans(a,b))

執(zhí)行該程序段,依次輸入11和2,則輸出的結(jié)果是()

A.IOllB.IlOlC.OlOllD.HOlO

答案C

3.(2023屆浙南名校聯(lián)盟10月聯(lián)考,8)小王走樓梯,每次走1個(gè)臺(tái)階或2個(gè)臺(tái)階,問(wèn)小王走n

個(gè)臺(tái)階時(shí),有多少種不同的走法?現(xiàn)編寫代碼如下：

defupstairs(n):

ifn==0orn==l:

return1

else：

returnupstairs(n-l)+upstairs(n-2)

n=int(input(,請(qǐng)輸入樓梯有幾個(gè)臺(tái)階：'))

way=upstairs(n)

print(way)

第14頁(yè)共45頁(yè)

當(dāng)輸入的樓梯有10個(gè)臺(tái)階時(shí),請(qǐng)問(wèn)有多少種走樓梯的方法（）

A.88B.89C.90D.91

答案B

4.（2022麗水質(zhì)量監(jiān)控,12）某二分查找算法的Python程序段如下：

key=int（input（"請(qǐng)輸入待查數(shù)據(jù)值：”））

d=[17,l8,20,23,24,25,28,32,34,35]

f=False；s="”

i=0；j=len（d）-l

whilei<=j:

m=（i+j）∕∕2

s=s+,z∕,+str（d[m]）

ifd[m]==key:

f=True

break

ifkey<d[m]:

j=m?l

else：

i=m+l

ifaTrue：

Print（"查找成功!遍歷的數(shù)據(jù)〃+s）

else：

Print（"沒有找到!”）

輸入待直數(shù)據(jù)值為23,執(zhí)行該程序段,則輸出的結(jié)果是（）

第15頁(yè)共45頁(yè)

A.25,20,24,23B.24,18,20,23

C.25,20,23D.24,20,23

答案B

5.（2022衢州期末,12）某二分查找算法的Python程序段如下：

a=[14/7,18,19,19,22,22,22,28,28]

S=O

key=int（input（，，key：，/））

LzR=0zlen（a）-l

whileL<=R:

m=（L+R）∕∕2

s+=l

ifa[m]>key:

R=m-1

else：

L=m+1

若輸入key的值為22,程序運(yùn)行結(jié)束后,下列描述不正確的是（）

A.m的值是7B.s的值是3

C.L的值是8D.R的值是7

答案A

6.（2022寧波九校聯(lián)考期末,12）某二分查找算法的Python程序段如下,運(yùn)行該段代碼后,

輸出的結(jié)果不可能是（）

importrandom

a=[10,20,30,40,50,60,70,80]

第16頁(yè)共45頁(yè)

key=random.choice(a)^j=0,len(a)-l

whilei<弓：

m=(i+j)∕∕2

ifkey=a[m]:

s=s+z，Mz，；break

elifkey<a[m]:

j=m-ljs=s+,,Lzz

else：

i=m+]；s=s+〃R〃

print(s)

A.LLMB.LRM

C.RRRMD.RRLM

答案D

7.(2022浙江開學(xué)考,12)峰值元素指數(shù)組中其值大于左右相鄰值的元素,如序列3、8、4、

1中8為峰值元素。一個(gè)數(shù)組r包含多個(gè)峰值元素,現(xiàn)需要找出其中一個(gè)峰值元素所在的

位置(默認(rèn)第一個(gè)數(shù)的左側(cè)和最后一個(gè)數(shù)的右側(cè)為0,即序列1、2、3中3也為峰值元素)。

現(xiàn)有實(shí)現(xiàn)該功能的Python程序如下：

i=0；j=6

whilei<j:

m=(i+j)∕∕2

ifa[m+l]>a[m]:

i=m+l

第17頁(yè)共45頁(yè)

else：

j=m

Print("峰值位■是”,i)

數(shù)組a=[10,2,25,17,20,21,9]執(zhí)行該程序后輸出的值為

A.0B.2c.5D.8

答案C

8.有如下Python程序段：

a=[2,1,9,8,6,3]

cnt=O

foriinrange(len(a)-1,0,-1):

Aag=False

forjinrange(i):

ifaU]>a[j+l]:

aU]^U+l]=a[j+l],a∣j]

Aag=True

cnt+=l

ifnotflag:

break

則程序運(yùn)行結(jié)束后,變量Cnt的值為()

A.3B.4C.5D.6

答案B

9.有如下程序段：

d=[Ien,str,abs,chr,min,ord,ιnt,maxJ

n=len(d)

key=input(,zpleaseinputkey：〃)

第18頁(yè)共45頁(yè)

ans=O

i=O

〃〃

s=

whilei<=n-l:

ifd[i]>key:

s=s+str(i)

i=i+l

print(s)

程序運(yùn)行時(shí),輸入float,輸出結(jié)果為()

A.12567B.125678

C.014567D.0145678

答案C

10.某二分查找算法的Python程序段如下：

a=[125zl17,115,108,102,95,88,63,51,36]

key=108

ij=O,len(a)-l

〃〃

SS=

whilei<寸

m=int((i+j)∕2+0.5)

ss=ss+str(m)

ifkey=a[m]:

break

ifkey<a[m]:

i=m+l

ss=ss+,,>>,z

第19頁(yè)共45頁(yè)

else：

j=m-l

ss=ss+z,<<z,

print(ss)

執(zhí)行該程序段,輸出的內(nèi)容為()

A.4<<l>>2>>3B.5<<2<<4>>3

C.5<<2>>4<<3D.5<<2>>4>>3

答案C

11.(2022諸暨期末,15)火車調(diào)度臺(tái)是實(shí)現(xiàn)火車車廂整理的平臺(tái),當(dāng)相鄰2節(jié)車廂序號(hào)不符

合整理要求時(shí),可以對(duì)調(diào)2節(jié)車廂,實(shí)現(xiàn)序號(hào)順序調(diào)整。相鄰2節(jié)車廂進(jìn)行符合目標(biāo)的交

換,和我們學(xué)習(xí)的冒泡排序思想一致,所以這個(gè)調(diào)度過(guò)程可以用冒泡排序?qū)崿F(xiàn)。為了提高

效率,對(duì)冒泡排序做了優(yōu)化,請(qǐng)完善下列代碼：

nums=[3rlz2,4/5,6]

①

k=n-l

foriinrange(n-l)：

②

forjinrange(k)：

ifnums[j]>nums[j+1]：

nums[j]znums[j÷l]=nums∣j+l]znums∣j]

③

ex_flag=True

ifexflag：

break

print(nums)

第20頁(yè)共45頁(yè)

答案①n=len(nums)②ex_flag=FalSe③k=j

12.下列Python程序的功能是：輸入n的值(n>5),用迭代法求

1+(1*2)+(1*2*3)+…+(1*2*...*n)的值。

程序運(yùn)行效果如下所示,請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。

Pleaseinputn：10

1+(1*2)+(1*2*3)+???+(1*2*???*10)=4037913

n=int(input(zzPleaseinputn：〃))

sl=l

s2=0

i=l

whileφ：

sl=sl*i

②

i+=l

print(,l+(l*2)+(1*2*3)+…+(1*2*...*",n,")=",s2)

答案①i<=n②s2=s2+s1

13.(2022紹興諸暨期中,20)編寫一個(gè)Python程序,功能為:輸入關(guān)鍵字后,在書目清單列表

中查找書名中包含關(guān)鍵字的書,并統(tǒng)計(jì)數(shù)量,然后在所有找到的書目中找出價(jià)格最貴的書。

書目清單存儲(chǔ)在列表book中,每本書包含三個(gè)內(nèi)容:書名、作者和價(jià)格。程序運(yùn)行示例如

下：

書目清單為：

【'Python編程從入門到實(shí)踐'埃里克?馬瑟斯',89.0]

「C語(yǔ)言程序設(shè)計(jì)入門教程'史蒂芬?普拉達(dá)'，187.0]

[,Javascript高級(jí)程序設(shè)計(jì)’,馬特?弗里斯比’，129.0]

第21頁(yè)共45頁(yè)

ΓR語(yǔ)言實(shí)戰(zhàn)','卡巴科弗',99.0]

CJava核心技術(shù)卷I'凱?S?霍斯特曼',149,0]

[,PythonS?出教程'，'MagnusLieHetland),99.0]

['零基礎(chǔ)學(xué)C++','明日科技',79.8]

['Python學(xué)習(xí)手冊(cè)'/馬克?盧茨',219,0]

['Python數(shù)據(jù)結(jié)構(gòu)與算法分析'布拉德利?米勒',79.0]

請(qǐng)輸入關(guān)鍵詞:Python

符合要求的書單為：

['Python編程從入門到實(shí)踐'埃里克?馬瑟斯',89.0]

[,Python基礎(chǔ)教程','MagnusLieHetland,,99.0]

['Python學(xué)習(xí)手冊(cè)'；馬克?盧茨',219,0]

['Python數(shù)據(jù)結(jié)構(gòu)與算法分析'布拉德利?米勒',79.0]

共找到4本

價(jià)格最貴的是：['Python學(xué)習(xí)手冊(cè)'馬克?盧茨,219.0]

⑴觀察運(yùn)行結(jié)果,如果希望在書目清單列表中查找書名中包含關(guān)鍵字的書,比較合適的方

法是(選填/質(zhì)序查找”或“二分查找)

⑵實(shí)現(xiàn)上述功能的Python程序如下,請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。

#列表book中存儲(chǔ)了書的信息,內(nèi)容略

n=len(book)

Print("書目清單為：”)

foriinrange(0,n,3):

print(book[ili+3])

第22頁(yè)共45頁(yè)

keyword=input（"請(qǐng)輸入關(guān)鍵詞："）

Print（"符合要求的書單為：”）

count,maxprice,posi=0,0,-l

①

whilei<=n-3:

if②：

print（book[i：i+3]）

count+=1

ifmaxprice<book[i+2]：

maxprice=book[i+2]

③

i=i+3

PrintC'共找到",count,"本"）

ifposi=="l:

Print（〃對(duì)不起,沒有找到你要的書!”）

else：

Print（"價(jià)格最貴的是:",book[postposi+3]）

答案⑴I褥查找（2）φi=θ②keywordinbook[i]③PoSi=i

14.（2022紹興諸暨期中,⑼小明學(xué)了排序和查找算法后,編寫了一個(gè)處理成績(jī)的程序,功

能如下:程序運(yùn)行時(shí),首先從Excel文件中讀取n個(gè)學(xué)生的技術(shù)成績(jī)存儲(chǔ)在列表a中,并對(duì)

列表中的數(shù)據(jù)按升序進(jìn)行排序;輸入成績(jī)key,統(tǒng)計(jì)并輸出共有多少位同學(xué)的成績(jī)大于該

成績(jī)。

實(shí)現(xiàn)上述功能的Python程序如下,請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。

第23頁(yè)共45頁(yè)

#從Excel文件中讀取n個(gè)學(xué)生的技術(shù)成績(jī)存儲(chǔ)在列表a中,代碼略

#對(duì)列表a中的元素進(jìn)行升序排序

n=len(a)

foriinrange(n-l)：

forjinrange(O,n-i-l):

if①：

a[j],a∣j+I]=a∣j+l],a[j]

print(a)

#輸入成績(jī)key,統(tǒng)計(jì)并輸出共有多少位同學(xué)的成績(jī)大于該成績(jī)

key=int(input(zzpleaseinputkey："))

i,j=O,n-l

whilei<=j:

m=(i+j)∕∕2

if②：

j=m-l

else：

i=m+l

Print(〃共有"③+"位同學(xué)大于等于該成績(jī)。")

答案①a[j]>a[j+l]②key<a[m]③str(n-i)

15.計(jì)算組合數(shù)C器已知CS=CL+醴=,我們可以把餅看成二叉樹的根,把C%]和C%=

分別看成左、右子節(jié)點(diǎn),這兩個(gè)節(jié)點(diǎn)又可以按照同樣的規(guī)律得到各自的左、右子節(jié)點(diǎn)。隨

著二叉樹向下擴(kuò)展,左邊的子節(jié)點(diǎn)最終會(huì)變成C卜1,而右邊的子節(jié)點(diǎn)最終會(huì)變成喘T=1。

第24頁(yè)共45頁(yè)

⑴若采用遞歸算法計(jì)算組合數(shù)公式％=C^i+U],當(dāng)滿足邊界條件時(shí),函數(shù)

C(n,k)的值等于Io

⑵實(shí)現(xiàn)該算法的程序如下：

defC(n,k):

if①：

return1

else：

return②

n,k=map(int,input().split())

ans=C(n,k)

print(ans)

完善上述代碼。在劃線處填入合適的代碼語(yǔ)句:①：②。

答案⑴k=0或n=k⑵①k==0orn=k

(2)C(n-l,k)+C(n-l,k-l)

16.漢諾塔游戲的裝置是一塊銅板,上面有三根柱子,其中最左側(cè)一根柱子上放著從大到小

的∏個(gè)圓盤。游戲的目標(biāo)是把所有圓盤從最左側(cè)一根柱子上移動(dòng)到最右側(cè)一柱子針上,

中間一個(gè)柱子作為過(guò)渡。游戲規(guī)定每次只能移動(dòng)一個(gè)圓盤,并且大盤子不能壓在小盤子上

面。漢諾塔游戲可以抽象為如圖所示的模型:從左到右有A、B、C三根柱子,其中A柱

子上面放著從大到小的n個(gè)圓盤,現(xiàn)要求按一定規(guī)則,將A柱子上的圓盤移到C柱子上去。

ABC

抽象后的漢諾塔模型

第25頁(yè)共45頁(yè)

例如,當(dāng)n=2時(shí),一個(gè)可行的移動(dòng)方案為:先將A柱上端盤子移到B柱,然后再將A柱上端

盤子移到C柱,最后將B柱上端盤子移到C柱。用符號(hào)表示為:A-B,A-C,B→C.

⑴當(dāng)n=3時(shí),用符號(hào)表示3個(gè)圓盤的移動(dòng)情況是

⑵下列程序能夠使用符號(hào)表示n個(gè)圓盤的移動(dòng)過(guò)程,程序運(yùn)行后界面如下所示。請(qǐng)?jiān)趧?/p>

線處填入合適的代碼。

2個(gè)圓盤的移動(dòng)過(guò)程：

A-B,A-C,B-C

4個(gè)圓盤的移動(dòng)過(guò)程：

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→C

defhanoi(n,a,b,c):

ifn==l：#如果只有一個(gè)盤,直接將其從A柱移動(dòng)到C柱

Print(a,"—”,c,end=",")

else：

hanoi(①)#利用C柱中轉(zhuǎn),將n-1個(gè)盤從A柱移動(dòng)到B柱

Print(a,"τ”,c,end=T)#將第n個(gè)盤從A柱移動(dòng)到C柱

hanoi(②)#利用A柱中轉(zhuǎn),將n-1個(gè)盤從B柱移動(dòng)到C柱

#主函數(shù)部分

Print("2個(gè)圓盤的移動(dòng)過(guò)程：〃)

hanoi(2,"A",〃B","C")#利用B柱中轉(zhuǎn),將n個(gè)盤從A柱移動(dòng)到C柱

print()

Print("4個(gè)圓盤的移動(dòng)過(guò)程：〃)

第26頁(yè)共45頁(yè)

hanoi(4,"A","B","C")#利用B柱中轉(zhuǎn),將n個(gè)盤從A柱移動(dòng)到C柱

答案(1)A→C,A→B,C→B,A→C,B→A,B→C,A→C(2)①n-l,a,c,b②n-l,b,a,c

17.謝爾賓斯基三角形(SierPinSkitriangle)是一種分形,由波蘭數(shù)學(xué)家謝爾賓斯基在1915

年提出,它是一種典型的自相似集。其生成過(guò)程為：

1)取一個(gè)實(shí)心的三角形(多數(shù)使用等邊三角形)。

2)三邊中點(diǎn)的連線,將它分成四個(gè)小三角形。

3)去掉中間的那一個(gè)小三角形。

4)對(duì)其余三個(gè)小三角形重復(fù)上述步驟。

可以設(shè)計(jì)如下算法:先繪制一個(gè)大的綠色正三角形做底版,然后調(diào)用遞歸函數(shù)SPlit()繪制

謝爾賓斯基三角形。函數(shù)SPIit()先找到三角形三條邊的中點(diǎn),將其等分成4個(gè)全等三角形,

將中間的正三角形填充為白色,再遞歸處理另外3個(gè)綠色三角形,直到三角形的邊長(zhǎng)小于

某個(gè)特定值(例如40)為止。

能夠?qū)崿F(xiàn)上述功能的Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。

importturtleastt

#構(gòu)造三角形,并為其填充顏色C

deftriangle(xLy1,x2,y2,x3,y3,c):

tt.penup()；tt.goto(xl,yl)

tt.pendown()

tt.colour(c)

tt.begin_fill()

tt.goto(x2,y2)；tt.goto(x3,y3)；tt.goto(xl,yl)

第27頁(yè)共45頁(yè)

tt.endfill()

defSPIit(XLyI,x2,y2,x3,y3):

ifabs(xl-x2)>=40:

x4,y4=(xI÷x2)∕2z(yl+y2)∕2

x5fy5=(x2+x3)∕2,(y2+y3)∕2

x6,y6=①

triang?e(@)

split(xl,yI,x4,y4,x6,y6)

SPIit(X4,y4,x2,y2,x5,y5)

split(③)

#先繪制最大的三角形做底版,三點(diǎn)坐標(biāo)定位(xl,yl),(x2,y2),(x3,y3)

Xl,y1=-200,0

x2,y2=200,0

x3,y3=0,(400*400-200*200)**0.5

triangle(xLy1zx2,y2,x3,y3,“green")

SPIit(XI,yl,x2,y2,x3,y3)

tt.done()

答案①(x3+xl)∕2,(y3+yl)∕2

②x5,y5,x6,y6,x4,y4,"white”

③x6,y6,x5,y5,x3,y3

18.二叉排序樹也稱為二叉查找樹,它具有如下特性：

⑴若它的左子樹非空很!J左子樹上所有節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值。

第28頁(yè)共45頁(yè)

⑵若它的右子樹非空廁右子樹上所有節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。

⑶左、右子樹本身又各是一棵二叉排序樹。

如圖所示,就是一棵典型的二叉排序樹。

阿福編寫了一個(gè)二叉排序樹類,基本實(shí)現(xiàn)了二叉排序樹的插入節(jié)點(diǎn)、輸出節(jié)點(diǎn)和查找節(jié)點(diǎn)

功能。程序代碼如下所示,請(qǐng)根據(jù)代碼注釋,在劃線處填入合適的代碼。

classBTNode：#二叉樹節(jié)點(diǎn)類

de(init(seICdata=NoneJeft=None,right=None)：

self.data=data

Selfleft=Ieft

self.right=right

#二叉排序樹類

classSBTree:

def_init_(self^root=None)：

self.root=root

definsert(selfzroot,data)：#插入新節(jié)點(diǎn)

ifself.rootisNone：#空樹

self.root=BTNode(data)

elifdata<root.data:#比根節(jié)點(diǎn)小則插入到左子樹中

ifroot.leftisNone：

①

else：

第29頁(yè)共45頁(yè)

self.insert(root.leftzdata)

else：#否則插入到右子樹中

ifroot.rightisNone：

root.right=BTNode(data)

else：

②

#按非遞減次序(即中序遍歷)輸出節(jié)點(diǎn)

definorder(self^root)：

ifrootisNone：

return③

print(root.datazend=",)

④

#二分查找數(shù)據(jù)值為key的節(jié)點(diǎn)

defSearCh(SelCrOOt,key)：

ifrootisNoneorroot.data=key:

returnroot

elifkey<root.data:#比root小則到左子樹中尋找

return⑤

else：

return@

if^name=,,mai∏,z:

a=[3,5,2,6,4,l]

print(a)

sbt=SBTree()

第30頁(yè)共45頁(yè)

foriina：

sbt.insert(sbt.rooζi)

sbt.inorder(sbt.root)

print()

k=int(input())

p=sbt.search(sbt.rooζk)

ifpisnotNone：

print(k,p.data)

else：

print(k,p)

答案①root.Ieft=BTNode(data)

(2)self.insert(root,right,data)

(3)self.inorder(root,left)

@self.inorder(root,right)

?self.search(root,left,key)

(6)self.search(root,right,key)

19.(2022名校協(xié)作體,16)某會(huì)務(wù)組根據(jù)參會(huì)者到達(dá)指定上車點(diǎn)的時(shí)間和每位參會(huì)者可以

等待的時(shí)間信息,安排車輛接送參會(huì)者去賓館(不考慮車子座位數(shù)量)。參會(huì)者到達(dá)上車點(diǎn)

的時(shí)間和可以等待的時(shí)間用長(zhǎng)度為7的字符串表示,例如“08：152”表示參會(huì)者當(dāng)天8點(diǎn)

15分到達(dá)上車點(diǎn),最多等待2分鐘(每個(gè)人的等待時(shí)間都小于10),那么該參會(huì)者最晚8點(diǎn)

17分出發(fā)去賓館(若有8點(diǎn)17分剛到的參會(huì)者也一同出發(fā))。編寫Python程序,統(tǒng)計(jì)接送

第31頁(yè)共45頁(yè)

n個(gè)參會(huì)者所需的最少車輛數(shù)。運(yùn)行程序,顯示所有參會(huì)者提交的信息,按到達(dá)時(shí)間先后排

列,再顯示所需的最少車輛數(shù)程序運(yùn)行結(jié)果如圖所示。

⑴若將圖中第4行“08：154”數(shù)據(jù)改為“08：151?,程序輸出的結(jié)果是否會(huì)發(fā)生改變(A.

會(huì)改變B?不會(huì)改變)。

08:122

08:143

08:152

08:154

08:171

08:171

08:173

08:194

08:214

08:234

接送所有參會(huì)者最少需要3輛車I

⑵實(shí)現(xiàn)上述功能的部分Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。

a=[,08:154,/08:143','08:234','08:152','08:122','08:171','08:173','08:19

4','08:214','08:17f]

deftran(strl)：

ss=int(strl[：2])*60+int(strl[3:6])

returnss

foriinrange(len(a)-l):

forjinrange(len(a)-lriz-l):

ifa[j]<a[j-l]:

a[i](a[j-l]=a∣j-l],a∣j]

n=len(a)

b=[]

c=[]

foriinrange(n):

b.append(tran(a[i][：5]))

第32頁(yè)共45頁(yè)

c.append(b[-l]+int(a[i][6：]))

forjinrange(i,0,-l):

①

ifc[k]>c[j]:

b[k],b[j]=b∣j],b[k]

c[k],c[j]=c[j],c[k]

else：

break

sum=0

flag=[Falseforiinrange(n)]

foriinrange(n):

ifflag[i]==False:

forjinrange(i,n):

if②:

flag[j]=True

③

print(,接送所有參會(huì)者最少需要％d輛車'%sum)

答案(I)A(2)φk=j-l?b[j]<=c[i]或flag==FalSeandbUk=C[i]③SUm+=I

20.(2023屆十校聯(lián)盟10月聯(lián)考,15)小丁是一位電影發(fā)燒友,尤其鐘爰喜劇片和動(dòng)作片。他

設(shè)計(jì)了一個(gè)程序,根據(jù)某部電影的鏡頭數(shù)據(jù)預(yù)測(cè)出類型,這類操作可利用k-近鄰分類算法

來(lái)實(shí)現(xiàn),該算法核心思想是:一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于

某一類別,則該樣本也屬于這個(gè)類別。小丁讀取“movie.csv”數(shù)據(jù)集文件,如圖a所示,內(nèi)容

是一些電影的搞笑鏡頭和打斗鏡頭數(shù)目及類型。現(xiàn)要實(shí)現(xiàn)如下功能:輸入某部電影的搞笑

第33頁(yè)共45頁(yè)

鏡頭和打斗鏡頭數(shù)目后,輸出可能的類型,如圖C所示,并繪制該數(shù)據(jù)集文件和輸入的電影

在平面坐標(biāo)系的分布特點(diǎn)圖,如圖b所示。例如:輸入搞笑鏡頭40和打斗鏡頭40,判斷屬

于哪類,通過(guò)如下步驟實(shí)現(xiàn):

①計(jì)算點(diǎn)(40,40)和其余所有點(diǎn)的距離(兩點(diǎn)間的距離計(jì)算公式：

22

di2=√(×1-X2)+(Yi-y2));

②將所有樣本按照距離升序排序；

③假設(shè)k=3,取前k個(gè)距離的樣本；

④統(tǒng)計(jì)出在前k個(gè)距離中,出現(xiàn)頻次最多的類別則(40,40僦屬于該類別可能是喜劇片。

Nlmovie.CSV-記事本

文件(F)編輯(E)格式(O)

funny,action,kind

83,26,喜劇片

15,98.動(dòng)作片

80,13,喜劇片

70,20,喜劇片

56,93,動(dòng)作片

5,105,動(dòng)作片

12,73,動(dòng)作片

圖a

?動(dòng)作片

10動(dòng)作片

κO)

動(dòng)作片???I作片浮昨片

動(dòng)作戶動(dòng)彳

8o動(dòng)作片.E片______

*?動(dòng)作片

水動(dòng)作片

黑6Q星劇片

H，

fc4封作片喜劇片

F劇片

喜劇片喜劇片:

喜劇片?莘劇片

20406080

搞笑鏡頭

圖b

請(qǐng)輸入搞笑鏡頭：40

請(qǐng)輸入打斗鏡頭：40

該影片可能是喜劇片

圖C

第34頁(yè)共45頁(yè)

[[83,26,'喜敏/45.221676218380054],[15,98,'動(dòng)作片z,63.15853069855251],[80,13,'喜盼?,48.25971

⑴若輸入的搞笑鏡頭為20,輸入的打斗鏡頭為80,則該影片可能是(選填:喜劇片/

動(dòng)作片)。

⑵實(shí)現(xiàn)上述功能的Python代碼如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。

importpandasaspd

importnumpyasnp

frommathimportsqrt

,,,z

movie=pd.read-csv(movie.csv)

x=int(input(〃請(qǐng)輸入搞笑鏡頭:〃))

y=int(input(〃請(qǐng)輸入打斗鏡頭:〃))

dist?[]

foriinrange(len(movie))：

d=sqrt((χ-movie.funny[i])**2+①)

dist.append(d)

movie[,,dis,']=dist

movie_list=np.array(movie),tolist()*將df對(duì)象轉(zhuǎn)成列表,如圖d所示,k=3

foriinrange(k):

forjinrange(Ien(InOVi-1)：

if②：

movielist[j]rmovie_list[j-l]=movie_list[j-l],movielist[j]

fUnny=Ojaction=O

foriinrange(k):

第35頁(yè)共45頁(yè)

if③：

funny÷=l

else：

action÷zzl

iffunny>action:

Print("該影片可能是喜劇片”)

else：

Print("該影片可能是動(dòng)作片”)

地會(huì)圖代碼略

答案⑴動(dòng)作片(2)@(y-movie.action[i])**2或(y-movic["action"[[i])**2或

(y-movie.at[i,"action"])**2

(2)movie-list[j][3]<movielist[j-1][3]或movielist[j][-l]<moviejist[j-l][-l]

(3)movielist[i][2]=="喜劇片"或"喜劇片"inmovie_list[i]

21.(2023屆浙南名校聯(lián)盟10月聯(lián)考,15)插補(bǔ)查找算法又稱為插值查找,它是二分查找算

法的改進(jìn)版。插補(bǔ)查找是按照數(shù)據(jù)的分布,利用公式預(yù)測(cè)鍵值所在的位置,快速縮小鍵值

所在序列的范圍,慢慢逼近,直到查找到數(shù)據(jù)為止。它類似于平常查字典的方法。

例如,我們?cè)诜值洳橐粋€(gè)發(fā)音以字母B開頭的文字時(shí),不會(huì)使用二分查找法找字典的中

間部分,因?yàn)楦鶕?jù)字典的順序可知,發(fā)音以B開頭的文字應(yīng)該在字典較前的部分,所以可以

從字典前部的某處開始查找。插補(bǔ)查找算法的所謂中間位置鍵值索引計(jì)算方式如下：

middle=low+(target-data[low])∕(data[high]-data[low])*(high-low)

參數(shù)說(shuō)明：

data：數(shù)據(jù)列表

middle：當(dāng)前需要比對(duì)的數(shù)據(jù)索引

第36頁(yè)共45頁(yè)

low：最左側(cè)數(shù)據(jù)的索引

high:最右側(cè)數(shù)據(jù)的索引

target：查找的目標(biāo)數(shù)據(jù)

現(xiàn)有150位學(xué)生（編號(hào)從1到150）參加軍訓(xùn)拉練,從中隨機(jī)選取9位同學(xué)作為旗手,如:[12,'

薛丁'],[45,'李強(qiáng)'],[56,'徐梓'],[66,‘鮑杰'],[77,‘黃怡'],[80,'余潮'],[97,'金維'],[101,‘方

茹[120,邛知?jiǎng)?現(xiàn)在某位家長(zhǎng)想知道方茹同學(xué)是否被選到,如果選到又是第幾個(gè)旗手,

為了解決這個(gè)問(wèn)題,可以使用插補(bǔ)查找算法。例如:查找方茹,需要輸入IOl進(jìn)行查找,具體

如圖所示：

旗手如下：

（編號(hào):⑵[薛丁]（編號(hào)：45）[李強(qiáng)]（編號(hào)：56）[徐梓]（編

號(hào)：66）[鮑杰]（編號(hào)：77）[黃怡]（編號(hào)：80）[余潮]（編

號(hào)：97）[金維]（編號(hào)：101）[方茹]（編號(hào):120）[陳金]

請(qǐng)輸入需要查找的學(xué)生編號(hào):101

正在查找.....

正在查看第7個(gè)旗手[[97,'金維']]

正在查看第8個(gè)旗手皿01,'方茹']]

方茹同學(xué)是第8個(gè)旗手

⑴在題目所示案例中,若使用插補(bǔ)查找算法查找45號(hào)旗手,則該過(guò)程中訪問(wèn)到的數(shù)據(jù)依

次為O

⑵實(shí)現(xiàn)上述功能的Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。

defsearch（data,num）：#定義查找函數(shù),參數(shù)是原數(shù)列d