高中信息技术 （高考复习）八数据结构与算法（习题部分）

专题八数据结构与算法

考点集训

考点一数据结构与算法效率

L下列有关数据结构与算法关系的描述中,错误的是()

A.数据结构与算法的关系可表示为:程序+数据结构=算法

B.算法设计必须考虑到数据结构,算法设计不可能独立于数据结构

C算法的设计同时伴有数据结构的设计,两者都是为最终解决问题服务的

D.数据结构是编程思想,算法则是这些思想的逻辑基础

答案D

2.某手机APP为了增加热度,采用“签到换积分得奖品”的形式来吸引用户。签到积分的规

则为:第1天签到得1分,第2天签到得2分,第3天签到得3分,……第n天签到得n分。

统计连续签到n天可以获得的总积分。通过分析可知总积分为1+2+3+…+n,利用程序实

现计算总积分,时间复杂度最低的是()

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

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

答案A

3.常见算法时间复杂度函数的增长率如图所示。

则当问题规模n=100时,下列时间复杂度中效率最高的是()

第1页共45页

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)

则该算法的时间复杂度为()

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

答案C

5.分析以下程序段的时间复杂度。

a=b=c=l

foriinrange(3zn÷l):

c=a+b

a=b

b=c

答案时间复杂度为O(n)

6.有以下Python程序段：

defjishu(n)：

s=0

第2页共，45页

whilen>0：

s+=n%2

n∕∕=2

returns

n=int(input(〃输入一个正整数:〃))

ans=yishu(n)

print(ans)

阅读上述代码,回答以下问题。

⑴该程序运行后,输入整数23,输出结果为.

⑵若输入整数23,则程序中自定义函数jishu()中语句“s+=n%2”执行的次数是。

⑶函数jishu()的时间复杂度为(单选:A.O(n)B.O(log2n))o

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

考点二迭代与递归

L从微信LO版本到微信8.0版本不断更新的过程可以看出,一款产品从上市到最终框架

的成型,是不断试错、不断根据用户体验反馈快速调整和完善得到的结果。这个例子体现

的算法思想是()

A枚举B.递归C.解析D.迭代

答案D

2.通过函数调用把大问题分解为更小规模且相同的问题的组合,并对最小规模的问题给

出简单解,这种解决问题的方法称为()

A.枚举B.递归C.解析D.迭代

答案B

3.在计算机内实现递归算法时所需的数据结构是()

第3页共45页

A∙数组B栈C.队列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])

运行该程序段,输出结果不可能是()

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)

程序执行时,输入n的值为25则输出的结果为()

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

答案C

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

第4页共45页

defdoit(x):

ifx>=6:

ans=l

else：

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

returnans

print(doit(3))

程序运行后,输出的结果为()

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

答案C

7.(2023浙江1月选考,11,2分)定义如下函数：

defrf(n):

ifn<3:

returnn

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

执行语句v=rf(5),函数rf被调用的次数是()

A.lB.5C.7D.15

答案C

考点三数据排序

L利用冒泡排序按从后至前的比较顺序给数组[15,63,88,23,69,71,20,53]排序,第三遍冒泡

加工之后的数组结果是()

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

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

第5页共45页

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]

经过该程序段“加工”后,列表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）对一组数据采用冒泡排序算法进行排序,若第一趟排序完成后

的数据序列为31,24,23,15,20,10,则该数据序列的原始顺序不可能是（）

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页共45页

答案D

4.(2022台州玉环月考,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)

该程序段运行后,列表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页共45页

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

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

print(a)

为实现n个数的升序排序,划线处应填()

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个互不相等的元素,即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]

该程序段实现的是()

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页共45页

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)

排序后,数组a=o

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

考点四数据查找

1.(2022Z20名校联盟联考⑼某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

数组a中的元素为“58,69,78,80,83,84,90,90,95”,则执行该程序段后,数组S中的元素不可

能为()

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

第9页共，45页

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

答案D

2.(2022百校联考,12)某程序段如下：

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

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

key=int(input(〃请输入待查数据:〃))

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)

执行该程序后,当输入的key值为15时,输出的结果是()

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

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

答案A

3.(2022名校协作体联考,12)某算法的Python程序段如下：

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

第10页共45页

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],该程序段执行后,下列说法不正碉的是()

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

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

答案B

4.(2022诸暨海亮高中月考,12)下列程序实现了输入k,找出大于k的数据的起始索引位置

并显示。

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页共45页

ι=m

L=____

Print（">",k,''的数据索引起始位置为",L）

上述程序段横线处语句依次为（）

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]）

程序执行后,下列说法正确的是（）

A.变量C的值为4

B.程序输出的结果为Lettuce

C.变量left的值为2

第12页共45页

D.变量right的值为3

答案B

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

#列表a存放整数升序数据,代码略

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⑴

输入待查找数据执行该程序段后,下列选项中,列表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

专题集训

第13页共45页

1.(2023届十校联盟10月联考,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))

执行该程序段,依次输入11和2,则输出的结果是()

A.IOllB.IlOlC.OlOllD.HOlO

答案C

3.(2023届浙南名校联盟10月联考,8)小王走楼梯,每次走1个台阶或2个台阶,问小王走n

个台阶时,有多少种不同的走法?现编写代码如下：

defupstairs(n):

ifn==0orn==l:

return1

else：

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

n=int(input(,请输入楼梯有几个台阶：'))

way=upstairs(n)

print(way)

第14页共45页

当输入的楼梯有10个台阶时,请问有多少种走楼梯的方法（）

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

答案B

4.（2022丽水质量监控,12）某二分查找算法的Python程序段如下：

key=int（input（"请输入待查数据值：”））

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（"查找成功!遍历的数据〃+s）

else：

Print（"没有找到!”）

输入待直数据值为23,执行该程序段,则输出的结果是（）

第15页共45页

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,程序运行结束后,下列描述不正确的是（）

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

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

答案A

6.（2022宁波九校联考期末,12）某二分查找算法的Python程序段如下,运行该段代码后,

输出的结果不可能是（）

importrandom

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

第16页共45页

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浙江开学考,12)峰值元素指数组中其值大于左右相邻值的元素,如序列3、8、4、

1中8为峰值元素。一个数组r包含多个峰值元素,现需要找出其中一个峰值元素所在的

位置(默认第一个数的左侧和最后一个数的右侧为0,即序列1、2、3中3也为峰值元素)。

现有实现该功能的Python程序如下：

i=0；j=6

whilei<j:

m=(i+j)∕∕2

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

i=m+l

第17页共45页

else：

j=m

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

数组a=[10,2,25,17,20,21,9]执行该程序后输出的值为

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

则程序运行结束后,变量Cnt的值为()

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

答案B

9.有如下程序段：

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

n=len(d)

key=input(,zpleaseinputkey：〃)

第18页共45页

ans=O

i=O

〃〃

s=

whilei<=n-l:

ifd[i]>key:

s=s+str(i)

i=i+l

print(s)

程序运行时,输入float,输出结果为()

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页共45页

else：

j=m-l

ss=ss+z,<<z,

print(ss)

执行该程序段,输出的内容为()

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

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

答案C

11.(2022诸暨期末,15)火车调度台是实现火车车厢整理的平台,当相邻2节车厢序号不符

合整理要求时,可以对调2节车厢,实现序号顺序调整。相邻2节车厢进行符合目标的交

换,和我们学习的冒泡排序思想一致,所以这个调度过程可以用冒泡排序实现。为了提高

效率,对冒泡排序做了优化,请完善下列代码：

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页共45页

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

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

1+(1*2)+(1*2*3)+…+(1*2*...*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)编写一个Python程序,功能为:输入关键字后,在书目清单列表

中查找书名中包含关键字的书,并统计数量,然后在所有找到的书目中找出价格最贵的书。

书目清单存储在列表book中,每本书包含三个内容:书名、作者和价格。程序运行示例如

下：

书目清单为：

【'Python编程从入门到实践'埃里克•马瑟斯',89.0]

「C语言程序设计入门教程'史蒂芬•普拉达'，187.0]

[,Javascript高级程序设计’,马特•弗里斯比’，129.0]

第21页共45页

ΓR语言实战','卡巴科弗',99.0]

CJava核心技术卷I'凯∙S•霍斯特曼',149,0]

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

['零基础学C++','明日科技',79.8]

['Python学习手册'/马克・卢茨',219,0]

['Python数据结构与算法分析'布拉德利•米勒',79.0]

请输入关键词:Python

符合要求的书单为：

['Python编程从入门到实践'埃里克•马瑟斯',89.0]

[,Python基础教程','MagnusLieHetland,,99.0]

['Python学习手册'；马克•卢茨',219,0]

['Python数据结构与算法分析'布拉德利•米勒',79.0]

共找到4本

价格最贵的是：['Python学习手册'马克•卢茨,219.0]

⑴观察运行结果,如果希望在书目清单列表中查找书名中包含关键字的书,比较合适的方

法是(选填/质序查找”或“二分查找)

⑵实现上述功能的Python程序如下,请在程序划线处填入合适的代码。

#列表book中存储了书的信息,内容略

n=len(book)

Print("书目清单为：”)

foriinrange(0,n,3):

print(book[ili+3])

第22页共45页

keyword=input（"请输入关键词："）

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（〃对不起,没有找到你要的书!”）

else：

Print（"价格最贵的是:",book[postposi+3]）

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

14.（2022绍兴诸暨期中,⑼小明学了排序和查找算法后,编写了一个处理成绩的程序,功

能如下:程序运行时,首先从Excel文件中读取n个学生的技术成绩存储在列表a中,并对

列表中的数据按升序进行排序;输入成绩key,统计并输出共有多少位同学的成绩大于该

成绩。

实现上述功能的Python程序如下,请在程序划线处填入合适的代码。

第23页共45页

#从Excel文件中读取n个学生的技术成绩存储在列表a中,代码略

#对列表a中的元素进行升序排序

n=len(a)

foriinrange(n-l)：

forjinrange(O,n-i-l):

if①：

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

print(a)

#输入成绩key,统计并输出共有多少位同学的成绩大于该成绩

key=int(input(zzpleaseinputkey："))

i,j=O,n-l

whilei<=j:

m=(i+j)∕∕2

if②：

j=m-l

else：

i=m+l

Print(〃共有"③+"位同学大于等于该成绩。")

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

15.计算组合数C器已知CS=CL+醴=,我们可以把饼看成二叉树的根,把C%]和C%=

分别看成左、右子节点,这两个节点又可以按照同样的规律得到各自的左、右子节点。随

着二叉树向下扩展,左边的子节点最终会变成C卜1,而右边的子节点最终会变成喘T=1。

第24页共45页

⑴若采用递归算法计算组合数公式％=C^i+U],当满足边界条件时,函数

C(n,k)的值等于Io

⑵实现该算法的程序如下：

defC(n,k):

if①：

return1

else：

return②

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

ans=C(n,k)

print(ans)

完善上述代码。在划线处填入合适的代码语句:①：②。

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

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

16.汉诺塔游戏的装置是一块铜板,上面有三根柱子,其中最左侧一根柱子上放着从大到小

的∏个圆盘。游戏的目标是把所有圆盘从最左侧一根柱子上移动到最右侧一柱子针上,

中间一个柱子作为过渡。游戏规定每次只能移动一个圆盘,并且大盘子不能压在小盘子上

面。汉诺塔游戏可以抽象为如图所示的模型:从左到右有A、B、C三根柱子,其中A柱

子上面放着从大到小的n个圆盘,现要求按一定规则,将A柱子上的圆盘移到C柱子上去。

ABC

抽象后的汉诺塔模型

第25页共45页

例如,当n=2时,一个可行的移动方案为:先将A柱上端盘子移到B柱,然后再将A柱上端

盘子移到C柱,最后将B柱上端盘子移到C柱。用符号表示为:A-B,A-C,B→C.

⑴当n=3时,用符号表示3个圆盘的移动情况是

⑵下列程序能够使用符号表示n个圆盘的移动过程,程序运行后界面如下所示。请在划

线处填入合适的代码。

2个圆盘的移动过程：

A-B,A-C,B-C

4个圆盘的移动过程：

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：#如果只有一个盘,直接将其从A柱移动到C柱

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

else：

hanoi(①)#利用C柱中转,将n-1个盘从A柱移动到B柱

Print(a,"τ”,c,end=T)#将第n个盘从A柱移动到C柱

hanoi(②)#利用A柱中转,将n-1个盘从B柱移动到C柱

#主函数部分

Print("2个圆盘的移动过程：〃)

hanoi(2,"A",〃B","C")#利用B柱中转,将n个盘从A柱移动到C柱

print()

Print("4个圆盘的移动过程：〃)

第26页共45页

hanoi(4,"A","B","C")#利用B柱中转,将n个盘从A柱移动到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)是一种分形,由波兰数学家谢尔宾斯基在1915

年提出,它是一种典型的自相似集。其生成过程为：

1)取一个实心的三角形(多数使用等边三角形)。

2)三边中点的连线,将它分成四个小三角形。

3)去掉中间的那一个小三角形。

4)对其余三个小三角形重复上述步骤。

可以设计如下算法:先绘制一个大的绿色正三角形做底版,然后调用递归函数SPlit()绘制

谢尔宾斯基三角形。函数SPIit()先找到三角形三条边的中点,将其等分成4个全等三角形,

将中间的正三角形填充为白色,再递归处理另外3个绿色三角形,直到三角形的边长小于

某个特定值(例如40)为止。

能够实现上述功能的Python程序如下,请在划线处填入合适的代码。

importturtleastt

#构造三角形,并为其填充颜色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页共45页

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(③)

#先绘制最大的三角形做底版,三点坐标定位(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左子树上所有节点的值均小于根节点的值。

第28页共45页

⑵若它的右子树非空厕右子树上所有节点的值均大于根节点的值。

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

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

阿福编写了一个二叉排序树类,基本实现了二叉排序树的插入节点、输出节点和查找节点

功能。程序代码如下所示,请根据代码注释,在划线处填入合适的代码。

classBTNode：#二叉树节点类

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)：#插入新节点

ifself.rootisNone：#空树

self.root=BTNode(data)

elifdata<root.data:#比根节点小则插入到左子树中

ifroot.leftisNone：

①

else：

第29页共45页

self.insert(root.leftzdata)

else：#否则插入到右子树中

ifroot.rightisNone：

root.right=BTNode(data)

else：

②

#按非递减次序(即中序遍历)输出节点

definorder(self^root)：

ifrootisNone：

return③

print(root.datazend=",)

④

#二分查找数据值为key的节点

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页共45页

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名校协作体,16)某会务组根据参会者到达指定上车点的时间和每位参会者可以

等待的时间信息,安排车辆接送参会者去宾馆(不考虑车子座位数量)。参会者到达上车点

的时间和可以等待的时间用长度为7的字符串表示,例如“08：152”表示参会者当天8点

15分到达上车点,最多等待2分钟(每个人的等待时间都小于10),那么该参会者最晚8点

17分出发去宾馆(若有8点17分刚到的参会者也一同出发)。编写Python程序,统计接送

第31页共45页

n个参会者所需的最少车辆数。运行程序,显示所有参会者提交的信息,按到达时间先后排

列,再显示所需的最少车辆数程序运行结果如图所示。

⑴若将图中第4行“08：154”数据改为“08：151»,程序输出的结果是否会发生改变(A.

会改变B∙不会改变)。

08:122

08:143

08:152

08:154

08:171

08:171

08:173

08:194

08:214

08:234

接送所有参会者最少需要3辆车I

⑵实现上述功能的部分Python程序如下,请在划线处填入合适的代码。

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页共45页

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(,接送所有参会者最少需要％d辆车'%sum)

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

20.(2023届十校联盟10月联考,15)小丁是一位电影发烧友,尤其钟爰喜剧片和动作片。他

设计了一个程序,根据某部电影的镜头数据预测出类型,这类操作可利用k-近邻分类算法

来实现,该算法核心思想是:一个样本在特征空间中的k个最相邻的样本中的大多数属于

某一类别,则该样本也属于这个类别。小丁读取“movie.csv”数据集文件,如图a所示,内容

是一些电影的搞笑镜头和打斗镜头数目及类型。现要实现如下功能:输入某部电影的搞笑

第33页共45页

镜头和打斗镜头数目后,输出可能的类型,如图C所示,并绘制该数据集文件和输入的电影

在平面坐标系的分布特点图,如图b所示。例如:输入搞笑镜头40和打斗镜头40,判断属

于哪类,通过如下步骤实现:

①计算点(40,40)和其余所有点的距离(两点间的距离计算公式：

22

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

②将所有样本按照距离升序排序；

③假设k=3,取前k个距离的样本；

④统计出在前k个距离中,出现频次最多的类别则(40,40僦属于该类别可能是喜剧片。

Nlmovie.CSV-记事本

文件(F)编辑(E)格式(O)

funny,action,kind

83,26,喜剧片

15,98.动作片

80,13,喜剧片

70,20,喜剧片

56,93,动作片

5,105,动作片

12,73,动作片

图a

•动作片

10动作片

κO)

动作片•∙⅞I作片浮昨片

动作户动彳

8o动作片.E片______

*•动作片

水动作片

黑6Q星剧片

H，

fc4封作片喜剧片

F剧片

喜剧片喜剧片:

喜剧片•莘剧片

20406080

搞笑镜头

图b

请输入搞笑镜头：40

请输入打斗镜头：40

该影片可能是喜剧片

图C

第34页共45页

[[83,26,'喜敏/45.221676218380054],[15,98,'动作片z,63.15853069855251],[80,13,'喜盼ʃ,48.25971

⑴若输入的搞笑镜头为20,输入的打斗镜头为80,则该影片可能是(选填:喜剧片/

动作片)。

⑵实现上述功能的Python代码如下,请在划线处填入合适的代码。

importpandasaspd

importnumpyasnp

frommathimportsqrt

,,,z

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

x=int(input(〃请输入搞笑镜头:〃))

y=int(input(〃请输入打斗镜头:〃))

distɪ[]

foriinrange(len(movie))：

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

dist.append(d)

movie[,,dis,']=dist

movie_list=np.array(movie),tolist()*将df对象转成列表,如图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页共45页

if③：

funny÷=l

else：

action÷zzl

iffunny>action:

Print("该影片可能是喜剧片”)

else：

Print("该影片可能是动作片”)

地会图代码略

答案⑴动作片(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届浙南名校联盟10月联考,15)插补查找算法又称为插值查找,它是二分查找算

法的改进版。插补查找是按照数据的分布,利用公式预测键值所在的位置,快速缩小键值

所在序列的范围,慢慢逼近,直到查找到数据为止。它类似于平常查字典的方法。

例如,我们在翻字典查一个发音以字母B开头的文字时,不会使用二分查找法找字典的中

间部分,因为根据字典的顺序可知,发音以B开头的文字应该在字典较前的部分,所以可以

从字典前部的某处开始查找。插补查找算法的所谓中间位置键值索引计算方式如下：

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

参数说明：

data：数据列表

middle：当前需要比对的数据索引

第36页共45页

low：最左侧数据的索引

high:最右侧数据的索引

target：查找的目标数据

现有150位学生（编号从1到150）参加军训拉练,从中随机选取9位同学作为旗手,如:[12,'

薛丁'],[45,'李强'],[56,'徐梓'],[66,‘鲍杰'],[77,‘黄怡'],[80,'余潮'],[97,'金维'],[101,‘方

茹[120,邛知匀'现在某位家长想知道方茹同学是否被选到,如果选到又是第几个旗手,

为了解决这个问题,可以使用插补查找算法。例如:查找方茹,需要输入IOl进行查找,具体

如图所示：

旗手如下：

（编号:⑵[薛丁]（编号：45）[李强]（编号：56）[徐梓]（编

号：66）[鲍杰]（编号：77）[黄怡]（编号：80）[余潮]（编

号：97）[金维]（编号：101）[方茹]（编号:120）[陈金]

请输入需要查找的学生编号:101

正在查找.....

正在查看第7个旗手[[97,'金维']]

正在查看第8个旗手皿01,'方茹']]

方茹同学是第8个旗手

⑴在题目所示案例中,若使用插补查找算法查找45号旗手,则该过程中访问到的数据依

次为O

⑵实现上述功能的Python程序如下,请在划线处填入合适的代码。

defsearch（data,num）：#定义查找函数,参数是原数列d