资源简介

(共105张PPT)
考点一　数据结构与算法效率
考点集训
1.下列有关数据结构与算法关系的描述中,错误的是 (　 )
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时,下列时间复杂度中效率最高的是 (　 )
A.O(nlog2n)　　B.O(log2n) C.O(n)　　D.O(n3)
答案 B
4.有如下Python程序代码:
n=int(input("n="))
ans1=ans2=0
for i in range(0,n,2):
　　for j in range(n):
　　ans1=ans1+1
　　ans2=ans2+ans1
print("ans1=",ans1,"ans2=",ans2)
则该算法的时间复杂度为 (　 )
A.O(1)　　B.O(n)　　C.O(n2)　　D.O(2n)
答案 C
5.分析以下程序段的时间复杂度。
a=b=c=1
for i in range(3,n+1):
　　c=a+b
　　a=b
　　b=c
答案　时间复杂度为O(n)
6.有以下Python程序段:
def jishu(n):
s=0
while n>0:
　s+=n%2
　n//=2
return s
n=int(input("输入一个正整数:"))
ans=jishu(n)
print(ans)
阅读上述代码,回答以下问题。
(1)该程序运行后,输入整数23,输出结果为　　　 。
(2)若输入整数23,则程序中自定义函数jishu()中语句“s+=n%2”执行的
次数是　　 。
(3)函数jishu()的时间复杂度为　　　 (单选:A.O(n)　B.O(log2n))。
答案 (1)4 (2)5 (3)B
考点二　迭代与递归
1.从微信1.0版本到微信8.0版本不断更新的过程可以看出,一款产品从上
市到最终框架的成型,是不断试错、不断根据用户体验反馈快速调整和
完善得到的结果。这个例子体现的算法思想是 (　 )
A.枚举　　B.递归　　C.解析　　D.迭代
答案 D
2.通过函数调用把大问题分解为更小规模且相同的问题的组合,并对最
小规模的问题给出简单解,这种解决问题的方法称为 (　 )
A.枚举　　B.递归　　C.解析　　D.迭代
答案 B
3.在计算机内实现递归算法时所需的数据结构是 (　 )
A.数组　　B.栈　　C.队列　　D.链表
答案 B
4.(2022绍兴诸暨期中,10)某Python程序段如下:
import random
fibo=[1]*11
for i in range(2,11):
　 fibo[i]=fibo[i-1]+fibo[i-2]
n=random.randint(1,10)
print(fibo[n])
运行该程序段,输出结果不可能是 (　 )
A.1　　B.21　　C.35　　D.89
答案 C
5.(2022绍兴诸暨期中,12)下列Python程序的功能是使用迭代算法求s的
值。
n=int(input("please input n:"))
s=0
for i in range(1,n):
　　if i%3==0:
　　　　 s=s+i
print("s=",s)
程序执行时,输入n的值为25,则输出的结果为 (　 )
A.s=84　　B.s=118　　C.s=108　　D.s=105
答案 C
6.(2022衢州期末,11)某Python程序段如下:
def doit(x):
　　if x>=6:
　　　　ans=1
　　else:
　　　　ans=3*doit(x+1)+2*doit(x+2)
　　return ans
print(doit(3))
程序运行后,输出的结果为 (　 )
A.17　　B.21　　C.61　　D.62
答案 C
7.(2023浙江1月选考,11,2分)定义如下函数:
def rf(n):
if n<3:
return n
return rf(n-1)+rf(n-3)
执行语句v=rf(5),函数rf被调用的次数是 (　 )
A.1　　B.5　　C.7　　D.15
答案 C
考点三　数据排序
1.利用冒泡排序按从后至前的比较顺序给数组[15,63,88,23,69,71,20,53]
排序,第三遍冒泡加工之后的数组结果是 (　 )
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]
答案 D
2.(2022绍兴诸暨期中,11)有如下Python程序段:
b=[56,80,10,31,24,52,66,49]
n=len(b)
for i in range(1,3):
　for j in range(0,n-i):
　　　if b[j]>b[j+1]:
　　　　b[j],b[j+1]=b[j+1],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.[10,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
答案 D
4.(2022台州玉环月考,12)有如下Python程序段:
a=[1] * 6
b=[96,88,84,91,99,80]
for i in range(6):
　 for j in range(i+1,6):
　　　if b[j] > b[i]:
　　　　 a[i] += 1
　　　else:
　　　　 a[j] += 1
print(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]
答案 B
5.(2022诸暨海亮高中月考,11)有如下程序段:
a=[92,22,11,98,96,71]
n=len(a)
for i in range(n):
　　for j in range(　　　　　　 ):
　　　　if a[j]>a[j+1]:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
print(a)
为实现n个数的升序排序,划线处应填 (　 )
A.range(i-1)　　B.range(n-2,i-1,-1) C.range(i,n)　　D.range(n-1,n-i-2,-1)
答案 B
6.(2023浙江1月选考,10,2分)列表s包含8个互不相等的元素,即s[0],s[1],s
[2],…,s[7],有如下 Python程序段:
n=8
for i in range(1,n-1):
　for j in range(1,n-i-1):
if s[j]>s[j-1]:
　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是 (　 )
A.s[0]到s[5]的降序排列 B.s[1]到s[6]的降序排列
C.s[1]到s[7]的升序排列 D.s[2]到s[6]的升序排列
答案 A
7.(2022绍兴诸暨期中,17)有如下Python程序段:
import random
n=6
a=[9,4,3,4,7,6]
for i in range(n-1,0,-1):
　　for j in range(0,i):
　　　if a[i]　　　　　　a[i],a[j]=a[j],a[i]
print(a)
排序后,数组a=　　　　　 。
答案 [3,4,4,6,7,9]
考点四　数据查找
1.(2022 Z20名校联盟联考,9)某Python程序如下:
import random
key=random.randint(35,45)*2
i=0;j=len(a)-1;s=[]
while i<=j:
　　m=(i+j+1)//2
　　s.append(a[m])
　　if key　　　j=m-1
　　else:
　　　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,58
答案 D
2.(2022百校联考,12)某程序段如下:
a=[9,15,19,20,23,36,78,87,96,100]
ans=[];i=0;j=9
key=int(input("请输入待查数据:"))
flag=False
while i<=j and not flag:
　　m=(i+j)//2
　　ans.append(a[m])
　　if a[m]==key:
　　　flag=True
　　elif a[m]>key:
　　　j=m-1
　　else:
　　　i=m+1
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
i,j,c=0,len(a)-1,0
while i<=j:
　m=(i+j+1)//2
　if a[m] >=key:
　　i=m+1
　else:
　　j=m-1
　c+=1
列表a=[23,21,19,18,16,15,14,11],该程序段执行后,下列说法不正确的是
(　 )
A.i的值为j+1　　B.i的值可能是8
C.j的值可能是5　　D.c的值一定是3
答案 B
4.(2022诸暨海亮高中月考,12)下列程序实现了输入k,找出大于k的数据的
起始索引位置并显示。
a=[1,3,3,5,5,7,10,11,12,15]
n=10
k=int(input())
i=-1
j=　　　
while i < j:
　　m=(i+j+1)//2
　　if k < a[m]:
　　　　j=　　
　　else:
　　　　i=m
L=　　
print(">",k,"的数据索引起始位置为",L)
上述程序段横线处语句依次为 (　 )
A.n　m-1　i　　B.n-1　m-1　i+1
C.n　m+1　i　　D.n-1　m+1　i+1
答案 B
5.(2022绍兴诸暨期中,15)某二分查找算法的Python程序段如下:
list1=["Carrot","Celery","Garlic","Lettuce","Mooli","Onion","Potato","
Tomato"]
key=list1[2]
left,right=0,len(list1)-1
c=0
while left<=right:
　 m=(left+right)//2
　 c=c+1
　 if list1[m]>key:
　　 right=m-1
　 else:
　　 left=m+1
print(list1[left])
程序执行后,下列说法正确的是 (　 )
A.变量c的值为4
B.程序输出的结果为Lettuce
C.变量left的值为2
D.变量right的值为3
答案 B
6.(2022诸暨期末,12)有如下二分查找程序段:
　#列表a存放整数升序数据,代码略
　key=int(input())
　f=[0]*9
　i=0
　j=8
　while i<=j:
　　　m=(i+j)//2
　　　f[m]=1
　　　if a[m]>key:
　　　　　 j=m-1
　　　else:
　　　　　i=m+1
　print(f)
输入待查找数据,执行该程序段后,下列选项中,列表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届十校联盟10月联考,9)有如下Python程序段:
def trans(m,n):
if m!=0:
r=m%n
return trans(m// n, n)+str(r)
else:
　　return "0"
a=int(input("a="))
b=int(input("b="))
print(trans(a,b))
专题集训
执行该程序段,依次输入11和2,则输出的结果是 (　 )
A.1011　　B.1101　　C.01011　　D.11010
答案　C
3.(2023届浙南名校联盟10月联考,8)小王走楼梯,每次走1个台阶或2个台
阶,问小王走n个台阶时,有多少种不同的走法 现编写代码如下:
def upstairs(n):
if n==0 or n==1:
return 1
else:
return upstairs(n-1)+upstairs(n-2)
n=int(input('请输入楼梯有几个台阶:'))
way=upstairs(n)
print(way)
当输入的楼梯有10个台阶时,请问有多少种走楼梯的方法 (　 )
A.88　　B.89　　C.90　　D.91
答案　B
4.(2022丽水质量监控,12)某二分查找算法的Python程序段如下:
key=int(input("请输入待查数据值:"))
d=[17,18,20,23,24,25,28,32,34,35]
f=False;s=" "
i=0;j=len(d)-1
while i<=j:
　　m=(i+j)//2
　　s=s+","+str(d[m])
　　if d[m]==key:
　　　 f=True
　　　 break
　　if key < d[m]:
　　　 j=m-1
　　else:
　　　 i=m+1
if f==True:
　　print("查找成功!遍历的数据"+s)
else:
print("没有找到!")
输入待查数据值为 23,执行该程序段,则输出的结果是 (　 )
A.25,20,24,23　　B.24,18,20,23 C.25,20,23　　D.24,20,23
答案 B
5.(2022衢州期末,12)某二分查找算法的Python程序段如下:
a=[14,17,18,19,19,22,22,22,28,28]
s=0
key=int(input("key:"))
L,R=0,len(a)-1
while L<=R:
　　m=(L+R)//2
　　s+=1
　　if a[m]>key:
　　　R=m-1
　　else:
　　　L=m+1
若输入key的值为22,程序运行结束后,下列描述不正确的是 (　 )
A.m的值是7　　B.s的值是3
C.L的值是8　　D.R的值是7
答案 A
6.(2022宁波九校联考期末,12)某二分查找算法的 Python程序段如下,运
行该段代码后,输出的结果不可能是 (　 )
import random
a=[10,20,30,40,50,60,70,80]
key=random.choice(a);i,j=0,len(a)-1
s=" "
while i<=j:
　　m=(i+j)//2
　　if key==a[m]:
　　　　s=s+"M";break
　　elif key　　　　j=m-1;s=s+"L"
　　else:
i=m+1;s=s+"R"
print(s)
A.LLM　　B.LRM
C.RRRM　　D.RRLM
答案 D
7.(2022浙江开学考,12)峰值元素指数组中其值大于左右相邻值的元素,如
序列3、8、4、1中8为峰值元素。一个数组r包含多个峰值元素,现需要
找出其中一个峰值元素所在的位置(默认第一个数的左侧和最后一个数
的右侧为0,即序列1、2、3中3也为峰值元素)。现有实现该功能的Python
程序如下:
i=0;j=6
while i　　m=(i+j)//2
　　if a[m+1]>a[m]:
　　　　i=m+1
　　else:
　　　　j=m
print("峰值位置是",i)
数组a=[10,2,25,17,20,21,9],执行该程序后,输出的值为 (　 )
A.0　　B.2　　c.5　　D.8
答案 C
8.有如下Python程序段:
a=[2,1,9,8,6,3]
cnt=0
for i in range(len(a)-1,0,-1):
flag=False
for j in range(i):
　　　　if a[j]>a[j+1]:
　　　　　a[j],a[j+1]=a[j+1],a[j]
　　　　　flag=True
　　cnt+=1
if not flag:
　　break
则程序运行结束后,变量cnt的值为(　　)
A.3　　　B.4　　　C.5　　　D.6
答案 B
9.有如下程序段:
d=["len","str","abs","chr","min","ord","int","max"]
n=len(d)
key=input("please input key:")
ans=0
i=0
s=" "
while i<=n-1:
　　if d[i]>key:
　　　　s=s+str(i)
　　i=i+1
print(s)
程序运行时,输入float,输岀结果为 (　 )
A.12567　　B.125678
C.014567　　D.0145678
答案 C
10.某二分查找算法的Python程序段如下:
a=[125,117,115,108,102,95,88,63,51,36]
key=108
i,j=0,len(a)-1
ss=" "
while i<=j:
　　m=int((i+j)/2+0.5)
　　ss=ss+str(m)
　　if key==a[m]:
　　break
　　if key　　i=m+1
　　ss=ss+">>"
　　else:
　　j=m-1
　　ss=ss+"<<"
print(ss)
执行该程序段,输出的内容为 (　 )
A.4<<1>>2>>3　　B.5<<2<<4>>3
C.5<<2>>4<<3　　D.5<<2>>4>>3
答案 C
11.(2022诸暨期末,15)火车调度台是实现火车车厢整理的平台,当相邻2节
车厢序号不符合整理要求时,可以对调2节车厢,实现序号顺序调整。相
邻2节车厢进行符合目标的交换,和我们学习的冒泡排序思想一致,所以
这个调度过程可以用冒泡排序实现。为了提高效率,对冒泡排序做了优
化,请完善下列代码:
nums=[3,1,2,4,5,6]
　　①　
k=n-1
for i in range(n-1):
　　②　
　　for j in range(k):
　　　　if nums[j]>nums[j+1]:
　　　　　nums[j],nums[j+1]=nums[j+1],nums[j]
　　③　
ex_flag=True
　　if ex_flag:
　　　　break
print(nums)
答案　①n=len(nums)　②ex_flag=False　③k=j
12.下列Python程序的功能是:输入n的值(n≥5),用迭代法求1+(1*2)+(1*2*
3)+…+(1*2*…*n)的值。
程序运行效果如下所示,请在程序划线处填入合适的代码。
Please input n:10
1+(1*2)+(1*2*3)+…+(1*2*…*10)=4037913
n=int(input("Please input n:"))
s1=1
s2=0
i=1
while　　①　 :
s1=s1*i
　　②　
i+=1
print("1+(1*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]
['R 语言实战','卡巴科弗',99.0]
['Java 核心技术卷Ⅰ','凯·S·霍斯特曼',149.0]
['Python 基础教程','Magnus Lie Hetland',99.0]
['零基础学C++','明日科技',79.8]
['Python 学习手册','马克·卢茨',219.0]
['Python 数据结构与算法分析','布拉德利·米勒',79.0]
请输入关键词: Python
符合要求的书单为:
['Python 编程从入门到实践','埃里克·马瑟斯',89.0]
['Python 基础教程','Magnus Lie Hetland',99.0]
['Python 学习手册','马克·卢茨',219.0]
['Python 数据结构与算法分析','布拉德利·米勒',79.0]
共找到4本
价格最贵的是:['Python 学习手册','马克·卢茨',219.0]
(1)观察运行结果,如果希望在书目清单列表中查找书名中包含关键字的
书,比较合适的方法是　　　　 (选填:“顺序查找”或“二分查
找”)。
(2)实现上述功能的Python程序如下,请在程序划线处填入合适的代码。
#列表book中存储了书的信息,内容略
n=len(book)
print("书目清单为:")
for i in range(0,n,3):
　　print(book[i:i+3])
keyword=input("请输入关键词:")
print("符合要求的书单为:")
count,maxprice,posi=0,0,-1
　　①　
while i<=n-3:
　　if　　②　 :
　　　　print(book[i:i+3])
　　　　count+=1
　　　　if maxprice　　　　　maxprice=book[i+2]
　　③　
　　i=i+3
print("共找到",count,"本")
if posi==-1:
　　print("对不起,没有找到你要的书!")
else:
print("价格最贵的是:",book[posi:posi+3])
答案 (1)顺序查找 (2)①i=0　②keyword in book[i]　③posi=i
14.(2022绍兴诸暨期中,19)小明学了排序和查找算法后,编写了一个处理
成绩的程序,功能如下:程序运行时,首先从Excel文件中读取n个学生的技
术成绩存储在列表a中,并对列表中的数据按升序进行排序;输入成绩 key,
统计并输出共有多少位同学的成绩大于该成绩。
实现上述功能的Python程序如下,请在程序划线处填入合适的代码。
#从Excel文件中读取n个学生的技术成绩存储在列表a中,代码略
#对列表a中的元素进行升序排序
n=len(a)
for i in range(n-1):
　　for j in range(0,n-i-1):
　　　　if　　①　 :
　　　　　　a[j],a[j+1]=a[j+1],a[j]
print (a)
#输入成绩 key,统计并输出共有多少位同学的成绩大于该成绩
key=int(input("please input key:"))
i,j=0,n-1
while i<=j:
　　m=(i+j)//2
　　if　　②　 :
　　　　j=m-1
　　else:
　　　　i=m+1
print("共有"　　③　 + "位同学大于等于该成绩。")
答案　①a[j]>a[j+1]　②key15.计算组合数 。已知 = + ,我们可以把 看成二叉树的根,把
和 分别看成左、右子节点,这两个节点又可以按照同样的规律得
到各自的左、右子节点。随着二叉树向下扩展,左边的子节点最终会变
成 =1,而右边的子节点最终会变成 =1。
(1)若采用递归算法计算组合数公式 = + ,当满足边界条件　　
时,函数C(n,k)的值等于1。
(2)实现该算法的程序如下:
def C(n,k):
　if　　①　 :
　　　return 1
　else:
　　　return　　②　
n,k=map(int,input().split())
ans=C(n,k)
print(ans)
完善上述代码。在划线处填入合适的代码语句:①　　　　　　 ;②
。
答案 (1)k=0或n=k (2)①k==0　or　n==k
②C(n-1,k)+C(n-1,k-1)
16.汉诺塔游戏的装置是一块铜板,上面有三根柱子,其中最左侧一根柱子
上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根柱
子上移动到最右侧一柱子针上,中间一个柱子作为过渡。游戏规定每次
只能移动一个圆盘,并且大盘子不能压在小盘子上面。汉诺塔游戏可以
抽象为如图所示的模型:从左到右有A、B、C三根柱子,其中A柱子上面
放着从大到小的n个圆盘,现要求按一定规则,将A柱子上的圆盘移到C柱
子上去。

抽象后的汉诺塔模型
例如,当n=2时,一个可行的移动方案为:先将A柱上端盘子移到B柱,然后再
将A柱上端盘子移到C柱,最后将B柱上端盘子移到C柱。用符号表示为:A
→B,A→C,B→C。
(1)当n=3时,用符号表示3个圆盘的移动情况是 。
(2)下列程序能够使用符号表示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
def hanoi(n,a,b,c):
　　if n==1:#如果只有一个盘,直接将其从A柱移动到C柱
　　　print(a,"→",c,end=",")
　　else:
　　　hanoi(　　①　 )#利用C柱中转,将n-1个盘从A柱移动到B柱
　　　print(a,"→",c,end=",")#将第n个盘从A柱移动到C柱
　　　hanoi(　　②　 )#利用A柱中转,将n-1个盘从B柱移动到C柱
#主函数部分
print("2个圆盘的移动过程:")
hanoi(2,"A","B","C")#利用B柱中转,将n个盘从A柱移动到C柱
print()
print("4个圆盘的移动过程:")
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-1,a,c,b　②
n-1,b,a,c
17.谢尔宾斯基三角形(Sierpinski triangle)是一种分形,由波兰数学家谢尔
宾斯基在1915年提出,它是一种典型的自相似集。其生成过程为:
1)取一个实心的三角形(多数使用等边三角形)。
2)三边中点的连线,将它分成四个小三角形。
3)去掉中间的那一个小三角形。
4)对其余三个小三角形重复上述步骤。

可以设计如下算法:先绘制一个大的绿色正三角形做底版,然后调用递归
函数split()绘制谢尔宾斯基三角形。函数split()先找到三角形三条边的中
点,将其等分成4个全等三角形,将中间的正三角形填充为白色,再递归处
理另外3个绿色三角形,直到三角形的边长小于某个特定值(例如40)为
止。
能够实现上述功能的Python程序如下,请在划线处填入合适的代码。
import turtle as tt
#构造三角形,并为其填充颜色c
def triangle(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()
def split(x1,y1,x2,y2,x3,y3):
　　if abs(x1-x2)>=40:
　　　x4,y4=(x1+x2)/2,(y1+y2)/2
　　　x5,y5=(x2+x3)/2,(y2+y3)/2
　　　x6,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,0
x2,y2=200,0
x3,y3=0,(400*400-200*200)**0.5
triangle(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,y3
18.二叉排序树也称为二叉查找树,它具有如下特性:
(1)若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
(2)若它的右子树非空,则右子树上所有节点的值均大于根节点的值。
(3)左、右子树本身又各是一棵二叉排序树。
如图所示,就是一棵典型的二叉排序树。

阿福编写了一个二叉排序树类,基本实现了二叉排序树的插入节点、输
出节点和查找节点功能。程序代码如下所示,请根据代码注释,在划线处
填入合适的代码。
class BTNode:　　#二叉树节点类
　　def_init_(self,data=None,left=None,right=None):
　　　self.data=data
　　　self.left=left
　　　self.right=right
#二叉排序树类
class SBTree:
　　def_init_(self,root=None):
　　　self.root=root
　　def insert(self,root,data):#插入新节点
　　　if self.root is None:　　#空树
　　　　　self.root=BTNode(data)
　　　elif data　　　　　if root.left is None:
　　①　
　　　　　else:
　　　　　　 self.insert(root.left,data)
　　　else:　　#否则插入到右子树中
　　　　　if root.right is None:
　　　　　　 root.right=BTNode(data)
　　　　　else:
　　②　
　　#按非递减次序(即中序遍历)输出节点
　　def inorder(self,root):
if root is None:
　　　　　return 　　③　
　　　print(root.data,end=",")
　　④　
　　　#二分查找数据值为key的节点
　　def search(self,root,key):
　　　if root is None or root.data==key:
　　　　　return root
　　　elif key　　　　　return　　⑤　
　　　else:
　　　　　return　　⑥　
if_name_=="_main_":
　　a=[3,5,2,6,4,1]
　　print(a)
　　sbt=SBTree()
　　for i in a:
sbt.insert(sbt.root,i)
　　sbt.inorder(sbt.root)
　　print()
　　k=int(input())
　　p=sbt.search(sbt.root,k)
　　if p is not None:
　　　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名校协作体,16)某会务组根据参会者到达指定上车点的时间和
每位参会者可以等待的时间信息,安排车辆接送参会者去宾馆(不考虑车
子座位数量)。参会者到达上车点的时间和可以等待的时间用长度为7的
字符串表示,例如“08:15 2”表示参会者当天8点15分到达上车点,最多
等待2分钟(每个人的等待时间都小于10),那么该参会者最晚8点17分出发
去宾馆(若有8点17分刚到的参会者也一同出发)。编写Python程序,统计
接送n个参会者所需的最少车辆数。运行程序,显示所有参会者提交的信
息,按到达时间先后排列,再显示所需的最少车辆数,程序运行结果如图所
示。
(1)若将图中第4行“08:15 4”数据改为“08:15 1”,程序输出的结果是否
会发生改变　 (A.会改变　B.不会改变)。

(2)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
a=['08:15 4','08:14 3','08:23 4','08:15 2','08:12 2','08:17 1','08:17 3','08:19 4','
08:21 4','08:17 1']
def tran(str1):
　　ss=int(str1[:2])*60+int(str1[3:6])
　　return ss
for i in range(len(a)-1):
　　for j in range(len(a)-1,i,-1):
　　　if a [j]　　　　a[j],a[j-1]=a[j-1],a[j]
n=len(a)
b=[]
c=[]
for i in range(n):
　　b.append(tran(a[i][:5]))
　　c.append(b[-1]+int(a[i][6:]))
　　for j in range(i,0,-1):
　　①　
　　　　if c[k]>c[j]:
　　　　　　b[k],b[j]=b[j],b[k]
　　　　　　c[k],c[j]=c[j],c[k]
　　　　else:
　　　　　　break
sum=0
flag=[False for i in range(n)]
for i in range(n):
　　if flag[i]==False:
　　　　for j in range(i,n):
　　　　　　if　　②　 :
　　　　　　　　flag[j]=True
　　③　
print('接送所有参会者最少需要%d辆车'%sum)
答案 (1)A (2)①k=j-1　②b[j]<=c[i] 或flag==False and b[j]<=c[i]　③
sum+=1
20.(2023届十校联盟10月联考,15)小丁是一位电影发烧友,尤其钟爱喜剧
片和动作片。他设计了一个程序,根据某部电影的镜头数据预测出类型,
这类操作可利用k-近邻分类算法来实现,该算法核心思想是:一个样本在
特征空间中的k个最相邻的样本中的大多数属于某一类别,则该样本也属
于这个类别。小丁读取“movie.csv”数据集文件,如图a所示,内容是一
些电影的搞笑镜头和打斗镜头数目及类型。现要实现如下功能:输入某
部电影的搞笑镜头和打斗镜头数目后,输出可能的类型,如图c所示,并绘
制该数据集文件和输入的电影在平面坐标系的分布特点图,如图b所示。
例如:输入搞笑镜头40和打斗镜头40,判断属于哪类,通过如下步骤实现:
①计算点(40,40)和其余所有点的距离(两点间的距离计算公式:
d12= );
②将所有样本按照距离升序排序;
③假设k=3,取前k个距离的样本;
④统计出在前k个距离中,出现频次最多的类别,则(40,40)就属于该类别,
可能是喜剧片。




(1)若输入的搞笑镜头为20,输入的打斗镜头为80,则该影片可能是　　
(选填:喜剧片/动作片)。
(2)实现上述功能的 Python代码如下,请在划线处填入合适的代码。
import pandas as pd
import numpy as np
from math import sqrt
movie=pd.read_csv("movie.csv")
x=int(input("请输入搞笑镜头:"))
y=int(input("请输入打斗镜头:"))
dist=[]
for i in range(len(movie)) :
d=sqrt((x-movie.funny[i])**2+　① )
dist.append(d)
movie["dis"]=dist
movie_list =np.array(movie).tolist()　#将df对象转成列表,如图d所示,k=3
for i in range(k):
for j in range (len(movie_list)-1,i,-1):
if　② :
movie_list[j], movie_list[j-1]=movie_list[j-1], movie_list[j]
funny=0;action=0
for i in range(k):
if　③ :
funny+=1
else:
action+=1
if funny>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[i][2]=="喜剧片"或"喜剧片"in movie_list[i]
21.(2023届浙南名校联盟10月联考,15)插补查找算法又称为插值查找,它
是二分查找算法的改进版。插补查找是按照数据的分布,利用公式预测
键值所在的位置,快速缩小键值所在序列的范围,慢慢逼近,直到查找到数
据为止。它类似于平常查字典的方法。
例如,我们在翻字典查一个发音以字母B开头的文字时,不会使用二分查
找法找字典的中间部分,因为根据字典的顺序可知,发音以B开头的文字
应该在字典较前的部分,所以可以从字典前部的某处开始查找。插补查
找算法的所谓中间位置键值索引计算方式如下:
middle=low+(target-data[low])/(data[high]-data[low])*(high-low)
参数说明:
data:数据列表
middle:当前需要比对的数据索引
low:最左侧数据的索引
high:最右侧数据的索引
target:查找的目标数据
现有150 位学生(编号从1到150)参加军训拉练,从中随机选取9位同学作
为旗手,如:[12,'薛丁'],[45,'李强'],[56,'徐梓'],[66,'鲍杰'],[77,'黄怡'],[80,'余澍
'],[97,'金维'],[101,'方茹'],[120,'陈昀'],现在某位家长想知道方茹同学是否
被选到,如果选到又是第几个旗手,为了解决这个问题,可以使用插补查找
算法。例如:查找方茹,需要输入101 进行查找,具体如图所示:
旗手如下:
(编号:12)[薛丁](编号:45)[李强](编号:56)[徐梓](编号:66)[鲍杰](编号:77)
[黄怡](编号:80)[余澍](编号:97)[金维](编号:101)[方茹](编号:120)[陈昀]
请输入需要查找的学生编号:101
正在查找......
正在查看第7个旗手[[97,'金维']]
正在查看第8个旗手[[101,'方茹']]
方茹同学是第8个旗手
(1)在题目所示案例中,若使用插补查找算法查找45号旗手,则该过程中访
问到的数据依次为　　　 。
(2)实现上述功能的 Python程序如下,请在划线处填入合适的代码。
def search(data,num):　#定义查找函数,参数是原数列data和键值num
　　low=0　#定义变量用来表示低位
high=len(data)-1　#定义变量用来表示高位
print("正在查找.....")　#提示语
while low<=high and num!=-1:
left=data[low][0]
mid=low+(num-left)*(high-low)　① 　#请将表达式补充完整
print(f"正在查看第{mid+1}个旗手[{data[mid]} ]")
if numhigh=mid-1
elif num>data[mid][0]:
low=mid+1
else:
　　②　
return -1
num=0　#定义变量,用来输入键值
students=[[12,'薛丁'],[45,'李强'],[56,'徐梓'],[66,'鲍杰 '],[77,'黄怡'],[80,'余澍
'],[97,'金维'],[101,'方茹'],[120,'陈昀']]　#定义旗手列表
print("旗手如下: ")
for i in range(len(students)):
print(f'(编号:{students[i][0]})[{students[i][1]} ]',end='')#输出数列
print(' ')
number=0　#定义变量用来存储查找结果
num int(input("请输入需要查找的学生编号:"))　#输入查找键值
　　③　
if number==-1:　#判断查找结果是不是-1
print(f'没有找到编号为[{num}]的学生')
else:
print(f'{students[number][1]}同学是第{number+1}个旗手')
答案 (1)56 45 或(56,45)或[56,45]等其他答案
(2)①//(data[high][0]-data[low][0]) 或 //(data[high][0]-left)　②return mid
③number=search(students,num)
22.(2023届强基联盟10月统测,15)银行技术部编写风险控制算法,根据申
请贷款公司的收益率和信用度,从多个申请公司中挑选前n名公司发放贷
款,发放对象必须同时满足以下两个条件:
条件1:公司的收益率大于rate%;
条件2:公司的信用度在rank等级及以上。(A等高于B等,B等高于C等…
…)
将满足条件1和条件2的公司信息按收益率降序输出。
如所有公司信息为:[[1,20.0,'C'],[2,32.0,'A'],[3,46.0,'B'],[4,44.0,'A']]
满足A等级,且收益率大于20的输出情况为:
[4,44.0,'A'],[2,32.0,'A']]
(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。
(2)加框处代码有错,请改正。
#info=[[1,30.0,'C'],[2,44.0,'B'],……]其中[1,30.0,'C']分别表示公司编号、
收益率及信用度等级,代码略
m=len(info)
rate=float(input('输入收益率要求:'))
rank=input('输入等级要求:')
for i in range(m-1):
for j in range(m-1,　① ):
if info[j][2]<=rank:
if info[j][1]>info[j-1][1]and info[j-1][2]<=rank or　② :
info[j], info[j-1]=info[j-1], info[j]
if info[i][1]m=i
break
if i>0:
print('符合要求的公司为:',　③ )
else:
print('当前无符合要求的公司!')
答案 (1)①i,-1　②info[j-1][2]>rank　③info[0:m]或info[:m]
(2)info[i][1]rank
23.(2023届学军中学10月月考,15)学校为了使本校毕业生能以更好的状
态参加高考,都会创造条件向上级申请在本校设立标准化考点,让学生能
在本校参加考试。标准化考点要求很多,其中之一就是各考场内的座位
安排必须是蛇形排列,保证使用A、B卷的同学能完全错开,如图a所示。
小明用Python编写了一个模拟考场座位编排程序,程序运行结果如图b所
示,每个座位号占4位宽度右对齐。输出程序如下,请在划线处填入合适
的代码。


def px(lst):
for i in range(len(lst)-1):
k=i
for j in range(　① ):
if lst[j]>lst[k]:
k=j
if k!=i:
lst[i],lst[k]=lst[k],lst[i]
def gssc(t,n):　　　　#将字符t按n个字符宽度输出
t =" "* (n-len(t))+t
return t
n=int(input('请输入行数:'))
m=int(input('请输入列数:'))
a=[]
for j in range(m):
a.append([])
for i in range(n):
a[j].append(　② )
for i in range(m):
if　③ :
px(a[i])
for i in range(n):
st=" "
for j in range(m):
tmp ='A'
if a[j][i]%2==1:
tmp='B'
st+=　④ 　　#每个座位号按4位输出
print(st)
答案　①i+1,len(lst)　②i+j*n　③i%2==1
④gssc(str(a[j][i])+tmp,4)

展开更多......

收起↑