浙江版高中信息技術(shù)復(fù)習(xí)專(zhuān)題八數(shù)據(jù)結(jié)構(gòu)與算法練習(xí)含答案

專(zhuān)題八數(shù)據(jù)結(jié)構(gòu)與算法考點(diǎn)過(guò)關(guān)練考點(diǎn)一數(shù)據(jù)結(jié)構(gòu)與算法效率1.(2024屆發(fā)展共同體聯(lián)考,12)以下兩個(gè)程序段的功能相同,實(shí)現(xiàn)的功能是:刪除列表a(元素個(gè)數(shù)為n)中的重復(fù)元素(只保留一個(gè)),并將剩下的元素降序輸出。#程序段①#對(duì)列表a進(jìn)行降序排序,代碼略i=1whilei<n:ifa[i]==a[i-1]:forjinrange(i+1,n):a[j-l]=a[j]i-=1;n-=1i+=1#輸出列表元素a[0]到a[n-1],代碼略#程序段②max_num=max(a)#求出列表a中的最大值max_numb=[0]*(max_num+1)foriinrange(0,n):b[a[i]]+=1foriinrange(max_num,0,-1):ifb[i]>0:print(i,end="")關(guān)于上述兩個(gè)程序段及功能的描述,正確的是()A.同樣的數(shù)據(jù)規(guī)模,兩個(gè)程序段的時(shí)間效率一樣B.程序段①加框處語(yǔ)句是否執(zhí)行不受列表a原數(shù)據(jù)的影響C.程序段②加框處語(yǔ)句修改為“foriinrange(1,max_num+1)”,輸出結(jié)果不變D.在實(shí)現(xiàn)該功能的過(guò)程中,程序段②比程序段①需要更多的存儲(chǔ)空間答案D2.常見(jiàn)算法時(shí)間復(fù)雜度函數(shù)的增長(zhǎng)率如圖所示。則當(dāng)問(wèn)題規(guī)模n=100時(shí),下列時(shí)間復(fù)雜度中效率最高的是()A.O(nlog2n)B.O(log2n)C.O(n)D.O(n3)答案B3.有如下Python程序代碼:n=int(input("n="))ans1=ans2=0foriinrange(0,n,2):forjinrange(n):ans1=ans1+1ans2=ans2+ans1print("ans1=",ans1,"ans2=",ans2)則該算法的時(shí)間復(fù)雜度為()A.O(1)B.O(n)C.O(n2)D.O(2n)答案C4.有以下Python程序段:defjishu(n):s=0whilen>0:s+=n%2n//=2returnsn=int(input("輸入一個(gè)正整數(shù):"))ans=jishu(n)print(ans)閱讀上述代碼,回答以下問(wèn)題。(1)該程序運(yùn)行后,輸入整數(shù)23,輸出結(jié)果為。

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

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

答案(1)4(2)5(3)B考點(diǎn)二迭代與遞歸1.(2023浙江1月選考,11,2分)定義如下函數(shù):defrf(n):ifn<3:returnnreturnrf(n-1)+rf(n-3)執(zhí)行語(yǔ)句v=rf(5),函數(shù)rf被調(diào)用的次數(shù)是()A.1B.5C.7D.15答案C2.(2023浙江6月選考,10,2分)定義如下函數(shù):deff(a,s):ifa>=s:returnaelse:returnf(a+1,s-a)執(zhí)行語(yǔ)句k=f(6,21)后,k的值為()A.6B.7C.8D.9答案C3.(2024屆發(fā)展共同體聯(lián)考,10)定義如下函數(shù):deff(x,y):ifx<=2ory>20:returnx+yreturnf(x-1,y+1)執(zhí)行語(yǔ)句k=f(5,1)后,k的值為()A.6B.7C.8D.9答案A4.(2022紹興諸暨期中,10)某Python程序段如下:importrandomfibo=[1]*11foriinrange(2,11):fibo[i]=fibo[i-1]+fibo[i-2]n=random.randint(1,10)print(fibo[n])運(yùn)行該程序段,輸出結(jié)果不可能是()A.1B.21C.35D.89答案C5.(2022紹興諸暨期中,12)下列Python程序的功能是使用迭代算法求s的值。n=int(input("pleaseinputn:"))s=0foriinrange(1,n):ifi%3==0:s=s+iprint("s=",s)程序執(zhí)行時(shí),輸入n的值為25,則輸出的結(jié)果為()A.s=84B.s=118C.s=108D.s=105答案C6.(2022衢州期末,11)某Python程序段如下:defdoit(x):ifx>=6:ans=1else:ans=3*doit(x+1)+2*doit(x+2)returnansprint(doit(3))程序運(yùn)行后,輸出的結(jié)果為()A.17B.21C.61D.62答案C考點(diǎn)三數(shù)據(jù)排序1.(2023浙江1月選考,10,2分)列表s包含8個(gè)互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下Python程序段:n=8foriinrange(1,n-1):forjinrange(1,n-i-1):ifs[j]>s[j-1]:s[j],s[j-1]=s[j-1],s[j]該程序段實(shí)現(xiàn)的是()A.s[0]到s[5]的降序排列B.s[1]到s[6]的降序排列C.s[1]到s[7]的升序排列D.s[2]到s[6]的升序排列答案A2.(2024屆名校協(xié)作體聯(lián)考,10)有如下Python程序:a=[12,45,45,63,0,0,63]cnt=0foriinrange(1,len(a)):j=i-1t=a[i]whilej>=0andt>a[j]:a[j+1]=a[j]j=j-1cnt=cnt+1a[j+1]=tprint(cnt)運(yùn)行該程序后,輸出的結(jié)果是()A.8B.10C.11D.13答案B3.(2024屆浙南名校聯(lián)考,12)有如下Python程序段:fromrandomimportrandintx=randint(2,4)*2a=[9,2,5,1,3,4,8,7]n=len(a)foriinrange(0,n-1):k=iforjinrange(i+1,x):ifa[k]>a[j]:k=jifi!=k:a[k],a[i]=a[i],a[k]print(a)執(zhí)行后,輸出結(jié)果不可能是()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]答案D4.(2024屆天域全國(guó)名校協(xié)作體聯(lián)考,11)列表s存有4個(gè)整數(shù),有如下Python程序段:n=len(s)f=[1]*nforiinrange(n-1):forjinrange(i+1,n):ifs[j]>=s[i]:f[j]+=1else:f[i]+=1print(f)該程序段實(shí)現(xiàn)的功能是標(biāo)記列表中每個(gè)數(shù)值的名次值,名次排序的規(guī)則是()A.數(shù)值越大名次值越大,同數(shù)值先出現(xiàn)的名次值小B.數(shù)值越大名次值越大,同數(shù)值先出現(xiàn)的名次值大C.數(shù)值越大名次值越小,同數(shù)值先出現(xiàn)的名次值小D.數(shù)值越大名次值越小,同數(shù)值先出現(xiàn)的名次值大答案A5.(2022紹興諸暨期中,11)有如下Python程序段:b=[56,80,10,31,24,52,66,49]n=len(b)foriinrange(1,3):forjinrange(0,n-i):ifb[j]>b[j+1]:b[j],b[j+1]=b[j+1],b[j]經(jīng)過(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.[10,24,31,52,49,56,66,80]答案B6.(2022紹興柯橋期末,11)對(duì)一組數(shù)據(jù)采用冒泡排序算法進(jìn)行排序,若第一趟排序完成后的數(shù)據(jù)序列為31,24,23,15,20,10,則該數(shù)據(jù)序列的原始順序不可能是()A.24,23,15,31,10,20B.24,23,15,20,31,10C.24,31,23,15,10,20D.23,24,15,20,31,10答案D考點(diǎn)四數(shù)據(jù)查找1.(2022Z20名校聯(lián)盟聯(lián)考,9)某Python程序如下:importrandomkey=random.randint(35,45)*2i=0;j=len(a)-1;s=[]whilei<=j:m=(i+j+1)//2s.append(a[m])ifkey<a[m]:j=m-1else:i=m+1數(shù)組a中的元素為“58,69,78,80,83,84,90,90,95”,則執(zhí)行該程序段后,數(shù)組s中的元素不可能為()A.83,90,95B.83,78,80C.83,90,90,84D.83,78,69,58答案D2.(2022百校聯(lián)考,12)某程序段如下:a=[9,15,19,20,23,36,78,87,96,100]ans=[];i=0;j=9key=int(input("請(qǐng)輸入待查數(shù)據(jù):"))flag=Falsewhilei<=jandnotflag:m=(i+j)//2ans.append(a[m])ifa[m]==key:flag=Trueelifa[m]>key:j=m-1else:i=m+1print(ans)執(zhí)行該程序后,當(dāng)輸入的key值為15時(shí),輸出的結(jié)果是()A.[23,15]B.[23,19,15]C.[20,15]D.[20,19,15]答案A3.(2022名校協(xié)作體聯(lián)考,12)某算法的Python程序段如下:key=randint(0,3)*2+13i,j,c=0,len(a)-1,0whilei<=j:m=(i+j+1)//2ifa[m]>=key:i=m+1else:j=m-1c+=1列表a=[23,21,19,18,16,15,14,11],該程序段執(zhí)行后,下列說(shuō)法不正確的是()A.i的值為j+1B.i的值可能是8C.j的值可能是5D.c的值一定是3答案B4.(2022諸暨海亮月考,12)下列程序?qū)崿F(xiàn)了輸入k,找出大于k的數(shù)據(jù)的起始索引位置并顯示。a=[1,3,3,5,5,7,10,11,12,15]n=10k=int(input())i=-1j=

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

else:i=mL=

print(">",k,"的數(shù)據(jù)索引起始位置為",L)上述程序段橫線處語(yǔ)句依次為()A.nm-1iB.n-1m-1i+1C.nm+1iD.n-1m+1i+1答案B5.(2022諸暨期末,12)有如下二分查找程序段:#列表a存放整數(shù)升序數(shù)據(jù),代碼略key=int(input())f=[0]*9i=0;j=8whilei<=j:m=(i+j)//2f[m]=1ifa[m]>key:j=m-1else:i=m+1print(f)輸入待查找數(shù)據(jù),執(zhí)行該程序段后,下列選項(xiàng)中,列表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]答案C6.(2022紹興諸暨期中,19)小明學(xué)了排序和查找算法后,編寫(xiě)了一個(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)诔绦騽澗€處填入合適的代碼。#從Excel文件中讀取n個(gè)學(xué)生的技術(shù)成績(jī)存儲(chǔ)在列表a中,代碼略#對(duì)列表a中的元素進(jìn)行升序排序n=len(a)foriinrange(n-1):forjinrange(0,n-i-1):if①:

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

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

答案①a[j]>a[j+1]②key<a[m]③str(n-i)專(zhuān)題綜合練題組一1.(2024屆A9協(xié)作體返?？?11)有如下Python程序段:importrandoma=[1,3,4,6,6,6,9,9,11,12]key=random.randint(2,5)*2i,j=0,9whilei<=j:m=(i+j)//2ifkey<a[m]:j=m-1else:i=m+1print(j)執(zhí)行該程序段后,輸出的結(jié)果不可能是()A.2B.3C.5D.7答案B2.(2024屆Z20聯(lián)盟聯(lián)考,10)有如下Python函數(shù):deftrans(num,n):s="0123456789ABCDEF"ifnum<n:returns[num]else:returntrans(num//n,n)+s[num%n]執(zhí)行語(yǔ)句a=trans(394,16)后,a的值為()A.19AB.1810C.180D.18A答案D3.(2024屆七彩聯(lián)盟聯(lián)考,10)有如下程序段:defcal(n):ifn<=1:return1ifn%2==0:return2*cal(n-1)return1+cal(n-1)執(zhí)行語(yǔ)句k=cal(5),則k的值為()A.6B.7C.10D.11答案B4.(2024屆強(qiáng)基聯(lián)盟統(tǒng)測(cè),10)有如下程序段:deffun(k):ifk==1:return"1"elifk%2==0:returnfun(k-1)+str(k%2)else:returnstr(k%2)+fun(k-1)執(zhí)行語(yǔ)句s=fun(5),則s的值為()A."00111"B."11010"C."11100"D."10110"答案C5.(2024屆新陣地聯(lián)盟聯(lián)考,10)有如下Python程序:importrandomdeffunc(n):ifn==1:return1elifn==2:return2elifn%2==1:return2*func(n-2)+func(n-1)else:returnfunc(n-2)+2*func(n-1)p=random.randint(3,6)print(func(p))執(zhí)行程序后,輸出結(jié)果不可能為()A.4B.10C.12D.18答案C6.(2024屆天域全國(guó)名校協(xié)作體聯(lián)考,10)某遞歸函數(shù)如下所示:defhs(m):ifm<=1:f=1else:f=hs(m-1)+hs(m-2)returnfans=0foriinrange(5):ifhs(i)%2==1:ans+=1print(ans)程序運(yùn)行后,輸出的結(jié)果是()A.2B.3C.4D.5答案C7.(2023十校聯(lián)盟聯(lián)考,12)某二分查找算法的Python程序段如下:importrandomkey=random.randint(0,4)*2+5n=10;ans=0a=[4,5,5,8,9,11,11,13,15,17]i=0;j=n-1whilei<=j:m=(i+j)//2ifa[m]<=key:i=m+1else:j=m-1ans+=a[m]print(ans)執(zhí)行該程序段后,ans的值不可能是()A.19B.27C.37D.44答案A8.(2024屆七彩聯(lián)盟聯(lián)考,15)某工廠每天會(huì)收到多個(gè)訂單,有n臺(tái)機(jī)器對(duì)零件進(jìn)行加工。為減少機(jī)器的損耗,需要在滿(mǎn)足所有訂單加工的情況下(訂單即到即加工),機(jī)器開(kāi)啟數(shù)量盡量少。若開(kāi)啟n臺(tái)機(jī)器不能滿(mǎn)足訂單即到即加工,則計(jì)算所有訂單最少的平均等待時(shí)間。若給定某天內(nèi)所有的訂單信息,請(qǐng)計(jì)算需要開(kāi)啟的機(jī)器數(shù)量以及訂單平均等待時(shí)間,代碼運(yùn)行效果圖如圖所示(注意:若上一個(gè)訂單結(jié)束時(shí)間為9:00,下一個(gè)訂單開(kāi)啟時(shí)間最早為9:00)。訂單信息如下:(批次,到達(dá)時(shí)間,加工時(shí)間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)機(jī)器數(shù)量:22臺(tái)機(jī)器全部開(kāi)啟,訂單平均等待2.5min第1臺(tái)機(jī)器:A1:09:00~09:30,A8:09:30~09:50,A4:10:00~11:00,A3:11:00~11:50第2臺(tái)機(jī)器:A5:09:20~10:00,A7:10:20~11:00,A6:11:00~11:20,A2:11:30~12:20請(qǐng)回答下列問(wèn)題:(1)上圖所示的例子中,若機(jī)器有10臺(tái),則只需要開(kāi)啟臺(tái)機(jī)器。

(2)定義如下data_sort(a)函數(shù),參數(shù)a為列表,列表中每個(gè)元素包含三個(gè)數(shù)據(jù)項(xiàng),依次分別對(duì)應(yīng)訂單批次、到達(dá)時(shí)間、加工時(shí)間(時(shí)間均轉(zhuǎn)為分鐘)。該函數(shù)實(shí)現(xiàn)將列表a按照訂單到達(dá)時(shí)間升序排序。defdata_sort(a):foriinrange(len(a)):forjinrange(len(a)-i-1):if:

a[j],a[j+1]=a[j+1],a[j]①劃線處填入的語(yǔ)句為,可實(shí)現(xiàn)上述功能。

②若將加框處語(yǔ)句寫(xiě)錯(cuò)為range(i,len(a)-1),則下列4組數(shù)據(jù)中,列表a的值為(單選,填字母)時(shí)不能測(cè)試出問(wèn)題。

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)實(shí)現(xiàn)計(jì)算開(kāi)啟機(jī)器數(shù)量的部分Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defhuan(n):#將分鐘轉(zhuǎn)換為時(shí)間AA:BB格式,返回值為字符串,代碼略#讀取文件中的信息,并存儲(chǔ)在列表order中,代碼略data_sort(order)n=int(input("機(jī)器數(shù)量:"))foriinrange(len(order)):order[i].append(-1)#order[i]追加一個(gè)元素-1mach=[-1]*nnum,wait=0,0foriinrange(len(order)):k=-1time=-1forjin①:

t1=mach[j]ifk==-1:k=jtime=order[t1][1]+order[t1][2]else:t2=mach[k]iforder[t1][1]+order[t1][2]<order[t2][1]+order[t2][2]:k=jtime=order[t1][1]+order[t1][2]ifk==-1ornum<nand②:

mach[num]=inum+=1else:order[i][3]=mach[k]mach[k]=iiftime>order[i][1]:wait+=time-order[i][1]order[i][1]=timeifnum<n:print("只需開(kāi)啟"+str(num)+"臺(tái)機(jī)器")else:print(str(n)+"臺(tái)機(jī)器全部開(kāi)啟,訂單平均等待"+str(round(wait/len(order),2))+"min")foriinrange(num):print('第'+str(i+1)+'臺(tái)機(jī)器:')p=mach[i]ans=''whilep!=-1:ans=order[p][0]+':'+huan(order[p][1])+'~'+huan(order[p][1]+order[p][2])+','+ansp=③

print(ans[:-1])答案(1)3(2)①a[j][1]>a[j+1][1]②A(3)①range(num)②time>order[i][1]③order[p][3]9.(2024屆名校協(xié)作體聯(lián)考,15)有一款益智游戲,規(guī)則如下:軌道上有不同顏色的珠子連成珠串,玩家可以通過(guò)炮臺(tái)發(fā)射若干珠子,每次發(fā)射一顆珠子到珠串中的某位置,形成新的珠串。當(dāng)新珠串中出現(xiàn)3顆及以上顏色相同的連續(xù)珠子時(shí),這些連續(xù)的同色珠子會(huì)被消除,并獲得相應(yīng)積分,若消除后仍有符合條件的同色珠子,會(huì)繼續(xù)被消除。記分規(guī)則為:在被消除的連續(xù)珠子中,前面3顆直接記3分,其余的珠子每顆記2分,例如有5顆相同顏色的連續(xù)珠子被消除,可獲得7分。程序運(yùn)行過(guò)程如圖所示?，F(xiàn)軌道的珠串為:-1->3->1->5->4->2->2->1->2->2當(dāng)前珠子的顏色為:1請(qǐng)輸入當(dāng)前發(fā)射位置:7當(dāng)前珠子的顏色為:1請(qǐng)輸入當(dāng)前發(fā)射位置:7當(dāng)前珠子的顏色為:4請(qǐng)輸入當(dāng)前發(fā)射位置:5當(dāng)前珠子的顏色為:4請(qǐng)輸入當(dāng)前發(fā)射位置:5最終得分為11軌道中剩余的珠串為:-1->3->1->5編寫(xiě)程序模擬游戲的實(shí)現(xiàn)過(guò)程,珠子的顏色用數(shù)字表示,為方便處理,在珠串最前面加入一顆不可消除的珠子,顏色值為-1。請(qǐng)回答下列問(wèn)題:(1)若珠串為-1,2,2,3,3,2,2,將顏色為3的珠子發(fā)射到顏色為2和3的珠子之間,可獲得積分為。

(2)定義如下insert(t,pos)函數(shù),函數(shù)功能是將顏色為t的珠子,插入到當(dāng)前珠串中的第pos顆珠子后面(列表link存儲(chǔ)珠串的相關(guān)數(shù)據(jù),例如link中某元素的值為[3,2],3表示某顆珠子的顏色,2表示與該珠子相鄰的下一顆珠子的存儲(chǔ)地址,變量head保存珠串第一個(gè)珠子的存儲(chǔ)地址),請(qǐng)?jiān)趧澗€處填入合適的代碼。definsert(t,pos):#將顏色為t的珠子,插入到當(dāng)前珠串第pos顆珠子的后面p=headwhilepos>1:pos-=1p=link[p][1]link.append()

link[p][1]=len(link)-1(3)定義如下fun()函數(shù),函數(shù)功能是:查找珠串里最早出現(xiàn)的可消除珠串,函數(shù)返回ret,ret由該珠串起始珠子的前一顆珠子位置和該珠串的連續(xù)長(zhǎng)度組成。deffun():p=head;st=headpre=pnum=0lastcolor=-1ret=[-1,0]whilep!=-1:t=link[p][0]ift!=lastcolor:ifnum>=3:ret=[st,num]breaklastcolor=tst=prenum=1else:num+=1pre=pp=link[p][1]ifnum>=3:ret=[st,num]returnret若將函數(shù)中加框處代碼刪除,會(huì)導(dǎo)致某些情況下無(wú)法得到符合函數(shù)功能的結(jié)果。調(diào)用fun()函數(shù),下列4組數(shù)據(jù)中能測(cè)試出這一問(wèn)題的是(單選,填字母)。

A.head=4link=[[2,3],[1,0],[1,1],[2,-1],[-1,2]]B.head=0link=[[-1,1],[2,3],[2,4],[2,2],[1,-1]]C.head=1link=[[2,-1],[-1,3],[2,0],[1,4],[2,2]]D.head=4link=[[2,-1],[1,0],[1,1],[1,2],[-1,3]](4)實(shí)現(xiàn)模擬游戲過(guò)程的部分Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defclear(g):#根據(jù)fun函數(shù)的返回值對(duì)珠串進(jìn)行消除,并統(tǒng)計(jì)獲得本次消除的積分p=g[0]q=plength=g[1]ret=①

whilelength>=0:q=link[q][1]length-=1link[p][1]=qreturnretdeftraverl():#將軌道中珠串按序輸出,代碼略head=7link=[[1,3],[1,8],[2,1],[5,5],[2,2],[4,4],[3,0],[-1,6],[2,9],[2,-1]]print("現(xiàn)軌道的珠串為:")traverl()points=0que=[1,1,4,4]#保存炮臺(tái)中待發(fā)射珠子的顏色qhead=0qtail=4whileqhead!=qtail:print("當(dāng)前珠子的顏色為:",que[ghead])s=int(input("請(qǐng)輸入當(dāng)前發(fā)射位置:"))insert(que[qhead],s)qhead+=1g=fun()whileg!=[-1,0]:points+=clear(g)②

print("最終得分為",points)print("軌道中剩余的珠串為:")traverl()答案(1)8(2)[t,link[p][1]](3)C(4)①3+(length-3)*2②g=fun()10.(2024屆發(fā)展共同體聯(lián)考,15)某業(yè)務(wù)服務(wù)大廳共有m個(gè)服務(wù)窗口(編號(hào)為0~m-1),服務(wù)大廳根據(jù)服務(wù)對(duì)象的優(yōu)先等級(jí)(等級(jí)分為1~10,數(shù)字越大優(yōu)先級(jí)越高)從高到低依次分配窗口并提供服務(wù)。某個(gè)時(shí)間段內(nèi)(該時(shí)間段起始時(shí)刻各窗口都空閑著),服務(wù)對(duì)象按服務(wù)優(yōu)先等級(jí)從高到低排隊(duì)后依次到空閑的窗口享受服務(wù),服務(wù)優(yōu)先等級(jí)相同時(shí),先到達(dá)的先享受服務(wù)。由于辦理的業(yè)務(wù)不同,每個(gè)服務(wù)對(duì)象的服務(wù)時(shí)長(zhǎng)(單位:分鐘)可能是不相同的。按照上述服務(wù)規(guī)則,問(wèn)所有服務(wù)對(duì)象完成業(yè)務(wù)辦理需要多少時(shí)間。一個(gè)服務(wù)對(duì)象業(yè)務(wù)辦理結(jié)束,另一個(gè)服務(wù)對(duì)象馬上到該窗口接受服務(wù),中間浪費(fèi)的時(shí)間忽略不計(jì)。圖a描述了5個(gè)服務(wù)對(duì)象的信息,按照服務(wù)規(guī)則確定的服務(wù)次序如圖b所示。到達(dá)序號(hào)服務(wù)優(yōu)先等級(jí)服務(wù)時(shí)長(zhǎng)1710261234324524568圖a到達(dá)序號(hào)服務(wù)優(yōu)先等級(jí)服務(wù)時(shí)長(zhǎng)服務(wù)次序171012612234325452445683圖b若服務(wù)大廳提供2個(gè)服務(wù)窗口(m=2),則所有服務(wù)對(duì)象完成業(yè)務(wù)辦理需要50分鐘。具體方案可以是:0號(hào)窗口依次服務(wù)到達(dá)序號(hào)為1、5、3的對(duì)象,1號(hào)窗口依次服務(wù)到達(dá)序號(hào)為2、4的對(duì)象。請(qǐng)回答下列問(wèn)題:(1)若有6個(gè)服務(wù)對(duì)象的信息如圖c所示,根據(jù)上述服務(wù)規(guī)則,在提供3個(gè)服務(wù)窗口的情況下,所有服務(wù)對(duì)象完成業(yè)務(wù)辦理需要分鐘。

到達(dá)序號(hào)服務(wù)優(yōu)先等級(jí)服務(wù)時(shí)長(zhǎng)132257341341558126411圖c(2)定義如下sort_lst(lst)函數(shù),參數(shù)lst是所有服務(wù)對(duì)象信息構(gòu)成的列表。函數(shù)的功能是將列表lst按照服務(wù)對(duì)象的優(yōu)先等級(jí)降序排列并構(gòu)成鏈表,返回排序后的鏈表及其頭指針。defsort_lst(lst):foriinrange(len(lst)):lst[i].append(-1)head=0foriinrange(1,len(lst)):p=headwhilep!=-1:iflst[p][1]>=lst[i][1]:q=pp=lst[p][3]else:breakifp==head:lst[i][3]=headhead=ielse:lst[q][3]=ilst[i][3]=preturnlst,head若lst列表依次存儲(chǔ)圖c所示的服務(wù)對(duì)象信息,如lst[0]為[1,3,2],各數(shù)據(jù)項(xiàng)依次表示服務(wù)對(duì)象的到達(dá)序號(hào),服務(wù)優(yōu)先等級(jí)及服務(wù)時(shí)長(zhǎng)。調(diào)用sort_lst(lst)時(shí),程序中加框處的語(yǔ)句“q=p”總共執(zhí)行次。

(3)計(jì)算時(shí)間段內(nèi)服務(wù)對(duì)象完成業(yè)務(wù)辦理所需時(shí)間的部分Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defproc(lst,p,n,m):s=[0]*mforiinrange(m):#前m個(gè)人直接開(kāi)始服務(wù),等待時(shí)間為0ifp==-1:breaks[i]=lst[p][2]①

ans=0whilep!=-1:k=s[0]#找出正在被服務(wù)的對(duì)象中最早結(jié)束的一個(gè)forjinrange(1,m):ifs[j]<k:k=s[j]ans+=kforjinrange(m):s[j]-=kif②:

s[i]=lst[p][2]p=lst[p][3]k=s[0]foriinrange(m):ifs[i]>k:k=s[i]③

print("所有服務(wù)對(duì)象完成業(yè)務(wù)辦理需要",str(ans),"分鐘")'''讀入服務(wù)對(duì)象總數(shù)n和窗口數(shù)m按到達(dá)序號(hào)讀入n個(gè)服務(wù)對(duì)象的信息到列表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)#對(duì)lst按照服務(wù)對(duì)象優(yōu)先等級(jí)降序排序proc(lst,head,n,m)答案(1)18(2)7(3)①p=lst[p][3]或其他等價(jià)答案②s[j]==0andp!=-1或其他等價(jià)答案③ans=ans+k或其他等價(jià)答案11.(2024浙江1月選考,15,9分)某項(xiàng)活動(dòng)有n個(gè)單位(編號(hào)1到n)參加,需將員工分成若干個(gè)小組,每個(gè)小組的人數(shù)上限為m,小組編號(hào)按新建次序從1開(kāi)始編號(hào)。分組時(shí),首先按單位編號(hào)次序依次在各單位內(nèi)部分組,每m人分配到一個(gè)新建小組中,不足m人的剩余員工暫不分配;然后按剩余員工人數(shù)由大到小的順序,依次為各單位剩余員工分配小組。若某單位剩余員工人數(shù)為k,則分配方法為:在已建的小組中查找空位數(shù)(該小組還可容納的人數(shù))大于或等于k的小組,如果找到的小組有多個(gè),則選擇空位數(shù)最少的小組,將此k人分配到該小組中;如果沒(méi)有找到,則新建一個(gè)小組,將此k人分配到該小組中。設(shè)n為5,m為20,各單位員工人數(shù)及單位內(nèi)部的分組過(guò)程如圖a所示,各單位剩余員工的分組過(guò)程如圖b所示。編寫(xiě)程序:給定各單位編號(hào)及員工人數(shù),根據(jù)上述方法進(jìn)行分組處理,按單位編號(hào)次序輸出各單位所分配的分組編號(hào)。請(qǐng)回答下列問(wèn)題:(1)由題意可知,若僅將圖a中1號(hào)單位的員工人數(shù)修改為25,然后對(duì)圖中5個(gè)單位重新分組,則1號(hào)單位所分配的分組編號(hào)為。

(2)定義如下bubble_sort(lst)函數(shù),參數(shù)lst的每個(gè)元素由單位編號(hào)和剩余員工人數(shù)2個(gè)數(shù)據(jù)項(xiàng)組成。函數(shù)的功能是根據(jù)每個(gè)單位的剩余員工人數(shù),對(duì)lst進(jìn)行降序排序。defbubble_sort(lst):n=len(lst)foriinrange(0,n-1):forjinrange(n-1,i,-1):iflst[j-1][1]<lst[j][1]:tmp=lst[j]lst[j]=lst[j-1]lst[j-1]=tmpiflst[i][1]==0:breakreturn調(diào)用該函數(shù),若lst為[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],請(qǐng)回答①和②兩個(gè)問(wèn)題。①框中的程序段第1次執(zhí)行后,關(guān)于lst中的剩余員工人數(shù),下列說(shuō)法正確的是(單選,填字母)。

A.lst[0][1]數(shù)值最小B.lst[0][1]數(shù)值最大C.lst[5][1]數(shù)值最小D.lst[5][1]數(shù)值最大②框中的程序段執(zhí)行的次數(shù)為。

(3)實(shí)現(xiàn)分組功能的部分Python程序如下,程序中用到的列表函數(shù)與方法如圖c所示,請(qǐng)?jiān)诔绦蛑袆澗€處填入合適的代碼。函數(shù)與方法功能w.append(x)在列表w末尾添加元素xx.w.pop()將列表w末尾元素賦值給x,并將其從w中刪除圖cdefgroup(data,m):n=len(data)a=[]foriinrange(n+1):a.append([])#a[i]初始化為空列表,存放編號(hào)為i的單位所分配的分組編號(hào)gnum=0foriinrange(n):#各單位內(nèi)部分組whiledata[i][1]>=m:gnum+=1k=data[i][0]a[k].append(gnum)①

bubble_sort(data)#根據(jù)每個(gè)單位的剩余員工人數(shù),對(duì)data進(jìn)行降序排序b=[]foriinrange(m):b.append([])i=0#對(duì)剩余員工分組whilei<nanddata[i][1]!=0:②

whilej<mandlen(b[j])==0:j+=1ifj<m:v=b[j].pop()else:gnum+=1v=gnuma[data[i][0]].append(v)③

i+=1#輸出各單位的分組編號(hào),代碼略'''讀取小組人數(shù)上限存入m;讀取1至n號(hào)單位的數(shù)據(jù),依次存入列表data的data[0]至data[n-1]中。data[i]包含2個(gè)數(shù)據(jù)項(xiàng),data[i][0],data[i][1]分別存放單位編號(hào)及員工人數(shù),代碼略'''group(data,m)答案(1)1,8(2)①B②4(3)①data[i][1]-=m②j=data[i][1]③b[j-data[i][1]].append(v)12.(2024屆浙南名校聯(lián)盟聯(lián)考,15)某工廠將送達(dá)的各批次物品按品種打包。小李將各批次物品信息按送達(dá)時(shí)間順序合并,得到如圖a-2所示數(shù)據(jù)data。同一個(gè)包裹只能裝入同一品種任意批次的物品,當(dāng)某一個(gè)品種物品A送達(dá)使得已送達(dá)的該品種物品總質(zhì)量超過(guò)m時(shí),則將在該物品之前送達(dá)的物品按質(zhì)量由大到小依次裝入包裹,其余質(zhì)量不足m的品種,按各品種依次裝入包裹。編寫(xiě)程序,讀取物品合并更新后的信息,按送達(dá)時(shí)間順序打包,輸出各包裹中的物品序號(hào),運(yùn)行結(jié)果如圖b所示。序號(hào)品種送達(dá)時(shí)間批次質(zhì)量(千克)128:3516218:5018309:1012409:1514序號(hào)品種送達(dá)時(shí)間批次質(zhì)量(千克)108:3023序號(hào)品種送達(dá)時(shí)間批次質(zhì)量(千克)108:4034圖a-1序號(hào)品種送達(dá)時(shí)間批次質(zhì)量(千克)108:3023228:3516308:4034418:5018509:1012609:1514圖a-2m=10data=[[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個(gè)包裹中品種為0,各物品的序號(hào)依次是:3,1,5,第2個(gè)包裹中品種為0,各物品的序號(hào)依次是:6,第3個(gè)包裹中品種為1,各物品的序號(hào)依次是:4,第4個(gè)包裹中品種為2,各物品的序號(hào)依次是:2,圖b請(qǐng)回答下列問(wèn)題:(1)送達(dá)物品信息合并后如圖a-2所示,若包裹裝入物品質(zhì)量不能超過(guò)8千克,則首先打包完成的包裹中裝入品種為0,各物品的序號(hào)依次是。

(2)定義data_sort(lst)函數(shù)。先將數(shù)據(jù)(見(jiàn)圖a-1)合并得到lst列表(見(jiàn)圖a-2),函數(shù)data_sort(lst)的功能是對(duì)lst列表按送達(dá)時(shí)間升序排列,并對(duì)序號(hào)進(jìn)行更新。defdata_sort(lst):foriinrange(n-1):#n為數(shù)據(jù)個(gè)數(shù)forjinrange(n-1,i,-1):iflst[j][2]<lst[j-1][2]:lst[j],lst[j-1]=lst[j-1],lst[j]lst[i][0]=i+1returnlst執(zhí)行上述代碼后,(填寫(xiě):能/不能)正確得到圖a-2中的數(shù)據(jù)。

(3)實(shí)現(xiàn)上述功能的部分Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defpack(k):#對(duì)品種k已送達(dá)待打包的物品按質(zhì)量由大到小輸出#部分代碼略p=b[k][1]num+=1print("第"+str(num)+"個(gè)包裹中品種為"+str(k)+",各物品的序號(hào)依次是:",end="")whilep!=-1:print(data[p][0],end=",")p=x[p]print()#合并后排序得到n件物品的數(shù)據(jù)存儲(chǔ)在數(shù)組data中并輸出,包裹最大承受質(zhì)量為m千克。物品品種的數(shù)量是sn,代碼略b=[[0,-1]foriinrange(sn)]x=[-1foriinrange(n)]num=0foriinrange(n):k=data[i][1]ifb[k][0]+data[i][4]>m:pack(k)b[k]=[0,-1]p=①

ifp==-1:b[k][1]=ielse:ifdata[i][4]>data[p][4]:b[k][1]=i②

else:q=-1while③:

q=pp=x[p]x[q]=ix[i]=pb[k][0]+=data[i][4]#質(zhì)量不足m的品種,按品種依次裝入包裹foriinrange(sn):ifb[i][1]!=-1:pack(i)答案(1)3,1(2)不能(3)①b[k][1]②x[i]=p③p!=-1anddata[i][4]<=data[p][4]或p>-1anddata[i][4]<=data[p][4]或p>=0anddata[i][4]<=data[p][4]13.(2024屆新陣地聯(lián)盟聯(lián)考,15)進(jìn)入新學(xué)期第一天,班主任老師將班上N個(gè)同學(xué)(學(xué)號(hào)為1~N)排成一排,分配座位。從排隊(duì)到分配座位步驟如下:步驟一:先將1號(hào)同學(xué)安排進(jìn)隊(duì);步驟二:2~N號(hào)同學(xué)由老師依次指定入隊(duì)位置,如學(xué)號(hào)為i的同學(xué)由老師指定站在隊(duì)中某位同學(xué)的左側(cè)或右側(cè);步驟三:所有同學(xué)按照上述方法入隊(duì)完畢后,以2人一組的方式依次分配到四個(gè)組別中;步驟四:輸出每組學(xué)生的名單。請(qǐng)回答下列問(wèn)題。(1)若某班有4位同學(xué),學(xué)號(hào)為1~4,完成步驟一后,執(zhí)行步驟二的指令3次,每次指令包含兩個(gè)整數(shù)k和p(p為0或1)。若p為0,則表示插在k號(hào)同學(xué)的左側(cè),p為1則表示插在k號(hào)同學(xué)的右側(cè)。若三條指令分別為10、21、10,則執(zhí)行指令后隊(duì)伍從左到右學(xué)號(hào)分別為。

(2)實(shí)現(xiàn)上述功能的部分Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。#insert(k,x)函數(shù)的功能是在k號(hào)的右側(cè)插入x號(hào)同學(xué)#L和R列表分別用于記錄每位同學(xué)的左側(cè)和右側(cè)的同學(xué)學(xué)號(hào)definsert(k,x):R[x]=R[k]L[x]=k①

R[k]=xL=[0]*100;R=[0]*100;vis=[0]*100insert(0,1)#0的右邊插入1號(hào)同學(xué)#info列表存儲(chǔ)各學(xué)生姓名和學(xué)號(hào),格式如[["張三",1],["李四",2]…],代碼略n=int(input("請(qǐng)輸入同學(xué)人數(shù):"))foriinrange(2,n+1):k=int(input("請(qǐng)問(wèn)插入在幾號(hào)同學(xué)旁邊?"))p=int(input("請(qǐng)輸入該同學(xué)的左側(cè)還是右側(cè)"))ifp==0:②

else:insert(k,i)q=[[]foriinrange(4)]i=m=0③

whilex!=0:q[i].append(x)m=m+1ifm%2==0:④

x=R[x]foriinrange(4):forjinq[i]:print(info[j-1][0],end="")print()答案(1)2341(2)①L[R[k]]=x②insert(L[k],i)③x=R[0]④i=(i+1)%414.(2023學(xué)軍中學(xué)月考,15)學(xué)校為了使本校畢業(yè)生能以更好的狀態(tài)參加高考,都會(huì)創(chuàng)造條件向上級(jí)申請(qǐng)?jiān)诒拘ＴO(shè)立標(biāo)準(zhǔn)化考點(diǎn),讓學(xué)生能在本校參加考試。標(biāo)準(zhǔn)化考點(diǎn)要求很多,其中之一就是各考場(chǎng)內(nèi)的座位安排必須是蛇形排列,保證使用A、B卷的同學(xué)能完全錯(cuò)開(kāi),如圖a所示。小明用Python編寫(xiě)了一個(gè)模擬考場(chǎng)座位編排程序,程序運(yùn)行結(jié)果如圖b所示,每個(gè)座位號(hào)占4位寬度右對(duì)齊。輸出程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defpx(lst):foriinrange(len(lst)-1):k=iforjinrange(①):

iflst[j]>lst[k]:k=jifk!=i:lst[i],lst[k]=lst[k],lst[i]defgssc(t,n):#將字符t按n個(gè)字符寬度輸出t=""*(n-len(t))+treturntn=int(input('請(qǐng)輸入行數(shù):'))m=int(input('請(qǐng)輸入列數(shù):'))a=[]forjinrange(m):a.append([])foriinrange(n):a[j].append(②)

foriinrange(m):if③:

px(a[i])foriinrange(n):st=""forjinrange(m):tmp='A'ifa[j][i]%2==1:tmp='B'st+=④#每個(gè)座位號(hào)按4位輸出

print(st)答案①i+1,len(lst)②i+j*n③i%2==1④gssc(str(a[j][i])+tmp,4)題組二1.(2024屆名校協(xié)作體聯(lián)考,11)定義如下函數(shù):deff(k):ifk<=3:print(k)returnforiinrange(1,4):f(k-i)return執(zhí)行語(yǔ)句f(6),則f(3)被調(diào)用的次數(shù)為()A.1次B.2次C.3次D.4次答案D2.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,10)執(zhí)行下列Python代碼,輸出結(jié)果為()deff(s):m=len(s)ifm==1:returnint(s)else:returnf(s[:m-1])+f(s[m-1])print(f("101"))A.11B.2C.5D.101答案B3.(2024屆百校起點(diǎn)調(diào)研測(cè)試,10)定義如下遞歸函數(shù):deff(a,n):n=n-1ifn==0:returnaelse:returnf(a-1,n)+f(a+1,n)print(f(5,3))程序運(yùn)行后,輸出的結(jié)果是()A.10B.20C.30D.40答案B4.(2022寧波九校聯(lián)考期末,12)某二分查找算法的Python程序段如下,運(yùn)行該段代碼后,輸出的結(jié)果不可能是()importrandoma=[10,20,30,40,50,60,70,80]key=random.choice(a);i,j=0,len(a)-1s=""whilei<=j:m=(i+j)//2ifkey==a[m]:s=s+"M";breakelifkey<a[m]:j=m-1;s=s+"L"else:i=m+1;s=s+"R"print(s)A.LLMB.LRMC.RRRMD.RRLM答案D5.(2023浙江開(kāi)學(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也為峰值元素)?，F(xiàn)有實(shí)現(xiàn)該功能的Python程序如下:i=0;j=6whilei<j:m=(i+j)//2ifa[m+1]>a[m]:i=m+1else:j=mprint("峰值位置是",i)數(shù)組a=[10,2,25,17,20,21,9],執(zhí)行該程序后,輸出的值為()A.0B.2C.5D.8答案C6.(2023十校聯(lián)盟聯(lián)考,9)有如下Python程序段:deftrans(m,n):ifm!=0:r=m%nreturntrans(m//n,n)+str(r)else:return"0"a=int(input("a="))b=int(input("b="))print(trans(a,b))執(zhí)行該程序段,依次輸入11和2,則輸出的結(jié)果是()A.1011B.1101C.01011D.11010答案C7.(2023浙南名校聯(lián)盟聯(lián)考,8)小王走樓梯,每次走1個(gè)臺(tái)階或2個(gè)臺(tái)階,問(wèn)小王走n個(gè)臺(tái)階時(shí),有多少種不同的走法?現(xiàn)編寫(xiě)代碼如下:defupstairs(n):ifn==0orn==1:return1else:returnupstairs(n-1)+upstairs(n-2)n=int(input('請(qǐng)輸入樓梯有幾個(gè)臺(tái)階:'))way=upstairs(n)print(way)當(dāng)輸入的樓梯有10個(gè)臺(tái)階時(shí),請(qǐng)問(wèn)有多少種走樓梯的方法()A.88B.89C.90D.91答案B8.(2024屆天域全國(guó)名校協(xié)作體聯(lián)考,15)計(jì)算機(jī)運(yùn)行多個(gè)任務(wù)(又稱(chēng)進(jìn)程)時(shí),需要進(jìn)行調(diào)度。有的進(jìn)程需要優(yōu)先響應(yīng),例如用戶(hù)的交互操作,此時(shí)就需要暫停當(dāng)前運(yùn)行的進(jìn)程,讓CPU先執(zhí)行需要優(yōu)先響應(yīng)的進(jìn)程,這稱(chēng)為搶占。操作系統(tǒng)需要設(shè)計(jì)調(diào)度算法,來(lái)決定CPU運(yùn)行進(jìn)程的順序。優(yōu)先級(jí)搶占式調(diào)度算法是一種簡(jiǎn)單的調(diào)度算法,規(guī)則如下:1)將進(jìn)程分為m個(gè)優(yōu)先級(jí),設(shè)置m個(gè)等待隊(duì)列,分別對(duì)應(yīng)每一級(jí)優(yōu)先級(jí)。2)每個(gè)進(jìn)程具有三個(gè)要素:到達(dá)時(shí)間,運(yùn)行所需時(shí)長(zhǎng),優(yōu)先級(jí)數(shù)(數(shù)越大優(yōu)先級(jí)越高)。3)相同優(yōu)先級(jí)的進(jìn)程,按照先到先服務(wù)的原則依次執(zhí)行。4)同一時(shí)刻中,先將到達(dá)的進(jìn)程都加入隊(duì)列,再按照優(yōu)先級(jí)進(jìn)行分配。5)只有當(dāng)k級(jí)隊(duì)列為空的時(shí)候,才會(huì)為k-1級(jí)隊(duì)列隊(duì)首的進(jìn)程分配時(shí)間。6)進(jìn)程Pi運(yùn)行時(shí),如果有優(yōu)先級(jí)更高的進(jìn)程Pj到達(dá),則立即發(fā)生搶占,先執(zhí)行Pj,并將進(jìn)程Pi未執(zhí)行完的部分,重新加入Pi優(yōu)先級(jí)對(duì)應(yīng)的隊(duì)列末尾,等待繼續(xù)執(zhí)行。編寫(xiě)程序模擬CPU分配計(jì)算資源的過(guò)程,已知按照到達(dá)時(shí)間升序排序的進(jìn)程數(shù)據(jù)(包含到達(dá)時(shí)間、運(yùn)行時(shí)長(zhǎng)、優(yōu)先級(jí)),計(jì)算并輸出每個(gè)進(jìn)程最終處理完成的時(shí)間。(時(shí)間單位均為毫秒)請(qǐng)回答下列問(wèn)題:(1)有4個(gè)進(jìn)程A、B、C、D如圖所示。進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)長(zhǎng)優(yōu)先級(jí)A071B242C413D542由優(yōu)先級(jí)搶占式調(diào)度算法的規(guī)則可知,0毫秒時(shí)進(jìn)程A到達(dá)并執(zhí)行;2毫秒時(shí)進(jìn)程B到達(dá),B的優(yōu)先級(jí)高于A,發(fā)生搶占,A剩余的5毫秒回到隊(duì)列1,B開(kāi)始執(zhí)行;4毫秒時(shí)進(jìn)程C到達(dá),C的優(yōu)先級(jí)高于B,發(fā)生搶占,B剩余的2毫秒回到隊(duì)列2,C開(kāi)始執(zhí)行;則進(jìn)程D執(zhí)行完的時(shí)刻為。

(2)模擬實(shí)現(xiàn)優(yōu)先級(jí)搶占式調(diào)度算法Python程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。definsert(p,remain):data[p][2]=remain#更新進(jìn)程剩余的運(yùn)行時(shí)間lvl=data[p][3]ifqueinfo[lvl][0]==-1:queinfo[lvl][0]=pifqueinfo[lvl][1]!=-1:data[queinfo[lvl][1]][-1]=pdata[p][-1]=-1queinfo[lvl][1]=pm=int(input('設(shè)置優(yōu)先級(jí)的數(shù)量m:'))#輸入列表data存儲(chǔ)進(jìn)程,data中的節(jié)點(diǎn)包含信息有[名稱(chēng),到達(dá)時(shí)間,運(yùn)行時(shí)長(zhǎng),優(yōu)先級(jí)],代碼略#進(jìn)程已經(jīng)按到達(dá)時(shí)間升序排序#例如:data=[['A',0,7,1],['B',2,4,2],['C',4,1,3],['D',5,4,2]]foriinrange(len(data)):data[i].append(-1)queinfo=[[-1,-1]foriinrange(m+1)]insert(0,data[0][2])#將第1個(gè)進(jìn)程加入隊(duì)列time=data[0][1]cnt=1#所有隊(duì)列內(nèi)等待的進(jìn)程總數(shù)idx=1lvl=mwhilecnt>0:ifqueinfo[lvl][0]!=-1:cur=queinfo[lvl][0]queinfo[lvl][0]=data[queinfo[lvl][0]][-1]cnt-=1①

whileidx<len(data)andtime+data[cur][2]>=data[idx][1]:iflvl>=data[idx][3]ortime+data[cur][2]==data[idx][1]:insert(idx,data[idx][2])cnt+=1idx+=1eliftime+data[cur][2]>data[idx][1]:insert(idx,data[idx][2])#搶占的進(jìn)程也先入隊(duì)cnt+=1insert(cur,②)

cnt+=1time=data[idx][1]lvl=data[idx][3]idx+=1flag=Truebreakifflag==False:time=time+data[cur][2]print("時(shí)刻",time,":進(jìn)程",data[cur][0],"完成")lvl=mif③:#仍然有未到達(dá)的進(jìn)程等待入隊(duì)

insert(idx,data[idx][2])cnt+=1time=data[idx][1]idx+=1else:lvl-=1iflvl==0:lvl=m(3)若將以上程序中insert函數(shù)內(nèi)的加框處代碼刪除,會(huì)導(dǎo)致某些情況下無(wú)法得到符合程序功能的結(jié)果,下列4組數(shù)據(jù)中能測(cè)試出這一問(wèn)題的是(單選,填字母)。

A.m=3data=[['A',0,1,1],['B',1,1,2],['C',3,1,3]]B.m=3data=[['A',0,2,2],['B',1,2,3],['C',3,1,3]]C.m=3data=[['A',0,2,1],['B',1,2,3],['C',2,1,2]]D.m=3data=[['A',0,2,2],['B',1,2,3],['C',2,1,1]]答案(1)11(2)①flag=True②data[cur][2]-(data[idx][1]-time)③idx<len(data)andcnt==0(3)D9.(2024屆A9協(xié)作體聯(lián)考,15)張三是一名計(jì)算機(jī)專(zhuān)業(yè)的大學(xué)生,為了幫助同學(xué)們學(xué)習(xí)專(zhuān)業(yè)相關(guān)的英語(yǔ)詞匯,編寫(xiě)了一個(gè)簡(jiǎn)易字典程序。該程序中存放詞匯數(shù)據(jù)庫(kù),在學(xué)習(xí)中輸入英文單詞,可以獲得中文翻譯結(jié)果。程序中的詞匯數(shù)據(jù)庫(kù)采用鏈表方式存儲(chǔ),首字母相同時(shí)按升序排序。查找單詞時(shí),首先根據(jù)首字母找到同首字母最小單詞所在鏈表,再按照鏈表順序查找該單詞。(1)根據(jù)題意,部分的單詞庫(kù)數(shù)據(jù)邏輯結(jié)構(gòu)如圖所示,查找單詞"byte"的過(guò)程是"binary"→"bit"→"byte",補(bǔ)充圖中空白單元格的值為。

列表索引數(shù)據(jù)區(qū)域指針區(qū)域0audio音頻-11binary二進(jìn)制數(shù)62byte字節(jié)-13cursor光標(biāo)-14access存取15cache高速緩存36bit比特

(2)wordlist(data,info)函數(shù)實(shí)現(xiàn)將詞匯數(shù)據(jù)庫(kù)data以鏈表的方式按字母序升序排列。info表示詞匯數(shù)據(jù)庫(kù)中各字母開(kāi)頭的最小單詞位置,如info[0]表示字母a開(kāi)頭的最小單詞在詞匯數(shù)據(jù)庫(kù)data中的位置。實(shí)現(xiàn)該功能的程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defwordlist(data,info):n=len(data)foriinrange(n):data[i].append(-1)#data[i]追加一個(gè)元素-1foriinrange(n):d=data[i][0]①

ifinfo[k]==-1:info[k]=ielse:head=info[k]q=headwhile②:

p=qq=data[q][2]ifq!=head:data[p][2]=idata[i][2]=qelse:data[i][2]=head③

returndata,info(3)searchword(data,info,key)函數(shù)實(shí)現(xiàn)單詞的查找。程序如下,請(qǐng)?jiān)趧澗€處填入合適的代碼。defsearchword(data,info,key):k=ord(key[0])-ord("a")head=info[k]p=headwhilep!=-1:ifdata[p][0]==key:return

p=data[p][2]return"沒(méi)有找到該單詞"#讀取詞匯數(shù)據(jù)庫(kù),存入列表data中,列表的每個(gè)元素包含2個(gè)數(shù)據(jù)項(xiàng),分別為英文單詞和中文翻譯,如data=[['audio','音頻'],['binary','二進(jìn)制數(shù)']…],數(shù)據(jù)讀取存入的代碼略info=[-1]*26data,info=wordlist(data,info)key=input("請(qǐng)輸入查找單詞:").lower()#轉(zhuǎn)化為小寫(xiě)字母res=searchword(data,info,key)print(key,"查找結(jié)果是:",res)答案(1)2(2)①k=ord(d[0])-ord('a')②q!=-1andd>data[q][0]③info[k]=i(3)data[p][1]10.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,15)某校針對(duì)高三高考成績(jī)進(jìn)行分析時(shí),其中有兩個(gè)主要指標(biāo):班級(jí)各科平均成績(jī)和班級(jí)總分平均成績(jī)。高考成績(jī)保存在“kscj.csv”文件中,格式如圖a所示,每行有四個(gè)項(xiàng)目,分別是“學(xué)號(hào)”“姓名”“學(xué)科”和“得分”,其中“學(xué)號(hào)”的前兩位表示班級(jí)編號(hào),后兩位表示該學(xué)生班內(nèi)編號(hào),兩種編號(hào)均從“01”遞增編排。設(shè)計(jì)如下Python程序,執(zhí)行后輸出上述兩個(gè)主要指標(biāo),如圖b所示。請(qǐng)回答下列問(wèn)題。(1)通讀下列程序代碼后,可知程序中各班級(jí)隊(duì)列采用的數(shù)據(jù)結(jié)構(gòu)為(選填,數(shù)組/鏈表)。

(2)函數(shù)dataToClassQue功能:根據(jù)班級(jí)編號(hào),將數(shù)據(jù)分配到各個(gè)班級(jí)隊(duì)列。請(qǐng)?jiān)趧澗€處填入合適的代碼。defdataToClassQue(data):num=len(data)foriinrange(num):classId=data[i][0]ifqueInfo[classId-1][0]==-1:queInfo[classId-1][0]=ielse:

queInfo[classId-1][1]=ireturn(3)函數(shù)dataProcessing功能:統(tǒng)計(jì)各班各科平均分和班總分平均分。請(qǐng)?jiān)趧澗€處填入合適的代碼。defdataProcessing(data):forclassIdinrange(1,classNumber+1):①

score=[[0,0]foriinrange(10)]#班級(jí)各科平均分和人數(shù)初始化p=queInfo[classId-1][0]whilep!=-1:subjectId=data[p][3]total+=data[p][4]②

score[subjectId][1]+=1p=data[p][-1]forsubjectIdinrange(10):ifscore[subjectId][1]!=0:t=③

averageScore[classId-1][subjectId]=round(t,1)averageScore[classId-1][10]=round(total/score[0][1],1)returndefreadFile(data):#讀入原始學(xué)生數(shù)據(jù),預(yù)處理后,存儲(chǔ)到data中,代碼略#data數(shù)據(jù)格式:[[6,10,'白凱修',0,117,-1],[6,10,'白凱修',1,109,-1],……]#每條記錄包括班級(jí)編號(hào),班內(nèi)編號(hào),姓名,學(xué)科編號(hào),得分和預(yù)留值-1returnmaxClassId#返回最大班級(jí)編號(hào)deffmtPrint():#格式化輸出,如圖b所示,代碼略return#主程序course={'語(yǔ)文':0,'數(shù)學(xué)':1,'英語(yǔ)':2,'物理':3,'化學(xué)':4,'生物':5,'政治':6,'歷史':7,'地理':8,'技術(shù)':9}data=[]#存儲(chǔ)讀入的數(shù)據(jù)classNumber=readFile(data)queInfo=[[-1,-1]foriinrange(classNumber)]#初始化隊(duì)列,用于存儲(chǔ)各班級(jí)信息averageScore=[[0forkinrange(11)]foriinrange(classNumber)]dataToClassQue(data)dataProcessing(data)fmtPrint()答案(1)鏈表(2)data[queInfo[classId-1][1]]=i(3)①total=0②score[subjectId][0]+=data[p][4]③score[subjectId][0]/score[subjectId][1]11.(2024屆百校起點(diǎn)調(diào)研測(cè)試,15)某醫(yī)院的團(tuán)體體檢流程如下:編號(hào)登記:為n位體檢者設(shè)置體檢編號(hào)1~n。體檢呼叫:體檢項(xiàng)目處空閑時(shí)呼叫下一個(gè)體檢者(編號(hào)小的優(yōu)先),若多個(gè)項(xiàng)目同時(shí)呼叫,體檢者到優(yōu)先級(jí)小的項(xiàng)目處體檢。僅考慮常規(guī)體檢項(xiàng)目,各個(gè)項(xiàng)目的優(yōu)先級(jí)及體檢時(shí)間如圖所示。項(xiàng)目名稱(chēng)B超心電圖抽血尿常規(guī)C14檢測(cè)胸透一般常規(guī)優(yōu)先級(jí)0123456時(shí)間(min)12522221前去體檢:各個(gè)體檢項(xiàng)目之間相互獨(dú)立,互不影響;病人排隊(duì)體檢和體檢完畢到下一科室之間沒(méi)有時(shí)間延遲。(1)某個(gè)團(tuán)隊(duì)4人(分別用編號(hào)1,2,3,4表示)參加體檢,開(kāi)始體檢后第5分鐘,4號(hào)在檢查(填寫(xiě)項(xiàng)目名稱(chēng))項(xiàng)目。

(2)定義如下lst(n)函數(shù),生成n人體檢隊(duì)列。若體檢人數(shù)為4,則que生成結(jié)果如圖所示。隊(duì)列索引號(hào)體檢編號(hào)已檢測(cè)項(xiàng)目01[]12[]23[]34[]deflst(n):que=[]foriinrange(n):temp=[i+1,[]]que.append(temp)returnque若加框處語(yǔ)句改為:foriinrange(1,n+1):temp=[i,[]]則執(zhí)行語(yǔ)句lst(4),que的生成結(jié)果(選填:相同/不同)。

(3)用Python程序模擬一個(gè)10人團(tuán)隊(duì)參加體檢的流程。程序運(yùn)行后,體檢完成順序如圖所示。體檢完成順序:編號(hào)2:心電圖→一般常規(guī)→抽血→尿常規(guī)→C14檢測(cè)→胸透→B超編號(hào)1:B超→抽血→尿常規(guī)→C14檢測(cè)→胸透→一般常規(guī)→心電圖編號(hào)5:C14檢測(cè)→胸透→一般常規(guī)→抽血→尿常規(guī)→B超→心電圖編號(hào)3:抽血→尿常規(guī)→C14檢測(cè)→胸透→一般常規(guī)→心電圖→B超編號(hào)4:尿常規(guī)→C14檢測(cè)→胸透→一般常規(guī)→抽血→心電圖→B超編號(hào)6:胸透→一般常規(guī)→抽血→尿常規(guī)→C14檢測(cè)→心電圖→B超編號(hào)7:一般常規(guī)→抽血→尿常規(guī)→C