資源簡介

中小學教育資源及組卷應用平臺
2025新教材技術高考第一輪
專題八　數據結構與算法
考點過關練
考點一　數據結構與算法效率
1.(2024屆發展共同體聯考,12)以下兩個程序段的功能相同,實現的功能是:刪除列表a(元素個數為n)中的重復元素(只保留一個),并將剩下的元素降序輸出。
#程序段① #對列表a進行降序排序,代碼略 i=1 while i#程序段② max_num=max(a)#求出列表a中的最大值max_num b=[0]*(max_num+1) for i in range(0,n): 　 b[a[i]]+=1 for i in range(max_num,0,-1): 　 if b[i]>0: 　　　print(i,end=" ")
關于上述兩個程序段及功能的描述,正確的是(　　)
A.同樣的數據規模,兩個程序段的時間效率一樣
B.程序段①加框處語句是否執行不受列表a原數據的影響
C.程序段②加框處語句修改為“for i in range(1,max_num+1)”,輸出結果不變
D.在實現該功能的過程中,程序段②比程序段①需要更多的存儲空間
2.常見算法時間復雜度函數的增長率如圖所示。
則當問題規模n=100時,下列時間復雜度中效率最高的是(　　)
A.O(nlog2n)　　　　B.O(log2n)
C.O(n)　　　　D.O(n3)
3.有如下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)
4.有以下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.(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
2.(2023浙江6月選考,10,2分)定義如下函數:
def f(a,s):
　　if a>=s:
　　　　return a
　　else:
　　　　return f(a+1,s-a)
執行語句k=f(6,21)后,k的值為(　　)
A.6　　　B.7　　　C.8　　　D.9
3.(2024屆發展共同體聯考,10)定義如下函數:
def f(x,y):
　　if x<=2 or y>20:
　　　　return x+y
　　return f(x-1,y+1)
執行語句k=f(5,1)后,k的值為(　　)
A.6　　　B.7　　　C.8　　　D.9
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
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
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
考點三　數據排序
1.(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]的升序排列
2.(2024屆名校協作體聯考,10)有如下Python程序:
a=[12,45,45,63,0,0,63]
cnt=0
for i in range(1,len(a)):
　　j=i-1
　　t=a[i]
　　while j>=0 and t>a[j]:
　　　　 a[j+1]=a[j]
　　　　 j=j-1
　　　　 cnt=cnt+1
　　a[j+1]=t
print(cnt)
運行該程序后,輸出的結果是(　　)
A.8　　　B.10　　　C.11　　　D.13
3.(2024屆浙南名校聯考,12)有如下Python程序段:
from random import randint
x=randint(2,4)*2
a=[9,2,5,1,3,4,8,7]
n=len(a)
for i in range(0,n-1):
　　k=i
　　for j in range(i+1,x):
　　　 　if a[k]>a[j]:
　　　　　　k=j
　　if i!=k:
　　　 　a[k],a[i]=a[i],a[k]
print(a)
執行后,輸出結果不可能是(　　)
A. [1,2,3,4,5,7,8,9]
B. [1,2,3,4,5,9,8,7]
C. [1,2,5,9,3,4,8,7]
D. [1,2,3,4,5,9,7,8]
4.(2024屆天域全國名校協作體聯考,11)列表s存有4個整數,有如下Python程序段:
n=len(s)
f=[1]*n
for i in range(n-1):
　 　for j in range(i+1,n):
if s[j]>=s[i]:
　　f[j]+=1
else:
　　f[i]+=1
print(f)
該程序段實現的功能是標記列表中每個數值的名次值,名次排序的規則是(　　)
A.數值越大名次值越大,同數值先出現的名次值小
B.數值越大名次值越大,同數值先出現的名次值大
C.數值越大名次值越小,同數值先出現的名次值小
D.數值越大名次值越小,同數值先出現的名次值大
5.(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]
6.(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
考點四　數據查找
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
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]
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
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
5.(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]
6.(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("共有"　　③　　+ "位同學大于等于該成績。")
專題綜合練
題組一
1.(2024屆A9協作體返?？?11)有如下Python程序段:
import random
a=[1,3,4,6,6,6,9,9,11,12]
key=random.randint(2,5)*2
i,j=0,9
while i<=j:
m=(i+j)//2
if key　　j=m-1
else:
　　i=m+1
print(j)
執行該程序段后,輸出的結果不可能是(　　)
A.2　　　B.3　　　C.5　　　D.7
2.(2024屆Z20聯盟聯考,10)有如下Python函數:
def trans(num,n):
s="0123456789ABCDEF"
if num　　return s[num]
else:
　　return trans(num//n,n)+s[num%n]
執行語句a=trans(394,16)后,a的值為(　　)
A.19A　　　B.1810　　　C.180　　　D.18A
3.(2024屆七彩聯盟聯考,10)有如下程序段:
def cal(n):
if n<=1:
　　return 1
if n % 2==0:
　　return 2*cal(n-1)
return 1+cal(n-1)
執行語句k=cal(5),則k的值為(　　)
A.6　　　B.7　　　C.10　　　D.11
4.(2024屆強基聯盟統測,10)有如下程序段:
def fun(k):
if k==1:
　　return "1"
elif k%2==0:
　　return fun(k-1)+str(k%2)
else:
　　return str(k%2)+fun(k-1)
執行語句s=fun(5),則s 的值為(　　)
A."00111"　　　　B."11010"
C."11100"　　　　 D."10110"
5.(2024屆新陣地聯盟聯考,10)有如下Python程序:
import random
def func(n):
if n==1:
　　return 1
elif n==2:
　　return 2
elif n%2==1:
　　return 2*func(n-2)+func(n-1)
else:
　　return func(n-2)+2*func(n-1)
p=random.randint(3,6)
print(func(p))
執行程序后,輸出結果不可能為(　　)
A.4　　　B. 10　　　C. 12　　　D. 18
6.(2024屆天域全國名校協作體聯考,10)某遞歸函數如下所示:
def hs(m):
if m<=1:
　　f=1
else:
　　f=hs(m-1)+hs(m-2)
return f
ans=0
for i in range(5):
if hs(i)%2==1:
　　ans+=1
print(ans)
程序運行后,輸出的結果是(　　)
A.2　　　B.3　　　C.4　　　D.5
7.(2023十校聯盟聯考,12)某二分查找算法的Python程序段如下:
import random
key=random.randint(0,4)*2+5
n=10;ans=0
a=[4,5,5,8,9,11,11,13,15,17]
i=0;j=n-1
while i<=j:
m=(i+j)//2
if a[m]<=key:
i=m+1
else:
j=m-1
ans+=a[m]
print(ans)
執行該程序段后,ans的值不可能是(　　)
A.19　　　B.27　　　C.37　　　D.44
8.(2024屆七彩聯盟聯考,15)某工廠每天會收到多個訂單,有n臺機器對零件進行加工。為減少機器的損耗,需要在滿足所有訂單加工的情況下(訂單即到即加工),機器開啟數量盡量少。若開啟n臺機器不能滿足訂單即到即加工,則計算所有訂單最少的平均等待時間。若給定某天內所有的訂單信息,請計算需要開啟的機器數量以及訂單平均等待時間,代碼運行效果圖如圖所示(注意:若上一個訂單結束時間為9:00,下一個訂單開啟時間最早為9:00)。
訂單信息如下:(批次,到達時間,加工時間min)
(A1,9:00,30)(A2,11:30,50) (A3,10:40,50)(A4,10:00,60)(A5,9:20,40)(A6,11:00,20)(A7,10:20,40)(A8,9:30,20)
機器數量:2
2臺機器全部開啟,訂單平均等待2.5min
第1臺機器:
A1:09:00~09:30,A8:09:30~09:50,A4:10:00~11:00,A3:11:00~11:50
第2臺機器:
A5:09:20~10:00,A7:10:20~11:00,A6:11:00~11:20,A2:11:30~12:20
請回答下列問題:
(1)上圖所示的例子中,若機器有10臺,則只需要開啟　　　　臺機器。
(2)定義如下data_sort(a)函數,參數a為列表,列表中每個元素包含三個數據項,依次分別對應訂單批次、到達時間、加工時間(時間均轉為分鐘)。該函數實現將列表a按照訂單到達時間升序排序。
def data_sort(a):
for i in range(len(a)):
　　for j in range(len(a)-i-1):
　　　　if　　　　:
　　　　　a[j],a[j+1]=a[j+1], a[j]
①劃線處填入的語句為　　　　　　　,可實現上述功能。
②若將加框處語句寫錯為range(i,len(a)-1),則下列4組數據中,列表a的值為　　　(單選,填字母)時不能測試出問題。
A.[['A1',100,30],['A2',120,30],['A3',110,30],['A4',140,30],['A5',130,30]]
B.[['A1',120,30],['A2',110,30],['A3',100,30],['A4',130,30],['A5',140,30]]
C. [['A1',110,30],['A2' ,140,30],['A3',130,30],['A4',100,30],['A5',120,30]]
D.[['A1',110,30],['A2',120,30],['A3',130,30],['A4',140,30],['A5',100,30]]
(3)實現計算開啟機器數量的部分Python程序如下,請在劃線處填入合適的代碼。
def huan(n):
#將分鐘轉換為時間AA:BB格式,返回值為字符串,代碼略
#讀取文件中的信息,并存儲在列表order中,代碼略
data_sort(order)
n=int(input("機器數量:"))
for i in range(len(order)):
order[i].append(-1)
#order[i]追加一個元素-1
mach=[-1]* n
num, wait=0,0
for i in range(len(order)):
k=-1
time=-1
for j in 　?、佟　?
　　t1=mach[j]
　　if k==-1:
　　　　k=j
　　　　time=order[t1][1]+order
[t1][2]
　　else:
　　　　t2=mach[k]
　　　　if order[t1][1]+order[t1][2]　　　　　　k=j
　　　　　　time=order[t1][1]+order
[t1][2]
if k==-1 or num　 mach[num]=i
　 num+=1
　　else:
　 order[i][3]=mach[k]
　 mach[k]=i
　 if time>order[i][1]:
　　　　wait +=time-order[i][1]
　　　　order[i][1]=time
if numprint("只需開啟"+str(num)+"臺機器")
else:
print(str(n)+"臺機器全部開啟,訂單平均等待"+str(round(wait/len(order),2))+"min")
for i in range(num):
print('第'+str(i+1)+'臺機器: ')
p=mach[i]
ans=' '
while p!=-1:
　　ans=order[p][0]+':'+huan(order[p][1])+'~'+huan(order[p][1]+order[p][2])+','+ ans
　　p=　　③　　
　　print(ans[:-1])
9.(2024屆名校協作體聯考,15)有一款益智游戲,規則如下:軌道上有不同顏色的珠子連成珠串,玩家可以通過炮臺發射若干珠子,每次發射一顆珠子到珠串中的某位置,形成新的珠串。當新珠串中出現3顆及以上顏色相同的連續珠子時,這些連續的同色珠子會被消除,并獲得相應積分,若消除后仍有符合條件的同色珠子,會繼續被消除。記分規則為:在被消除的連續珠子中,前面3顆直接記3分,其余的珠子每顆記2分,例如有5顆相同顏色的連續珠子被消除,可獲得7分。程序運行過程如圖所示。
現軌道的珠串為:
-1->3->1->5->4->2->2->1->2->2
當前珠子的顏色為:1
請輸入當前發射位置:7
當前珠子的顏色為:1
請輸入當前發射位置:7
當前珠子的顏色為:4
請輸入當前發射位置:5
當前珠子的顏色為:4
請輸入當前發射位置:5
最終得分為11
軌道中剩余的珠串為:
-1->3->1->5
編寫程序模擬游戲的實現過程,珠子的顏色用數字表示,為方便處理,在珠串最前面加入一顆不可消除的珠子,顏色值為-1。請回答下列問題:
(1)若珠串為-1,2,2,3,3,2,2,將顏色為3的珠子發射到顏色為2和3的珠子之間,可獲得積分為　　　　。
(2)定義如下insert(t,pos)函數,函數功能是將顏色為t的珠子,插入到當前珠串中的第pos顆珠子后面(列表link存儲珠串的相關數據,例如link中某元素的值為[3,2],3表示某顆珠子的顏色,2表示與該珠子相鄰的下一顆珠子的存儲地址,變量 head保存珠串第一個珠子的存儲地址),請在劃線處填入合適的代碼。
def insert(t,pos): #將顏色為t的珠子,插入到當前珠串第pos顆珠子的后面
p=head
while pos>1:
　　pos-=1
　　p=link[p][1]
link.append(　　　　)
link[p][1]=len(link)-1
(3)定義如下fun()函數,函數功能是:查找珠串里最早出現的可消除珠串,函數返回ret,ret由該珠串起始珠子的前一顆珠子位置和該珠串的連續長度組成。
def fun():
p=head;st=head
pre=p
num=0
lastcolor=-1
ret=[-1,0]
while p!=-1:
　　t=link[p][0]
　　if t!=lastcolor:
　　　　if num>=3:
　　　　　　ret=[st,num]
　　　　　　break
　　　　lastcolor=t
　　　　st=pre
　　　　num=1
　　else:
　　　　num+=1
　　pre=p
　　p=link[p][1]
if num>=3:
ret=[st,num]
return ret
若將函數中加框處代碼刪除,會導致某些情況下無法得到符合函數功能的結果。調用fun()函數,下列4組數據中能測試出這一問題的是　　　　(單選,填字母)。
A.head=4
link=[[2,3],[1,0],[1,1],[2,-1],[-1,2]]
B.head=0
link=[[-1,1],[2,3],[2,4],[2,2],[1,-1]]
C. head=1
link=[[2,-1],[-1,3],[2,0],[1,4],[2,2]]
D.head=4
link=[[2,-1],[1,0],[1,1],[1,2],[-1,3]]
(4)實現模擬游戲過程的部分Python程序如下,請在劃線處填入合適的代碼。
def clear(g):#根據fun函數的返回值對珠串進行消除,并統計獲得本次消除的積分
p=g[0]
q=p
length=g[1]
ret=　?、佟　?
while length>=0:
　　q=link[q][1]
　　length-=1
link[p][1]=q
return ret
def traverl():
　　#將軌道中珠串按序輸出,代碼略
head=7
link=[[1,3],[1,8],[2,1],[5,5],[2,2],[4,4],[3,0],[-1,6],[2,9],[2,-1]]
print("現軌道的珠串為: ")
traverl()
points=0
que=[1,1,4,4]#保存炮臺中待發射珠子的顏色
qhead=0
qtail=4
while qhead!=qtail:
　　print("當前珠子的顏色為: ",que[ghead])
　　s=int(input("請輸入當前發射位置:"))
　　insert(que[qhead],s)
　　qhead+=1
　　g=fun()
　　while g!=[-1,0]:
　　　　points+=clear(g)
　　　　　?、凇　?
print("最終得分為",points)
print("軌道中剩余的珠串為: ")
traverl()
10.(2024屆發展共同體聯考,15)某業務服務大廳共有m個服務窗口(編號為0~m-1),服務大廳根據服務對象的優先等級(等級分為1~10,數字越大優先級越高)從高到低依次分配窗口并提供服務。某個時間段內(該時間段起始時刻各窗口都空閑著),服務對象按服務優先等級從高到低排隊后依次到空閑的窗口享受服務,服務優先等級相同時,先到達的先享受服務。由于辦理的業務不同,每個服務對象的服務時長(單位:分鐘)可能是不相同的。按照上述服務規則,問所有服務對象完成業務辦理需要多少時間。一個服務對象業務辦理結束,另一個服務對象馬上到該窗口接受服務,中間浪費的時間忽略不計。
圖a描述了5個服務對象的信息,按照服務規則確定的服務次序如圖b所示。
到達序號 服務優先等級 服務時長
1 7 10
2 6 12
3 4 32
4 5 24
5 6 8
圖a
到達序號 服務優先等級 服務時長 服務次序
1 7 10 1
2 6 12 2
3 4 32 5
4 5 24 4
5 6 8 3
圖b
若服務大廳提供2個服務窗口(m=2),則所有服務對象完成業務辦理需要50分鐘。具體方案可以是:0號窗口依次服務到達序號為1、5、3的對象,1號窗口依次服務到達序號為2、4的對象。請回答下列問題:
(1)若有6個服務對象的信息如圖c所示,根據上述服務規則,在提供3個服務窗口的情況下,所有服務對象完成業務辦理需要　　　　分鐘。
到達序號 服務優先等級 服務時長
1 3 2
2 5 7
3 4 13
4 1 5
5 8 12
6 4 11
圖c
(2)定義如下sort_lst(lst)函數,參數 lst是所有服務對象信息構成的列表。函數的功能是將列表lst 按照服務對象的優先等級降序排列并構成鏈表,返回排序后的鏈表及其頭指針。
def sort_lst(lst):
for i in range(len(lst)):
　　lst[i].append(-1)
head=0
for i in range(1,len(lst)):
　　p=head
　　while p!=-1:
　　　　if lst[p][1]>=lst[i][1]:
　　　　　　q=p
　　　　　　p=lst[p][3]
　　　　else:
　　　　　　break
　　if p==head:
　　　　lst[i][3]=head
　　　　head=i
　　else:
　　　　lst[q][3]=i
　　　　lst[i][3]=p
return lst,head
若lst列表依次存儲圖c所示的服務對象信息,如lst[0]為[1,3,2],各數據項依次表示服務對象的到達序號,服務優先等級及服務時長。調用sort_lst(lst)時,程序中加框處的語句“q=p”總共執行　　　　次。
(3)計算時間段內服務對象完成業務辦理所需時間的部分Python程序如下,請在劃線處填入合適的代碼。
def proc(lst,p,n,m):
s=[0]*m
for i in range(m):　　#前m個人直接開始服務,等待時間為0
　　if p==-1:
　　　　break
　　s[i]=lst[p][2]
　　　?、佟　?
ans=0
while p!=-1 :
　　k=s[0]　　#找出正在被服務的對象中最早結束的一個
　　for j in range(1,m):
　　　　if s[j]　　　　　　k=s[j]
　　ans+=k
　　for j in range(m):
　　　　s[j]-=k
　　　　if　?、凇　?
　　　　　　s[i]=lst[p][2]
　　　　　　p=lst[p][3]
k=s[0]
for i in range(m):
　　if s[i]>k:
　　　　k=s[i]
　?、邸　?
print("所有服務對象完成業務辦理需要" ,str(ans),"分鐘")
'''
讀入服務對象總數n和窗口數m
按到達序號讀入n個服務對象的信息到列表lst中,如圖c為:lst=[[1,3,2],[2,5,7],[3,4,13],[4,1,5],[5,8,12],[6,4,11]]
代碼略
'''
lst,head=sort_lst(lst)#對lst按照服務對象優先等級降序排序
proc(lst,head,n,m)
11.(2024浙江1月選考,15,9分)某項活動有n個單位(編號1到n)參加,需將員工分成若干個小組,每個小組的人數上限為m,小組編號按新建次序從1開始編號。分組時,首先按單位編號次序依次在各單位內部分組,每m人分配到一個新建小組中,不足m人的剩余員工暫不分配;然后按剩余員工人數由大到小的順序,依次為各單位剩余員工分配小組。
若某單位剩余員工人數為k,則分配方法為:在已建的小組中查找空位數(該小組還可容納的人數)大于或等于k的小組,如果找到的小組有多個,則選擇空位數最少的小組,將此k人分配到該小組中; 如果沒有找到,則新建一個小組,將此k人分配到該小組中。
設n為5,m為20,各單位員工人數及單位內部的分組過程如圖a所示,各單位剩余員工的分組過程如圖b所示。
編寫程序:給定各單位編號及員工人數,根據上述方法進行分組處理,按單位編號次序輸出各單位所分配的分組編號。請回答下列問題:
(1)由題意可知,若僅將圖a中1號單位的員工人數修改為25,然后對圖中5個單位重新分組,則1號單位所分配的分組編號為　　　　。
(2)定義如下bubble_sort(lst)函數,參數lst的每個元素由單位編號和剩余員工人數2個數據項組成。函數的功能是根據每個單位的剩余員工人數,對lst進行降序排序。
def bubble_sort(lst):
　　n=len(lst)
　　for i in range(0,n-1):
for j in range(n-1,i,-1):
　　if lst[j-1][1]　　　　tmp=lst[j]
lst[j]=lst[j-1]
lst[j-1]=tmp
if lst[i][1]==0:
　　break
　　return
調用該函數,若lst為[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],請回答①和②兩個問題。
①框中的程序段第1次執行后,關于lst中的剩余員工人數,下列說法正確的是　　　 (單選,填字母)。
A.lst[0][1]數值最小
B.lst[0][1]數值最大
C.lst[5][1]數值最小
D.lst[5][1]數值最大
②框中的程序段執行的次數為　　　　。
(3)實現分組功能的部分Python程序如下,程序中用到的列表函數與方法如圖c所示,請在程序中劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x.w.pop() 將列表w末尾元素賦值給x,并將其從w中刪除
圖c
def group(data,m):
n=len(data)
a=[]
for i in range(n+1):
a.append([])　　　#a[i]初始化為空列表,存放編號為i的單位所分配的分組編號
gnum=0
for i in range(n):　　#各單位內部分組
　　while data[i][1]>=m:
　　　　gnum+=1
k=data[i][0]
a[k].append(gnum)
　　?、佟　　?
bubble_sort(data)　　#根據每個單位的剩余員工人數,對data 進行降序排序
b=[]
for i in range(m):
b.append([])
i=0　　　#對剩余員工分組
while i　　　　?、凇　　?
while j　　j+=1
if j　　v=b[j].pop()
else:
　　gnum+=1
　　v=gnum
a[data[i][0]].append(v)
　　?、邸　　?
i+=1
#輸出各單位的分組編號,代碼略
'''
讀取小組人數上限存入m;讀取1至n號單位的數據,依次存入列表data的data[0]至data[n-1]中。
data[i]包含2個數據項,data[i][0],data[i][1]分別存放單位編號及員工人數,代碼略
'''
group(data,m)
12.(2024屆浙南名校聯盟聯考,15)某工廠將送達的各批次物品按品種打包。小李將各批次物品信息按送達時間順序合并,得到如圖a-2所示數據 data。同一個包裹只能裝入同一品種任意批次的物品,當某一個品種物品A送達使得已送達的該品種物品總質量超過m時,則將在該物品之前送達的物品按質量由大到小依次裝入包裹,其余質量不足m的品種,按各品種依次裝入包裹。編寫程序,讀取物品合并更新后的信息,按送達時間順序打包,輸出各包裹中的物品序號,運行結果如圖b所示。
序號 品種 送達時間 批次 質量(千克)
1 2 8:35 1 6
2 1 8:50 1 8
3 0 9:10 1 2
4 0 9:15 1 4
序號 品種 送達時間 批次 質量(千克)
1 0 8:30 2 3
序號 品種 送達時間 批次 質量(千克)
1 0 8:40 3 4
圖a-1
序號 品種 送達時間 批次 質量(千克)
1 0 8:30 2 3
2 2 8:35 1 6
3 0 8:40 3 4
4 1 8:50 1 8
5 0 9:10 1 2
6 0 9:15 1 4
圖a-2
m=10
data=[[1,0,'8:30',2,3],[2,2,'8:35',1,6],[3,0,'8:40',3,4],[4,1,'8:50',1,8],[5,0,'9:10',1,2],[6,0,'9:15',1,4]]
第1個包裹中品種為0,各物品的序號依次是:3,1,5,
第2個包裹中品種為0,各物品的序號依次是:6,
第3個包裹中品種為1,各物品的序號依次是:4,
第4個包裹中品種為2,各物品的序號依次是:2,
圖b
請回答下列問題:
(1)送達物品信息合并后如圖a-2所示,若包裹裝入物品質量不能超過8千克,則首先打包完成的包裹中裝入品種為0,各物品的序號依次是　　　　。
(2)定義data_sort(lst)函數。先將數據(見圖a-1)合并得到 lst列表(見圖a-2),函數data_sort(lst)的功能是對lst列表按送達時間升序排列,并對序號進行更新。
def data_sort(lst):
for i in range(n-1):#n為數據個數
　　for j in range(n-1,i,-1):
　　　　if lst[j][2]< lst[j-1][2]:
　　　　　　lst[j],lst[j-1]=lst[j-1],lst[j]
　　lst[i][0]=i+1
return lst
執行上述代碼后,　　　　(填寫:能/不能)正確得到圖a-2中的數據。
(3)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
def pack(k):　#對品種k已送達待打包的物品按質量由大到小輸出
#部分代碼略
p=b[k][1]
num+=1
print("第"+str(num)+"個包裹中品種為"+str(k)+",各物品的序號依次是: ",end=" ")
while p!=-1:
　　print(data[p][0],end=",")
　　p=x[p]
print()
#合并后排序得到n件物品的數據存儲在數組data中并輸出,包裹最大承受質量為m千克。物品品種的數量是sn,代碼略
b=[[0,-1] for i in range(sn)]
x=[-1 for i in range(n)]
num=0
for i in range(n):
k=data[i][1]
if b[k][0]+data[i][4]>m:
　　pack(k)
　　b[k]=[0,-1]
p=　?、佟　?
if p==-1:
　　b[k][1]=i
else:
　　if data[i][4]>data[p][4]:
　　　　b[k][1]=i
　　　　　?、凇　?
　　else:
　　　　q=-1
　　　　while　?、邸　?
　　　　　　q=p
　　　　　　p=x[p]
　　　　x[q]=i
　　　　x[i]=p
b[k][0]+=data[i][4]
#質量不足m的品種,按品種依次裝入包裹
for i in range(sn):
if b[i][1]!=-1:
　　pack(i)
13.(2024屆新陣地聯盟聯考,15)進入新學期第一天,班主任老師將班上N個同學(學號為1~N)排成一排,分配座位。從排隊到分配座位步驟如下:
步驟一:先將1號同學安排進隊;
步驟二:2~N號同學由老師依次指定入隊位置,如學號為i的同學由老師指定站在隊中某位同學的左側或右側;
步驟三:所有同學按照上述方法入隊完畢后,以2人一組的方式依次分配到四個組別中;
步驟四:輸出每組學生的名單。
請回答下列問題。
(1)若某班有4位同學,學號為1~4,完成步驟一后,執行步驟二的指令3次,每次指令包含兩個整數k和p(p為0或1)。若p為0,則表示插在k號同學的左側,p為1則表示插在k號同學的右側。若三條指令分別為1 0、2 1、1 0,則執行指令后隊伍從左到右學號分別為　　　　。
(2)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
#insert(k,x)函數的功能是在k號的右側插入x號同學
#L和R列表分別用于記錄每位同學的左側和右側的同學學號
def insert(k,x):
R[x]=R[k]
L[x]=k
　?、佟　?
R[k]=x
L=[0]*100;R=[0]*100;vis=[0]*100
insert(0,1)　　#0的右邊插入1號同學
#info列表存儲各學生姓名和學號,格式如[["張三",1],["李四",2]…],代碼略
n=int(input("請輸入同學人數:"))
for i in range(2,n+1):
k=int(input("請問插入在幾號同學旁邊 "))
p=int(input("請輸入該同學的左側還是右側"))
if p==0:
　　　?、凇　?
else:
　　insert(k, i)
q=[[] for i in range(4)]
i=m=0
　　③　　
while x!=0:
q[i].append(x)
m=m+1
if m%2==0:
　　　　④　　
x=R[x]
for i in range(4):
for j in q[i]:
　　print(info[j-1][0], end="　")
print()
14. (2023學軍中學月考,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)
題組二
1.(2024屆名校協作體聯考,11)定義如下函數:
def f(k):
if k<=3:
　　print(k)
　　return
for i in range(1,4):
　　f(k-i)
return
執行語句f(6),則f(3)被調用的次數為(　　)
A.1次　　　B.2次　　　C.3次　　　D.4次
2.(2024屆強基聯盟聯考,10)執行下列Python代碼,輸出結果為(　　)
def f(s):
m=len(s)
if m==1:
　　return int(s)
else:
　　return f(s[:m-1])+f(s[m-1])
print(f("101"))
A.11　　　　B.2　　　
C.5　　　　D.101
3.(2024屆百校起點調研測試,10)定義如下遞歸函數:
def f(a,n):
n=n-1
if n==0:
　　return a
else:
　　return f(a-1,n)+f(a+1,n)
print(f(5,3))
程序運行后,輸出的結果是(　　)
A.10　　　B.20　　　C.30　　　D.40
4.(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
5.(2023浙江開學考,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
6.(2023十校聯盟聯考,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
7.(2023浙南名校聯盟聯考,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
8.(2024屆天域全國名校協作體聯考,15)計算機運行多個任務(又稱進程)時,需要進行調度。有的進程需要優先響應,例如用戶的交互操作,此時就需要暫停當前運行的進程,讓CPU先執行需要優先響應的進程,這稱為搶占。操作系統需要設計調度算法,來決定CPU運行進程的順序。
優先級搶占式調度算法是一種簡單的調度算法,規則如下:
1)將進程分為m個優先級,設置m個等待隊列,分別對應每一級優先級。
2)每個進程具有三個要素:到達時間,運行所需時長,優先級數(數越大優先級越高)。
3)相同優先級的進程,按照先到先服務的原則依次執行。
4)同一時刻中,先將到達的進程都加入隊列,再按照優先級進行分配。
5)只有當k級隊列為空的時候,才會為k-1級隊列隊首的進程分配時間。
6)進程Pi運行時,如果有優先級更高的進程Pj到達,則立即發生搶占,先執行Pj,并將進程Pi未執行完的部分,重新加入Pi優先級對應的隊列末尾,等待繼續執行。
編寫程序模擬CPU分配計算資源的過程,已知按照到達時間升序排序的進程數據(包含到達時間、運行時長、優先級),計算并輸出每個進程最終處理完成的時間。(時間單位均為毫秒)
請回答下列問題:
(1)有4個進程A、B、C、D如圖所示。
進程 到達時間 運行時長 優先級
A 0 7 1
B 2 4 2
C 4 1 3
D 5 4 2
由優先級搶占式調度算法的規則可知,0毫秒時進程A到達并執行;2毫秒時進程B到達,B的優先級高于A,發生搶占,A剩余的5毫秒回到隊列1,B開始執行;4毫秒時進程C到達,C的優先級高于B,發生搶占,B剩余的2毫秒回到隊列2,C開始執行;則進程D執行完的時刻為　　　　。
(2)模擬實現優先級搶占式調度算法Python程序如下,請在劃線處填入合適的代碼。
def insert(p,remain):
data[p][2]=remain　#更新進程剩余的運行時間
lvl=data[p][3]
if queinfo[lvl][0]==-1:
　　queinfo[lvl][0]=p
if queinfo[lvl][1]!=-1:
　　data[queinfo[lvl][1]][-1]=p
data[p][-1]=-1
queinfo[lvl][1]=p
m=int(input('設置優先級的數量m:'))
#輸入列表data存儲進程,data中的節點包含信息有[名稱,到達時間,運行時長,優先級],代碼略
#進程已經按到達時間升序排序
#例如: data=[['A',0,7,1],['B',2,4,2],['C',4,1,3],['D',5,4,2]]
for i in range(len(data)):
data[i].append(-1)
queinfo=[[-1,-1] for i in range(m+1)]
insert(0,data[0][2])#將第1個進程加入隊列
time=data[0][1]
cnt=1　#所有隊列內等待的進程總數
idx=1
lvl=m
while cnt > 0:
if queinfo[lvl][0]!= -1:
　　cur=queinfo[lvl][0]
　　queinfo[lvl][0]= data[queinfo[lvl][0]][-1]
　　cnt -=1
　　　?、佟　?
　　while idx=data[idx][1]:
　　　　if lvl>=data[idx][3] or time+data[cur][2]==data[idx][1]:
　　　　　　insert(idx, data[idx][2])
　　　　　　cnt+= 1
　　　　　　idx+= 1
　　　　elif time+data[cur][2]> data[idx][1]:
　　　　　　insert(idx, data[idx][2])#搶占的進程也先入隊
　　　　　　cnt+=1
　　　　　　insert(cur,　?、凇　?
　　　　　　cnt+=1
　　　　　　time=data[idx][1]
　　　　　　lvl=data[idx][3]
　　　　　　idx+=1
　　　　　　flag=True
　　　　　　break
　　if flag==False:
　　　　time=time+data[cur][2]
　　　　print("時刻", time,":進程", data[cur][0],"完成")
　　lvl=m
　　if　　?、邸　?　#仍然有未到達的進程等待入隊
　　　　insert(idx, data[idx][2])
　　　　cnt+=1
　　　　time=data[idx][1]
　　　　idx+=1
else:
　　lvl-=1
　　if lvl==0:
　　　　lvl=m
(3)若將以上程序中insert 函數內的加框處代碼刪除,會導致某些情況下無法得到符合程序功能的結果,下列4組數據中能測試出這一問題的是　　　　(單選,填字母)。
A.m=3
data=[['A',0,1,1],['B',1,1,2],['C',3,1,3]]
B.m=3
data=[['A',0,2,2],['B',1,2,3],['C',3,1,3]]
C.m=3
data=[['A',0,2,1],['B',1,2,3],['C',2,1,2]]
D.m=3
data=[['A',0,2,2],['B',1,2,3],['C',2,1,1]]
9.(2024屆A9協作體聯考,15)張三是一名計算機專業的大學生,為了幫助同學們學習專業相關的英語詞匯,編寫了一個簡易字典程序。該程序中存放詞匯數據庫,在學習中輸入英文單詞,可以獲得中文翻譯結果。程序中的詞匯數據庫采用鏈表方式存儲,首字母相同時按升序排序。查找單詞時,首先根據首字母找到同首字母最小單詞所在鏈表,再按照鏈表順序查找該單詞。
(1)根據題意,部分的單詞庫數據邏輯結構如圖所示,查找單詞"byte"的過程是"binary"→"bit"→"byte",補充圖中空白單元格的值為　　　　。
列表索引 數據區域 指針區域
0 audio 音頻 -1
1 binary 二進制數 6
2 byte 字節 -1
3 cursor 光標 -1
4 access 存取 1
5 cache 高速緩存 3
6 bit 比特 　　　
(2)wordlist(data,info)函數實現將詞匯數據庫data以鏈表的方式按字母序升序排列。info表示詞匯數據庫中各字母開頭的最小單詞位置,如info[0]表示字母a開頭的最小單詞在詞匯數據庫data中的位置。實現該功能的程序如下,請在劃線處填入合適的代碼。
def wordlist(data,info):
n=len(data)
for i in range(n):
　　data[i].append(-1)　#data[i]追加一個元素-1
for i in range(n):
　　d=data[i][0]
　　　?、佟　?
　　if info[k]==-1:
　　　　info[k]=i
　　else:
　　　　head=info[k]
　　　　q=head
　　　　while　?、凇　?
　　　　　　p=q
　　　　　　q=data[q][2]
　　　　if q !=head:
　　　　　　data[p][2]=i
　　　　　　data[i][2]=q
　　　　else:
　　　　　　data[i][2]=head
　　　　　　　?、邸　?
return data,info
(3)searchword(data,info,key)函數實現單詞的查找。程序如下,請在劃線處填入合適的代碼。
def searchword(data,info,key):
k=ord(key[0])-ord("a")
head=info[k]
p=head
while p != -1:
　　if data[p][0]==key:
　　　　return 　　　
　　p=data[p][2]
return "沒有找到該單詞"
#讀取詞匯數據庫,存入列表data中,列表的每個元素包含2個數據項,分別為英文單詞和中文翻譯,如data = [['audio','音頻'],['binary','二進制數']…],數據讀取存入的代碼略
info=[-1]* 26
data,info=wordlist(data,info)
key=input("請輸入查找單詞:").lower()　#轉化為小寫字母
res=searchword(data,info,key)
print(key,"查找結果是:",res)
10.(2024屆強基聯盟聯考,15)某校針對高三高考成績進行分析時,其中有兩個主要指標:班級各科平均成績和班級總分平均成績。高考成績保存在“kscj.csv”文件中,格式如圖a所示,每行有四個項目,分別是“學號”“姓名”“學科”和“得分”,其中“學號”的前兩位表示班級編號,后兩位表示該學生班內編號,兩種編號均從“01”遞增編排。
設計如下Python程序,執行后輸出上述兩個主要指標,如圖b所示。請回答下列問題。
(1)通讀下列程序代碼后,可知程序中各班級隊列采用的數據結構為　　　　(選填,數組/鏈表)。
(2)函數dataToClassQue功能:根據班級編號,將數據分配到各個班級隊列。請在劃線處填入合適的代碼。
def dataToClassQue(data):
num=len(data)
for i in range(num):
　　classId=data[i][0]
　　if queInfo[classId-1][0]==-1:
　　　　queInfo[classId-1][0]=i
　　else:
　　　　　　　
　　queInfo[classId-1][1]=i
return
(3)函數dataProcessing 功能:統計各班各科平均分和班總分平均分。請在劃線處填入合適的代碼。
def dataProcessing(data):
for classId in range(1,classNumber+1):
　　　?、佟　?
　　score=[[0,0] for i in range(10)]#班級各科平均分和人數初始化
　　p=queInfo[classId-1][0]
　　while p !=-1:
　　　　subjectId=data[p][3]
　　　　total+=data[p][4]
　　　　　　②　　
　　　　score[subjectId][1]+=1
　　　　p=data[p][-1]
　　for subjectId in range(10):
　　　　if score[subjectId][1]!=0:
　　　　　　t=　?、邸　?
　　　　　　averageScore[classId-1][subjectId]=round(t,1)
　　averageScore[classId-1][10]=round(total/score[0][1],1)
return
def readFile(data):
#讀入原始學生數據,預處理后,存儲到data中,代碼略
#data數據格式:[[6,10,'白凱修',0,117,-1],[6,10,'白凱修',1,109,-1],……]
#每條記錄包括班級編號,班內編號,姓名,學科編號,得分和預留值-1
return maxClassId#返回最大班級編號
def fmtPrint():
#格式化輸出,如圖b所示,代碼略
return
#主程序
course={'語文':0,'數學':1,'英語':2,'物理':3,'化學':4,'生物':5,'政治':6,'歷史':7,'地理':8,'技術':9}
data=[]　#存儲讀入的數據
classNumber=readFile(data)
queInfo=[[-1,-1] for i in range(classNumber)]　#初始化隊列,用于存儲各班級信息
averageScore=[[0 for k in range(11)] for i in range(classNumber)]
dataToClassQue(data)
dataProcessing(data)
fmtPrint()
11.(2024屆百校起點調研測試,15)某醫院的團體體檢流程如下:
編號登記:為n位體檢者設置體檢編號1~n。
體檢呼叫:體檢項目處空閑時呼叫下一個體檢者(編號小的優先),若多個項目同時呼叫,體檢者到優先級小的項目處體檢。僅考慮常規體檢項目,各個項目的優先級及體檢時間如圖所示。
項目 名稱 B 超 心 電 圖 抽 血 尿 常 規 C14 檢測 胸 透 一般 常規
優先級 0 1 2 3 4 5 6
時間 (min) 12 5 2 2 2 2 1
前去體檢:各個體檢項目之間相互獨立,互不影響;病人排隊體檢和體檢完畢到下一科室之間沒有時間延遲。
(1)某個團隊4人(分別用編號1,2,3,4表示)參加體檢,開始體檢后第5分鐘,4號在檢查　　　　(填寫項目名稱)項目。
(2)定義如下lst(n)函數,生成n人體檢隊列。若體檢人數為4,則que生成結果如圖所示。
隊列索引號 體檢編號 已檢測項目
0 1 []
1 2 []
2 3 []
3 4 []
def lst(n):
que=[]
for i in range(n):
temp=[i+1,[]]
　　que.append(temp)
return que
若加框處語句改為:for i in range(1,n+1):
temp=[i,[]]
則執行語句lst(4),que的生成結果　　　(選填:相同/不同)。
(3)用Python程序模擬一個10人團隊參加體檢的流程。程序運行后,體檢完成順序如圖所示。
體檢完成順序:
編號2:心電圖→一般常規→抽血→尿常規→C14檢測→胸透→B超
編號1:B超→抽血→尿常規→C14檢測→胸透→一般常規→心電圖
編號5:C14檢測→胸透→一般常規→抽血→尿常規→B超→心電圖
編號3:抽血→尿常規→C14檢測→胸透→一般常規→心電圖→B超
編號4:尿常規→C14檢測→胸透→一般常規→抽血→心電圖→B超
編號6:胸透→一般常規→抽血→尿常規→C14檢測→心電圖→B超
編號7:一般常規→抽血→尿常規→C14檢測→胸透→心電圖→B超
編號8:一般常規→心電圖→C14檢測→胸透→抽血→尿常規→B超
編號9:一般常規→胸透→抽血→尿常規→C14檢測→心電圖→B超
編號10:一般常規→尿常規→C14檢測→胸透→抽血→心電圖→B超
Python部分程序如下,請在劃線處填入合適的代碼。
n=10
head=0
que=lst(n)
tail=10
dis=[['B超',12],['心電圖',5],['抽血',2],['尿常規',2],['C14檢測',2],['胸透',2],['一般常規',1]]
t=[-1]*7#t記錄各個項目當前體檢的開始時間
f=[-1]* 7#f記錄各個項目當前體檢人員編號
def jh(num):
global tail #global能夠實現在自定義函數中改變公共變量tail
p=head
while p　　if que[p][0]not in f and num not in que[p][1]:#p體檢者等待中且未體檢num項目
　　　　que[p][1].append(num)
　　　　　?、佟　?
　　　　t[num]=time
　　　　if len(que[p][1])==7:
　　　　　　temp=que[p]
　　　　　　for i in range(p,tail-1):
　　　　　　　　que[i]=que[i+1]
　　　　　　que[tail-1]=temp
　　　　　　tail-=1
　　　　break
　　p=p+1
time=0
while tail!=head:
i=0
while i<7:
　　if t[i]==-1:
　　　　jh(i)
　　elif　?、凇　?
　　　　t[i]=-1
　　　　f[i]=-1
　　　　i-=1
　　i+=1
time+=1
print('體檢完成順序:')
for i in range(　?、邸　?:　#按體檢完成順序輸出體檢者及其體檢項目順序
item=que[i][1]
s=' '
for j in item:
　　s+=dis[j][0]+'→'
print('編號%d: %s'%(que[i][0],s[:-1]))
12.(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)
13.(2023強基聯盟統測,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.(2024屆發展共同體聯考,12)以下兩個程序段的功能相同,實現的功能是:刪除列表a(元素個數為n)中的重復元素(只保留一個),并將剩下的元素降序輸出。
#程序段① #對列表a進行降序排序,代碼略 i=1 while i#程序段② max_num=max(a)#求出列表a中的最大值max_num b=[0]*(max_num+1) for i in range(0,n): 　 b[a[i]]+=1 for i in range(max_num,0,-1): 　 if b[i]>0: 　　　print(i,end=" ")
關于上述兩個程序段及功能的描述,正確的是(　　)
A.同樣的數據規模,兩個程序段的時間效率一樣
B.程序段①加框處語句是否執行不受列表a原數據的影響
C.程序段②加框處語句修改為“for i in range(1,max_num+1)”,輸出結果不變
D.在實現該功能的過程中,程序段②比程序段①需要更多的存儲空間
答案　D　
2.常見算法時間復雜度函數的增長率如圖所示。
則當問題規模n=100時,下列時間復雜度中效率最高的是(　　)
A.O(nlog2n)　　　　B.O(log2n)
C.O(n)　　　　D.O(n3)
答案　B　
3.有如下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　
4.有以下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.(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　
2.(2023浙江6月選考,10,2分)定義如下函數:
def f(a,s):
　　if a>=s:
　　　　return a
　　else:
　　　　return f(a+1,s-a)
執行語句k=f(6,21)后,k的值為(　　)
A.6　　　B.7　　　C.8　　　D.9
答案　C　
3.(2024屆發展共同體聯考,10)定義如下函數:
def f(x,y):
　　if x<=2 or y>20:
　　　　return x+y
　　return f(x-1,y+1)
執行語句k=f(5,1)后,k的值為(　　)
A.6　　　B.7　　　C.8　　　D.9
答案　A　
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　
考點三　數據排序
1.(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　
2.(2024屆名校協作體聯考,10)有如下Python程序:
a=[12,45,45,63,0,0,63]
cnt=0
for i in range(1,len(a)):
　　j=i-1
　　t=a[i]
　　while j>=0 and t>a[j]:
　　　　 a[j+1]=a[j]
　　　　 j=j-1
　　　　 cnt=cnt+1
　　a[j+1]=t
print(cnt)
運行該程序后,輸出的結果是(　　)
A.8　　　B.10　　　C.11　　　D.13
答案　B　
3.(2024屆浙南名校聯考,12)有如下Python程序段:
from random import randint
x=randint(2,4)*2
a=[9,2,5,1,3,4,8,7]
n=len(a)
for i in range(0,n-1):
　　k=i
　　for j in range(i+1,x):
　　　 　if a[k]>a[j]:
　　　　　　k=j
　　if i!=k:
　　　 　a[k],a[i]=a[i],a[k]
print(a)
執行后,輸出結果不可能是(　　)
A. [1,2,3,4,5,7,8,9]
B. [1,2,3,4,5,9,8,7]
C. [1,2,5,9,3,4,8,7]
D. [1,2,3,4,5,9,7,8]
答案　D　
4.(2024屆天域全國名校協作體聯考,11)列表s存有4個整數,有如下Python程序段:
n=len(s)
f=[1]*n
for i in range(n-1):
　 　for j in range(i+1,n):
if s[j]>=s[i]:
　　f[j]+=1
else:
　　f[i]+=1
print(f)
該程序段實現的功能是標記列表中每個數值的名次值,名次排序的規則是(　　)
A.數值越大名次值越大,同數值先出現的名次值小
B.數值越大名次值越大,同數值先出現的名次值大
C.數值越大名次值越小,同數值先出現的名次值小
D.數值越大名次值越小,同數值先出現的名次值大
答案　A　
5.(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　
6.(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　
考點四　數據查找
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諸暨期末,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　
6.(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("共有"　?、邸　? "位同學大于等于該成績。")
答案?、賏[j]>a[j+1]?、趉ey專題綜合練
題組一
1.(2024屆A9協作體返?？?11)有如下Python程序段:
import random
a=[1,3,4,6,6,6,9,9,11,12]
key=random.randint(2,5)*2
i,j=0,9
while i<=j:
m=(i+j)//2
if key　　j=m-1
else:
　　i=m+1
print(j)
執行該程序段后,輸出的結果不可能是(　　)
A.2　　　B.3　　　C.5　　　D.7
答案　B　
2.(2024屆Z20聯盟聯考,10)有如下Python函數:
def trans(num,n):
s="0123456789ABCDEF"
if num　　return s[num]
else:
　　return trans(num//n,n)+s[num%n]
執行語句a=trans(394,16)后,a的值為(　　)
A.19A　　　B.1810　　　C.180　　　D.18A
答案　D　
3.(2024屆七彩聯盟聯考,10)有如下程序段:
def cal(n):
if n<=1:
　　return 1
if n % 2==0:
　　return 2*cal(n-1)
return 1+cal(n-1)
執行語句k=cal(5),則k的值為(　　)
A.6　　　B.7　　　C.10　　　D.11
答案　B　
4.(2024屆強基聯盟統測,10)有如下程序段:
def fun(k):
if k==1:
　　return "1"
elif k%2==0:
　　return fun(k-1)+str(k%2)
else:
　　return str(k%2)+fun(k-1)
執行語句s=fun(5),則s 的值為(　　)
A."00111"　　　　B."11010"
C."11100"　　　　 D."10110"
答案　C　
5.(2024屆新陣地聯盟聯考,10)有如下Python程序:
import random
def func(n):
if n==1:
　　return 1
elif n==2:
　　return 2
elif n%2==1:
　　return 2*func(n-2)+func(n-1)
else:
　　return func(n-2)+2*func(n-1)
p=random.randint(3,6)
print(func(p))
執行程序后,輸出結果不可能為(　　)
A.4　　　B. 10　　　C. 12　　　D. 18
答案　C　
6.(2024屆天域全國名校協作體聯考,10)某遞歸函數如下所示:
def hs(m):
if m<=1:
　　f=1
else:
　　f=hs(m-1)+hs(m-2)
return f
ans=0
for i in range(5):
if hs(i)%2==1:
　　ans+=1
print(ans)
程序運行后,輸出的結果是(　　)
A.2　　　B.3　　　C.4　　　D.5
答案　C　
7.(2023十校聯盟聯考,12)某二分查找算法的Python程序段如下:
import random
key=random.randint(0,4)*2+5
n=10;ans=0
a=[4,5,5,8,9,11,11,13,15,17]
i=0;j=n-1
while i<=j:
m=(i+j)//2
if a[m]<=key:
i=m+1
else:
j=m-1
ans+=a[m]
print(ans)
執行該程序段后,ans的值不可能是(　　)
A.19　　　B.27　　　C.37　　　D.44
答案　A　
8.(2024屆七彩聯盟聯考,15)某工廠每天會收到多個訂單,有n臺機器對零件進行加工。為減少機器的損耗,需要在滿足所有訂單加工的情況下(訂單即到即加工),機器開啟數量盡量少。若開啟n臺機器不能滿足訂單即到即加工,則計算所有訂單最少的平均等待時間。若給定某天內所有的訂單信息,請計算需要開啟的機器數量以及訂單平均等待時間,代碼運行效果圖如圖所示(注意:若上一個訂單結束時間為9:00,下一個訂單開啟時間最早為9:00)。
訂單信息如下:(批次,到達時間,加工時間min)
(A1,9:00,30)(A2,11:30,50) (A3,10:40,50)(A4,10:00,60)(A5,9:20,40)(A6,11:00,20)(A7,10:20,40)(A8,9:30,20)
機器數量:2
2臺機器全部開啟,訂單平均等待2.5min
第1臺機器:
A1:09:00~09:30,A8:09:30~09:50,A4:10:00~11:00,A3:11:00~11:50
第2臺機器:
A5:09:20~10:00,A7:10:20~11:00,A6:11:00~11:20,A2:11:30~12:20
請回答下列問題:
(1)上圖所示的例子中,若機器有10臺,則只需要開啟　　　　臺機器。
(2)定義如下data_sort(a)函數,參數a為列表,列表中每個元素包含三個數據項,依次分別對應訂單批次、到達時間、加工時間(時間均轉為分鐘)。該函數實現將列表a按照訂單到達時間升序排序。
def data_sort(a):
for i in range(len(a)):
　　for j in range(len(a)-i-1):
　　　　if　　　　:
　　　　　a[j],a[j+1]=a[j+1], a[j]
①劃線處填入的語句為　　　　　　　,可實現上述功能。
②若將加框處語句寫錯為range(i,len(a)-1),則下列4組數據中,列表a的值為　　　(單選,填字母)時不能測試出問題。
A.[['A1',100,30],['A2',120,30],['A3',110,30],['A4',140,30],['A5',130,30]]
B.[['A1',120,30],['A2',110,30],['A3',100,30],['A4',130,30],['A5',140,30]]
C. [['A1',110,30],['A2' ,140,30],['A3',130,30],['A4',100,30],['A5',120,30]]
D.[['A1',110,30],['A2',120,30],['A3',130,30],['A4',140,30],['A5',100,30]]
(3)實現計算開啟機器數量的部分Python程序如下,請在劃線處填入合適的代碼。
def huan(n):
#將分鐘轉換為時間AA:BB格式,返回值為字符串,代碼略
#讀取文件中的信息,并存儲在列表order中,代碼略
data_sort(order)
n=int(input("機器數量:"))
for i in range(len(order)):
order[i].append(-1)
#order[i]追加一個元素-1
mach=[-1]* n
num, wait=0,0
for i in range(len(order)):
k=-1
time=-1
for j in 　?、佟　?
　　t1=mach[j]
　　if k==-1:
　　　　k=j
　　　　time=order[t1][1]+order
[t1][2]
　　else:
　　　　t2=mach[k]
　　　　if order[t1][1]+order[t1][2]　　　　　　k=j
　　　　　　time=order[t1][1]+order
[t1][2]
if k==-1 or num　 mach[num]=i
　 num+=1
　　else:
　 order[i][3]=mach[k]
　 mach[k]=i
　 if time>order[i][1]:
　　　　wait +=time-order[i][1]
　　　　order[i][1]=time
if numprint("只需開啟"+str(num)+"臺機器")
else:
print(str(n)+"臺機器全部開啟,訂單平均等待"+str(round(wait/len(order),2))+"min")
for i in range(num):
print('第'+str(i+1)+'臺機器: ')
p=mach[i]
ans=' '
while p!=-1:
　　ans=order[p][0]+':'+huan(order[p][1])+'~'+huan(order[p][1]+order[p][2])+','+ ans
　　p=　?、邸　?
　　print(ans[:-1])
答案　　(1)3 　(2)①a[j][1]> a[j+1][1]
②A　(3)①range(num)?、趖ime>order[i][1]?、踥rder[p][3]
9.(2024屆名校協作體聯考,15)有一款益智游戲,規則如下:軌道上有不同顏色的珠子連成珠串,玩家可以通過炮臺發射若干珠子,每次發射一顆珠子到珠串中的某位置,形成新的珠串。當新珠串中出現3顆及以上顏色相同的連續珠子時,這些連續的同色珠子會被消除,并獲得相應積分,若消除后仍有符合條件的同色珠子,會繼續被消除。記分規則為:在被消除的連續珠子中,前面3顆直接記3分,其余的珠子每顆記2分,例如有5顆相同顏色的連續珠子被消除,可獲得7分。程序運行過程如圖所示。
現軌道的珠串為:
-1->3->1->5->4->2->2->1->2->2
當前珠子的顏色為:1
請輸入當前發射位置:7
當前珠子的顏色為:1
請輸入當前發射位置:7
當前珠子的顏色為:4
請輸入當前發射位置:5
當前珠子的顏色為:4
請輸入當前發射位置:5
最終得分為11
軌道中剩余的珠串為:
-1->3->1->5
編寫程序模擬游戲的實現過程,珠子的顏色用數字表示,為方便處理,在珠串最前面加入一顆不可消除的珠子,顏色值為-1。請回答下列問題:
(1)若珠串為-1,2,2,3,3,2,2,將顏色為3的珠子發射到顏色為2和3的珠子之間,可獲得積分為　　　　。
(2)定義如下insert(t,pos)函數,函數功能是將顏色為t的珠子,插入到當前珠串中的第pos顆珠子后面(列表link存儲珠串的相關數據,例如link中某元素的值為[3,2],3表示某顆珠子的顏色,2表示與該珠子相鄰的下一顆珠子的存儲地址,變量 head保存珠串第一個珠子的存儲地址),請在劃線處填入合適的代碼。
def insert(t,pos): #將顏色為t的珠子,插入到當前珠串第pos顆珠子的后面
p=head
while pos>1:
　　pos-=1
　　p=link[p][1]
link.append(　　　　)
link[p][1]=len(link)-1
(3)定義如下fun()函數,函數功能是:查找珠串里最早出現的可消除珠串,函數返回ret,ret由該珠串起始珠子的前一顆珠子位置和該珠串的連續長度組成。
def fun():
p=head;st=head
pre=p
num=0
lastcolor=-1
ret=[-1,0]
while p!=-1:
　　t=link[p][0]
　　if t!=lastcolor:
　　　　if num>=3:
　　　　　　ret=[st,num]
　　　　　　break
　　　　lastcolor=t
　　　　st=pre
　　　　num=1
　　else:
　　　　num+=1
　　pre=p
　　p=link[p][1]
if num>=3:
ret=[st,num]
return ret
若將函數中加框處代碼刪除,會導致某些情況下無法得到符合函數功能的結果。調用fun()函數,下列4組數據中能測試出這一問題的是　　　　(單選,填字母)。
A.head=4
link=[[2,3],[1,0],[1,1],[2,-1],[-1,2]]
B.head=0
link=[[-1,1],[2,3],[2,4],[2,2],[1,-1]]
C. head=1
link=[[2,-1],[-1,3],[2,0],[1,4],[2,2]]
D.head=4
link=[[2,-1],[1,0],[1,1],[1,2],[-1,3]]
(4)實現模擬游戲過程的部分Python程序如下,請在劃線處填入合適的代碼。
def clear(g):#根據fun函數的返回值對珠串進行消除,并統計獲得本次消除的積分
p=g[0]
q=p
length=g[1]
ret=　　①　　
while length>=0:
　　q=link[q][1]
　　length-=1
link[p][1]=q
return ret
def traverl():
　　#將軌道中珠串按序輸出,代碼略
head=7
link=[[1,3],[1,8],[2,1],[5,5],[2,2],[4,4],[3,0],[-1,6],[2,9],[2,-1]]
print("現軌道的珠串為: ")
traverl()
points=0
que=[1,1,4,4]#保存炮臺中待發射珠子的顏色
qhead=0
qtail=4
while qhead!=qtail:
　　print("當前珠子的顏色為: ",que[ghead])
　　s=int(input("請輸入當前發射位置:"))
　　insert(que[qhead],s)
　　qhead+=1
　　g=fun()
　　while g!=[-1,0]:
　　　　points+=clear(g)
　　　　　?、凇　?
print("最終得分為",points)
print("軌道中剩余的珠串為: ")
traverl()
答案　(1)8　(2)[t ,link[p][1]]　(3)C　(4)①3+(length -3)*2?、趃=fun()
10.(2024屆發展共同體聯考,15)某業務服務大廳共有m個服務窗口(編號為0~m-1),服務大廳根據服務對象的優先等級(等級分為1~10,數字越大優先級越高)從高到低依次分配窗口并提供服務。某個時間段內(該時間段起始時刻各窗口都空閑著),服務對象按服務優先等級從高到低排隊后依次到空閑的窗口享受服務,服務優先等級相同時,先到達的先享受服務。由于辦理的業務不同,每個服務對象的服務時長(單位:分鐘)可能是不相同的。按照上述服務規則,問所有服務對象完成業務辦理需要多少時間。一個服務對象業務辦理結束,另一個服務對象馬上到該窗口接受服務,中間浪費的時間忽略不計。
圖a描述了5個服務對象的信息,按照服務規則確定的服務次序如圖b所示。
到達序號 服務優先等級 服務時長
1 7 10
2 6 12
3 4 32
4 5 24
5 6 8
圖a
到達序號 服務優先等級 服務時長 服務次序
1 7 10 1
2 6 12 2
3 4 32 5
4 5 24 4
5 6 8 3
圖b
若服務大廳提供2個服務窗口(m=2),則所有服務對象完成業務辦理需要50分鐘。具體方案可以是:0號窗口依次服務到達序號為1、5、3的對象,1號窗口依次服務到達序號為2、4的對象。請回答下列問題:
(1)若有6個服務對象的信息如圖c所示,根據上述服務規則,在提供3個服務窗口的情況下,所有服務對象完成業務辦理需要　　　　分鐘。
到達序號 服務優先等級 服務時長
1 3 2
2 5 7
3 4 13
4 1 5
5 8 12
6 4 11
圖c
(2)定義如下sort_lst(lst)函數,參數 lst是所有服務對象信息構成的列表。函數的功能是將列表lst 按照服務對象的優先等級降序排列并構成鏈表,返回排序后的鏈表及其頭指針。
def sort_lst(lst):
for i in range(len(lst)):
　　lst[i].append(-1)
head=0
for i in range(1,len(lst)):
　　p=head
　　while p!=-1:
　　　　if lst[p][1]>=lst[i][1]:
　　　　　　q=p
　　　　　　p=lst[p][3]
　　　　else:
　　　　　　break
　　if p==head:
　　　　lst[i][3]=head
　　　　head=i
　　else:
　　　　lst[q][3]=i
　　　　lst[i][3]=p
return lst,head
若lst列表依次存儲圖c所示的服務對象信息,如lst[0]為[1,3,2],各數據項依次表示服務對象的到達序號,服務優先等級及服務時長。調用sort_lst(lst)時,程序中加框處的語句“q=p”總共執行　　　　次。
(3)計算時間段內服務對象完成業務辦理所需時間的部分Python程序如下,請在劃線處填入合適的代碼。
def proc(lst,p,n,m):
s=[0]*m
for i in range(m):　　#前m個人直接開始服務,等待時間為0
　　if p==-1:
　　　　break
　　s[i]=lst[p][2]
　　　　①　　
ans=0
while p!=-1 :
　　k=s[0]　　#找出正在被服務的對象中最早結束的一個
　　for j in range(1,m):
　　　　if s[j]　　　　　　k=s[j]
　　ans+=k
　　for j in range(m):
　　　　s[j]-=k
　　　　if　?、凇　?
　　　　　　s[i]=lst[p][2]
　　　　　　p=lst[p][3]
k=s[0]
for i in range(m):
　　if s[i]>k:
　　　　k=s[i]
　?、邸　?
print("所有服務對象完成業務辦理需要" ,str(ans),"分鐘")
'''
讀入服務對象總數n和窗口數m
按到達序號讀入n個服務對象的信息到列表lst中,如圖c為:lst=[[1,3,2],[2,5,7],[3,4,13],[4,1,5],[5,8,12],[6,4,11]]
代碼略
'''
lst,head=sort_lst(lst)#對lst按照服務對象優先等級降序排序
proc(lst,head,n,m)
答案　(1)18　(2)7　(3)①p=lst [p][3]或其他等價答案?、趕[j]==0 and p !=-1或其他等價答案　③ans=ans+k 或其他等價答案
11.(2024浙江1月選考,15,9分)某項活動有n個單位(編號1到n)參加,需將員工分成若干個小組,每個小組的人數上限為m,小組編號按新建次序從1開始編號。分組時,首先按單位編號次序依次在各單位內部分組,每m人分配到一個新建小組中,不足m人的剩余員工暫不分配;然后按剩余員工人數由大到小的順序,依次為各單位剩余員工分配小組。
若某單位剩余員工人數為k,則分配方法為:在已建的小組中查找空位數(該小組還可容納的人數)大于或等于k的小組,如果找到的小組有多個,則選擇空位數最少的小組,將此k人分配到該小組中; 如果沒有找到,則新建一個小組,將此k人分配到該小組中。
設n為5,m為20,各單位員工人數及單位內部的分組過程如圖a所示,各單位剩余員工的分組過程如圖b所示。
編寫程序:給定各單位編號及員工人數,根據上述方法進行分組處理,按單位編號次序輸出各單位所分配的分組編號。請回答下列問題:
(1)由題意可知,若僅將圖a中1號單位的員工人數修改為25,然后對圖中5個單位重新分組,則1號單位所分配的分組編號為　　　　。
(2)定義如下bubble_sort(lst)函數,參數lst的每個元素由單位編號和剩余員工人數2個數據項組成。函數的功能是根據每個單位的剩余員工人數,對lst進行降序排序。
def bubble_sort(lst):
　　n=len(lst)
　　for i in range(0,n-1):
for j in range(n-1,i,-1):
　　if lst[j-1][1]　　　　tmp=lst[j]
lst[j]=lst[j-1]
lst[j-1]=tmp
if lst[i][1]==0:
　　break
　　return
調用該函數,若lst為[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],請回答①和②兩個問題。
①框中的程序段第1次執行后,關于lst中的剩余員工人數,下列說法正確的是　　　 (單選,填字母)。
A.lst[0][1]數值最小
B.lst[0][1]數值最大
C.lst[5][1]數值最小
D.lst[5][1]數值最大
②框中的程序段執行的次數為　　　　。
(3)實現分組功能的部分Python程序如下,程序中用到的列表函數與方法如圖c所示,請在程序中劃線處填入合適的代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x.w.pop() 將列表w末尾元素賦值給x,并將其從w中刪除
圖c
def group(data,m):
n=len(data)
a=[]
for i in range(n+1):
a.append([])　　　#a[i]初始化為空列表,存放編號為i的單位所分配的分組編號
gnum=0
for i in range(n):　　#各單位內部分組
　　while data[i][1]>=m:
　　　　gnum+=1
k=data[i][0]
a[k].append(gnum)
　　?、佟　　?
bubble_sort(data)　　#根據每個單位的剩余員工人數,對data 進行降序排序
b=[]
for i in range(m):
b.append([])
i=0　　　#對剩余員工分組
while i　　　　?、凇　　?
while j　　j+=1
if j　　v=b[j].pop()
else:
　　gnum+=1
　　v=gnum
a[data[i][0]].append(v)
　　?、邸　　?
i+=1
#輸出各單位的分組編號,代碼略
'''
讀取小組人數上限存入m;讀取1至n號單位的數據,依次存入列表data的data[0]至data[n-1]中。
data[i]包含2個數據項,data[i][0],data[i][1]分別存放單位編號及員工人數,代碼略
'''
group(data,m)
答案　(1)1,8　(2)①B?、?　(3)①data[i][1]-=m?、趈=data[i][1]?、踒[j-data[i][1]].append(v)
12.(2024屆浙南名校聯盟聯考,15)某工廠將送達的各批次物品按品種打包。小李將各批次物品信息按送達時間順序合并,得到如圖a-2所示數據 data。同一個包裹只能裝入同一品種任意批次的物品,當某一個品種物品A送達使得已送達的該品種物品總質量超過m時,則將在該物品之前送達的物品按質量由大到小依次裝入包裹,其余質量不足m的品種,按各品種依次裝入包裹。編寫程序,讀取物品合并更新后的信息,按送達時間順序打包,輸出各包裹中的物品序號,運行結果如圖b所示。
序號 品種 送達時間 批次 質量(千克)
1 2 8:35 1 6
2 1 8:50 1 8
3 0 9:10 1 2
4 0 9:15 1 4
序號 品種 送達時間 批次 質量(千克)
1 0 8:30 2 3
序號 品種 送達時間 批次 質量(千克)
1 0 8:40 3 4
圖a-1
序號 品種 送達時間 批次 質量(千克)
1 0 8:30 2 3
2 2 8:35 1 6
3 0 8:40 3 4
4 1 8:50 1 8
5 0 9:10 1 2
6 0 9:15 1 4
圖a-2
m=10
data=[[1,0,'8:30',2,3],[2,2,'8:35',1,6],[3,0,'8:40',3,4],[4,1,'8:50',1,8],[5,0,'9:10',1,2],[6,0,'9:15',1,4]]
第1個包裹中品種為0,各物品的序號依次是:3,1,5,
第2個包裹中品種為0,各物品的序號依次是:6,
第3個包裹中品種為1,各物品的序號依次是:4,
第4個包裹中品種為2,各物品的序號依次是:2,
圖b
請回答下列問題:
(1)送達物品信息合并后如圖a-2所示,若包裹裝入物品質量不能超過8千克,則首先打包完成的包裹中裝入品種為0,各物品的序號依次是　　　　。
(2)定義data_sort(lst)函數。先將數據(見圖a-1)合并得到 lst列表(見圖a-2),函數data_sort(lst)的功能是對lst列表按送達時間升序排列,并對序號進行更新。
def data_sort(lst):
for i in range(n-1):#n為數據個數
　　for j in range(n-1,i,-1):
　　　　if lst[j][2]< lst[j-1][2]:
　　　　　　lst[j],lst[j-1]=lst[j-1],lst[j]
　　lst[i][0]=i+1
return lst
執行上述代碼后,　　　　(填寫:能/不能)正確得到圖a-2中的數據。
(3)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
def pack(k):　#對品種k已送達待打包的物品按質量由大到小輸出
#部分代碼略
p=b[k][1]
num+=1
print("第"+str(num)+"個包裹中品種為"+str(k)+",各物品的序號依次是: ",end=" ")
while p!=-1:
　　print(data[p][0],end=",")
　　p=x[p]
print()
#合并后排序得到n件物品的數據存儲在數組data中并輸出,包裹最大承受質量為m千克。物品品種的數量是sn,代碼略
b=[[0,-1] for i in range(sn)]
x=[-1 for i in range(n)]
num=0
for i in range(n):
k=data[i][1]
if b[k][0]+data[i][4]>m:
　　pack(k)
　　b[k]=[0,-1]
p=　　①　　
if p==-1:
　　b[k][1]=i
else:
　　if data[i][4]>data[p][4]:
　　　　b[k][1]=i
　　　　　?、凇　?
　　else:
　　　　q=-1
　　　　while　?、邸　?
　　　　　　q=p
　　　　　　p=x[p]
　　　　x[q]=i
　　　　x[i]=p
b[k][0]+=data[i][4]
#質量不足m的品種,按品種依次裝入包裹
for i in range(sn):
if b[i][1]!=-1:
　　pack(i)
答案　(1)3,1　(2)不能　 (3)①b [k][1]?、趚 [i]=p
③p !=-1 and data [i][4]<=data[p][4]或 p >- 1 and data [i][4]<=data [p][4]或 p >=0 and data [i][4]<=data [p][4]
13.(2024屆新陣地聯盟聯考,15)進入新學期第一天,班主任老師將班上N個同學(學號為1~N)排成一排,分配座位。從排隊到分配座位步驟如下:
步驟一:先將1號同學安排進隊;
步驟二:2~N號同學由老師依次指定入隊位置,如學號為i的同學由老師指定站在隊中某位同學的左側或右側;
步驟三:所有同學按照上述方法入隊完畢后,以2人一組的方式依次分配到四個組別中;
步驟四:輸出每組學生的名單。
請回答下列問題。
(1)若某班有4位同學,學號為1~4,完成步驟一后,執行步驟二的指令3次,每次指令包含兩個整數k和p(p為0或1)。若p為0,則表示插在k號同學的左側,p為1則表示插在k號同學的右側。若三條指令分別為1 0、2 1、1 0,則執行指令后隊伍從左到右學號分別為　　　　。
(2)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
#insert(k,x)函數的功能是在k號的右側插入x號同學
#L和R列表分別用于記錄每位同學的左側和右側的同學學號
def insert(k,x):
R[x]=R[k]
L[x]=k
　?、佟　?
R[k]=x
L=[0]*100;R=[0]*100;vis=[0]*100
insert(0,1)　　#0的右邊插入1號同學
#info列表存儲各學生姓名和學號,格式如[["張三",1],["李四",2]…],代碼略
n=int(input("請輸入同學人數:"))
for i in range(2,n+1):
k=int(input("請問插入在幾號同學旁邊 "))
p=int(input("請輸入該同學的左側還是右側"))
if p==0:
　　　?、凇　?
else:
　　insert(k, i)
q=[[] for i in range(4)]
i=m=0
　?、邸　?
while x!=0:
q[i].append(x)
m=m+1
if m%2==0:
　　　　④　　
x=R[x]
for i in range(4):
for j in q[i]:
　　print(info[j-1][0], end="　")
print()
答案　(1)2341　(2)①L[R[k]]=x?、趇nsert(L[k], i)
③x=R[0]?、躨=(i+1)%4
14. (2023學軍中學月考,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)
答案?、賗+1,len(lst)?、趇+j*n?、踚%2==1
④gssc(str(a[j][i])+tmp,4)
題組二
1.(2024屆名校協作體聯考,11)定義如下函數:
def f(k):
if k<=3:
　　print(k)
　　return
for i in range(1,4):
　　f(k-i)
return
執行語句f(6),則f(3)被調用的次數為(　　)
A.1次　　　B.2次　　　C.3次　　　D.4次
答案　D　
2.(2024屆強基聯盟聯考,10)執行下列Python代碼,輸出結果為(　　)
def f(s):
m=len(s)
if m==1:
　　return int(s)
else:
　　return f(s[:m-1])+f(s[m-1])
print(f("101"))
A.11　　　　B.2　　　
C.5　　　　D.101
答案　B　
3.(2024屆百校起點調研測試,10)定義如下遞歸函數:
def f(a,n):
n=n-1
if n==0:
　　return a
else:
　　return f(a-1,n)+f(a+1,n)
print(f(5,3))
程序運行后,輸出的結果是(　　)
A.10　　　B.20　　　C.30　　　D.40
答案　B　
4.(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　
5.(2023浙江開學考,12)峰值元素指數組中其值大于左右相鄰值的元素,如序列3、8、4、1中8為峰值元素。一個數組r包含多個峰值元素,現需要找出其中一個峰值元素所在的位置(默認第一個數的左側

展開更多......

收起↑