資源簡介

中小學(xué)教育資源及組卷應(yīng)用平臺
2025新教材技術(shù)高考第一輪
專題七　數(shù)據(jù)的組織
考點(diǎn)過關(guān)練
考點(diǎn)一　數(shù)組
1.(2022浙北G2聯(lián)盟期中,15)有如下Python 程序段:
import random
a=[]
for i in range(10):
　　　 a.append(random.randint(1,100))
i=0
while i <10:
　　　 if i==0:
　　　　　　i=i+1
　　　 elif a[i-1]<=a[i]:
　　　　　　　　　①　　　
　　　 else:
　　　　　　a[i],a[i-1]=a[i-1],a[i]
　　　　　　　　　②　　　
print(a)
執(zhí)行該程序段實(shí)現(xiàn)了隨機(jī)生成一個數(shù)組,并將其元素遞增輸出的功能。劃線處的代碼應(yīng)該是(　　)
A.① i+=1　② i=1
B.① i-=1　② i=1
C.① i+=1　② i+=1
D.① i-=1　② i-=1
2.(2022紹興諸暨期中,3)使用列表生成的方式創(chuàng)建數(shù)組代碼如下:
a=[i*i-1 for i in range(10) if i%2==0]
則數(shù)組元素a[3]的值為(　　)
A.2　　　B. 8　　　C. 15　　　D. 35
3.(2022紹興諸暨期中,4)設(shè)有一個5×8的二維數(shù)組a,若按行優(yōu)先的順序存儲數(shù)組元素,則元素a[3][5]前面元素的個數(shù)為(　　)
A.21　　　B. 22　　　C. 29　　　D. 37
4.(2022紹興諸暨期中,13)有如下Python程序段:
a=[[0 for i in range(3)]for j in range(3)]
for i in range(3):
　for j in range(3):
　　a[i][j]=i*5+j+1
for i in range(1,3):
　for j in range(2):
　　print(a[j][i],end=" ")
程序段執(zhí)行后,輸出的結(jié)果是(　　)
A.2 3 7 8　　　　B.7 12 8 13
C.2 7 3 8　　　　D.6 7 11 12
5.(2022杭州期中,10)下述代碼段用于實(shí)現(xiàn)在數(shù)組a中將新數(shù)據(jù)k插入下標(biāo)為 j(0<=j<=8)的位置:
a=[8,6,12,3,5,7,11,2,10,0]
i=8
while i>=j:
　　　　(1)　　
　　　　(2)　　
　　(3)　　
橫線處的代碼由以下五部分中的三部分組成:
①a[i+1]=k　②a[i]=k　③a[i+1]=a[i]
④a[i]=a[i-1]　⑤i=i-1
下列選項(xiàng)中代碼選擇與順序正確的是(　　)
A.③⑤②　　　B.⑤③①　　　C.③⑤①　　　D.④⑤②
6.(2022嘉興期中,3)用 Python 程序段定義一個3行4列的二維數(shù)組(要求先將各元素的值初始化為0,再將第2行第 2 個元素重新賦值為1),以下程序段可行的是(　　)
A. arr=[[0]*3 for j in range(4)]
arr[2][2]=1
B.arr=[[0]*4]*3
arr[1][1]=1
C.arr=[[0 for i in range(4)]for j in range(3)]
arr[1][1]=1
D.arr=[[0,0,0,0]for j in range(3)]
arr[2][2]=1
考點(diǎn)二　鏈表
1.(2022浙南名校聯(lián)盟期末,12)一個頭指針 head=2 的單向鏈表 L=[[30,4], [10,-1], [20,0], [15,1],[21,3]]通過以下 Python 程序段,轉(zhuǎn)換為原鏈表的逆序鏈表,即頭指針 head=1,L=[[30,2], [10,3], [20,-1], [15,4],[21,0]]。
　q=-1
　p=head　#head 為原鏈表頭指針
　while p!=-1 :
　　tmp=L[p][1]
　　
　head=q
上述程序段中方框處可選的語句為:
①p=tmp　②q=p　③L[p][1]=q
則方框處語句依次為(　　)
A.③②①　　　B.③①②　　　C.①③②　　　D.①②③
2.(2022浙北G2聯(lián)盟期中,14)用兩個列表a、b分別保存單向鏈表中的數(shù)據(jù)區(qū)域和指針區(qū)域。如圖所示,在節(jié)點(diǎn)x與節(jié)點(diǎn)y之間插入一個新節(jié)點(diǎn),操作步驟正確的是(　　)
①b[i]=b[y]　　　　　②b[i]=b[x]
③b[y]=i　　　　④b[x]=i
⑤b[i]=x　　　　⑥b[i]=y
A.③⑥　　　B.④②　　　C.①③　　　D.②④
3.(2023浙江開學(xué)考,10)已知一個鏈表a,其a[i][0]存儲索引i下節(jié)點(diǎn)的數(shù)據(jù)區(qū)域,a[i][1]存儲索引i下節(jié)點(diǎn)的指針區(qū)域。對于當(dāng)前鏈表中的一個節(jié)點(diǎn)p(索引為p),若要刪除p的后一個節(jié)點(diǎn)q(q=a[p][1]),則應(yīng)執(zhí)行語句(　　)
A.a[p]=a[q]
B.a[p][1]=a[q][1]
C.a[p]=a[a[q][1]]
D.a[p]=a[q];a[p][1]=a[q][1]
4.(2022杭州期中,12)在Python中用列表模擬鏈表結(jié)構(gòu),某程序段如下:
a=[['H',1],['a',2],['n',3],['g',4],['2',5],['0',6],['2',7],['2',0]]
p, head=3,3;q,c=-1,0;m,n=3,0
while n<4:
　　c=c+1
　　if c==m:
　　　　n=n+1;c=0
　　　　if p==head:
head=a[p][1]
a[q][1]=head
p=a[p][1]
　　　　else:
　a[q][1]=a[p][1]
　p=a[p][1]
　　else:
q=p
p=a[p][1]
#從頭節(jié)點(diǎn)開始遍歷鏈表a邏輯順序的所有節(jié)點(diǎn),并依次輸出節(jié)點(diǎn)的數(shù)據(jù),代碼略
該程序段執(zhí)行后的輸出結(jié)果為(　　)
A.ng02　　　B.g02n　　　C.2an2　　　D.22an
5.(2022諸暨期末,8)某單向鏈表如圖所示,在data2與data3之間插入一個新節(jié)點(diǎn)data4(p指向data2,r指向data4。列表data來記錄鏈表數(shù)據(jù)域,列表next來記錄指針域),以下選項(xiàng)中正確的執(zhí)行步驟為(　　)
①next[p]=next[r]　　　　②next[p]=r
③next[r]=p　　　　④next[r]=-1
⑤next[r]=next[p]　　　　⑥next[p]=-1
A.③⑥　　　B.⑤②　　　C.①④　　　D.⑤②④
6.(2022杭嘉湖金月考,15)山頂上有10個圓形排列的洞,一只狐貍和一只兔子各住一個洞。狐貍總想吃掉兔子。一天兔子對狐貍說:“你想吃我有一個條件,先把洞從1~10編上號,你先到1號洞找我;第二次隔1個洞(即3號洞)找我,第三次隔2個洞(即6號洞)找我,依此類推,次數(shù)不限。但狐貍從早到晚進(jìn)進(jìn)出出了1000次,仍沒有找到兔子。請問兔子可能躲在哪個洞里
實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
hole=[]
n=10
m=1000
#構(gòu)造一個循環(huán)鏈表,并給n個洞編號,設(shè)置洞的初始標(biāo)志為0
#鏈表的節(jié)點(diǎn)樣式為:[洞的標(biāo)志,洞的編號]
for i in range(n-1):
　　hole.append([0,i+1])
　　　　　(1)　　　　　
#狐貍開始找兔子,將進(jìn)入過的洞標(biāo)志改為1,尋找m次結(jié)束
head=0
k=head
hole[0][0]=1
for i in range(1,m):
　　for j in range(1,i+2):
　　　　　　　　(2)　　　　　
　　hole[k][0]=1
#輸出標(biāo)志仍為0的洞,即兔子可能的藏身地點(diǎn)
for i in range (len(hole)):
　　if hole[i][0]==0:
　　　　print("兔子可能躲在第"+　(3)　+"號洞")
考點(diǎn)三　隊(duì)列
1.(2024屆七彩聯(lián)盟聯(lián)考,11)有如下程序段:
s=input()
head=0;tail=0;ans=0;tmp=' '
q=[' ']*100
flag=True
for i in range(len(s)):
　if s[i]==',':
　　while head!=tail:
　　　tmp+=q[head]
head+=1
if flag and head　head+=1
flag=not flag
　　ans+=int(tmp)
　　tmp=' ';flag=True
　elif '0'<=s[i]<='9':
　　q[tail]=s[i]
　　tail+=1
輸入s為"1-500,2023900-,",執(zhí)行該程序段,變量ans的值為(　　)
A.100　　　B.22300　　　C.22351　　　D.22400
2.(2022杭州“六縣九校”期中,5)有A、B、C、D、E五個人依次進(jìn)入電梯,結(jié)果警告超重了,需要出去一個人才能正常運(yùn)行,按照數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的思維,應(yīng)離開電梯的人分別是(　　)
A.棧:A　隊(duì)列:E　　　　B.棧:A　隊(duì)列:A
C.棧:E　隊(duì)列:A　　　　D.棧:E　隊(duì)列:E
3.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,9)執(zhí)行下列Python程序段,輸出結(jié)果為(　　)
data=[1,2,3,1,2,3]
que=[0]*10
head=tail=0
for i in range(len(data)):
if data[i]%2 !=0:
　　que[tail]=data[i]
　　tail+=1
elif tail-head>1:
　　que[tail-1]+=que[head]
　　head+=l
print(que[head:tail])
A.[3,2,1]　　　　B.[1,2,3]
C.[1,3,1]　　　　D.[3,2,3]
4.(2024屆新陣地聯(lián)盟第二次聯(lián)考,11)有如下程序段:
m=3;n=7
head=tail=0;ans=0
vis=[0]*10;q=[0]*10
for i in range(n):
x=int(input())
if(vis[x]=0):
　ans+=1
　if(tail-head>=m):
　　vis[q[head]]=0
　　head+=1
　q[tail]=x
　tail+=1
　vis[x]=1
print(ans)
運(yùn)行該程序段,依次輸入x的值:1,2,1,5,4,4,1。則程序運(yùn)行完成后ans 的值是(　　)
A.3　　　B.4　　　C.5　　　D.6
5. (2024屆天域全國名校協(xié)作體聯(lián)考,12)已知列表a的長度為6,a[0]至a[5]的值依次為18,12,24,15,21,0,某程序如下所示:
head, tail=0,5
x=a[head]
head+=1
while (head+1) % len(a) !=tail:
　　 t=y=a[head]
head=(head+1) % len(a)
if x　 x,y=y,x
if x % y !=0:
　 a[tail]=x % y
　 tail=(tail+1) % len(a)
x=t
print(a[head])
程序運(yùn)行后,輸出的結(jié)果是(　　)
A.24　　　　B.12　　　
C.3　　　　D.0
6.(2023“山水聯(lián)盟”開學(xué)考,11)有如下Python程序代碼:
s="ABCDEF"; head=0;tail=0
que=[" "]*100
for i in range(len(s)):
if i%2==0:
　que[tail]=s[i]
else:
　que[tail]=s[len(s)-i]
tail=tail+1
for i in range(len(s)):
print(que[head], end=" ")
head=head+1
以上程序運(yùn)行后,輸出列表的情況是(　　)
A.ABCDEF　　　　B.FEDCBA
C.ACEFDB　　　　D.AFCDEB
考點(diǎn)四　棧
1.(2022浙南名校聯(lián)盟期末,10)一個棧的入棧序列為“6、9、5、7、8、3”,其出棧序列不可能是(　　)
A.3、8、7、5、9、6
B.7、5、9、8、6、3
C.6、5、7、9、3、8
D.5、9、6、3、7、8
2.(2024屆百校起點(diǎn)調(diào)研測試,9)棧q初始有三個值,經(jīng)過一系列入棧、出棧操作后,棧為空,若元素出棧的順序是1,2,3,4,5,6,7,則棧q初始的情況可能是(　　)
A.[1,2,3]　　　　B.[7,5,6]
C.[6,3,1]　　　　D.[4,7,2]
3.(2024屆Z20聯(lián)盟聯(lián)考,9)若元素入棧的順序是1,2,3,4,5,6,不允許連續(xù)三次入棧,則可能的出棧序列為(　　)
A.2,3,5,1,6,4　　　　B.1,2,3,6,5,4
C.2,4,3,1,6,5　　　　D.2,5,4,6,3,1
4.(2024屆七彩聯(lián)盟聯(lián)考,9)假設(shè)棧S的最大長度為3,其初始狀態(tài)和終止?fàn)顟B(tài)均為空,經(jīng)過一系列入棧和出棧的操作,若元素最后的出棧序列為F,E,D,C,B,A,則可能的入棧順序?yàn)?　　)
A.ABCDEF　　　　B.ACDFEB
C.BEFACD　　　　D.BFDECA
5.(2024屆嘉興基測,12)待入棧的序列a有多種出棧序列,以下函數(shù)用于判斷序列b是不是a的出棧序列,代碼如下:
def judge(a,b):
n=len(a);st=[-1]*n
top=-1;i=j=0
while i　top+=1
　　　①　　
　i+=1
　while top>-1 and 　　②　　:
　　top-=1
　　j+=1
return top==-1
from random import shuffle
a=[1,2,3,4,5]
b=[1,2,3,4,5]
shuffle(b)　　#將序列b的元素隨機(jī)排序
if judge(a,b):
　　print(b,'是', a,'的出棧序列')
else:
　　print(b,'不是',a,'的出棧序列')
程序運(yùn)行結(jié)果如圖所示。劃線處應(yīng)填寫的語句是(　　)
python 12.py
[2,5,4,3,1]是[1,2,3,4,5]的出棧序列
python 12.py
[5,2,3,1,4]不是[1,2,3,4,5]的出棧序列
A.①st[top]=a[i]　②st[top]==b[j]
B.①st[top]=a[i]　②st[-1]==b[j]
C.①st[top]=b[i]　②st[top]==a[j]
D.①st[top]=b[i]　②st[-1]==a[j]
6.(2022 Z20名校聯(lián)盟,10)某算法利用“棧”思想進(jìn)行字符串處理,其步驟如下:①創(chuàng)建長度為n的空棧,字符依次入棧;②當(dāng)達(dá)到棧滿狀態(tài)或數(shù)據(jù)全部入棧時,字符依次出棧,按照出棧順序連接成新字符串:③若還有未處理的字符,則重復(fù)步驟①②,直到全部字符處理完畢。實(shí)現(xiàn)該功能的 Python程序如下:
s=input("請輸入字符串:")
n=5;st=[" "]*n
top=-1;i=0;m=" "
while i　while 　(1)　 and i　　　(2)　
　　st[top]=s[i]
　　i+=1
　while top!=-1:
　　m+=st[top]
　　　(3)　
print("密文:" ,m)
加框處(1)(2)(3)的代碼由以下代碼組成:
①top-=1　②top+=1　③top+1④top下列選項(xiàng)中代碼順序正確的是(　　)
A.④②①　　　　B.③①②
C.③②①　　　　D.④①②
7.(2022諸暨海亮高中月考,10)有如下程序段:
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i　　if i < len(bt) and bt[i] is not None:
　　　　stack.append(i)
　　　　i=2*i+1
　　else:
　　　　i=stack.pop()
　　　　result.append(bt[i])
　　　　i=2*i+2
print("-".join(result))
則程序運(yùn)行后輸出的結(jié)果為(　　)
A.A-B-D-C-E-F　　　　
B.D-B-E-F-C-A
C.D-B-A-E-C-F　　　　
D.A-B-C-D-E-F
考點(diǎn)五　樹
1.(2024屆Z20聯(lián)盟聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其后序遍歷結(jié)果為“物技化數(shù)英語”,則中序遍歷結(jié)果為(　　)
A.語數(shù)英物化技　　　　B.物數(shù)技化語英
C.語數(shù)物化技英　　　　D.化物技英數(shù)語
2.(2022名校協(xié)作體,10)已知二叉樹T2的后序遍歷序列為G-D-H-E-B-I-F-C-A,中序遍歷序列為D-G-B-E-H-A-C-I-F,則二叉樹T2的前序遍歷序列為(　　)
A.A-B-D-G-E-H-C-I-F
B.A-B-D-G-E-H-C-F-I
C.A-B-D-G-E-H-F-C-I
D.該二叉樹形態(tài)不唯一,無法確定
3.(2024屆新陣地聯(lián)盟第二次聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其后序遍歷結(jié)果為FABGDEC,則中序遍歷結(jié)果為(　　)
A.FDAGBCE　　　　B.FDABGEC
C.AGBDFCE　　　　D.FDAGBEC
4.(2024屆天域全國名校協(xié)作體聯(lián)考,8)下列二叉樹中,后序遍歷結(jié)果不為CBFEAD的是(　　)
　　
　　
5.(2024屆七彩聯(lián)盟聯(lián)考,8)某二叉樹用一維數(shù)組表示(見表)。該二叉樹從根節(jié)點(diǎn)開始,按照從上到下,從左到右的順序依次用A-H字母表示,該二叉樹的中序遍歷為(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H
A.DBGEACFH　　　　B.DBGEACHF
C.DBEGACHF　　　　D.ABCDEFGH
考點(diǎn)六　大數(shù)據(jù)時代的數(shù)據(jù)的組織
1.下列關(guān)于實(shí)時查詢數(shù)據(jù)系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)的說法,不正確的是(　　)
A.在實(shí)時查詢系統(tǒng)中使用數(shù)組,時效性較差
B.在鏈表中查找數(shù)據(jù)時效性較高,插入數(shù)據(jù)時效性較低
C.跳躍表基于有序鏈表
D.跳躍表通過跨區(qū)間、跳躍性的比較,避免了依次比較,提高了效率
2.有如下跳躍表:
若要在原鏈表中插入元素7,則數(shù)據(jù)元素需要比較的次數(shù)為(　　)
A.1　　　B.3　　　C.4　　　D.5
3.下列關(guān)于Hadoop的說法,不正確的是(　　)
A.Hadoop是一種超大規(guī)模,高可靠性,高可擴(kuò)展性的數(shù)據(jù)庫
B.Hadoop是Google云計算技術(shù)的開源實(shí)現(xiàn)
C.使用Hadoop可以在POI數(shù)據(jù)的處理中獲得更方便的體驗(yàn)和更低廉的成本
D.Hadoop可以對海量地理信息進(jìn)行處理和計算
專題綜合練
題組一
1.(2024屆名校協(xié)作體聯(lián)考,8)某二叉樹的前序遍歷結(jié)果為GFDECAB,中序遍歷結(jié)果為DFGCAEB。關(guān)于該二叉樹,以下說法正確的是(　　)
A.該二叉樹的后序遍歷為ADFCBEG
B.該二叉樹的深度為4,節(jié)點(diǎn)C在第3層
C.該二叉樹的葉子節(jié)點(diǎn)數(shù)比非葉子節(jié)點(diǎn)數(shù)多一個
D.該二叉樹可以通過添加3個節(jié)點(diǎn)后變?yōu)橥耆鏄?br/>2.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其后序遍歷結(jié)果為FBCEAD,則前序遍歷結(jié)果為(　　)
A.ABCDEF　　　　B.FEDCBA
C.DFACBE　　　　D.FDBCAE
3.(2024屆強(qiáng)基聯(lián)盟統(tǒng)測,8)已知某二叉樹的后序遍歷為GDBEHFCA,中序遍歷為DGBAECHF,下列說法正確的是(　　)
A.該二叉樹中葉子節(jié)點(diǎn)有3個
B.該二叉樹的前序遍歷為ABDGCEHF
C.該二叉樹是一棵完全二叉樹,樹的高度為4
D.該二叉樹中度為1的節(jié)點(diǎn)有2個
4.(2024屆新陣地聯(lián)盟第二次聯(lián)考,9)棧S初始狀態(tài)為空棧,將序列3,2,5,7,1中元素逐一入棧,當(dāng)棧空或入棧元素比棧頂元素大時則入棧,否則出棧至符合條件再入棧。序列所有元素入棧完畢后,棧內(nèi)剩余元素出棧,直至棧空。則出棧的順序是(　　)
A.17523　　　　B.37521
C.37512　　　　D.32751
5.(2024屆天域全國名校協(xié)作體聯(lián)考,9)利用棧求逆波蘭表達(dá)式(表達(dá)式由操作數(shù)和運(yùn)算符組成)的方法是:從左往右掃描該表達(dá)式,遇到操作數(shù)時入棧;遇到運(yùn)算符時,把處于棧上方的兩個元素依次出棧,用運(yùn)算符計算,并把計算結(jié)果壓入棧中。如此反復(fù)操作,直至表達(dá)式掃描結(jié)束。當(dāng)用該算法求逆波蘭表達(dá)式abcd-*e/+f-的值時(abcdef表示不同的操作數(shù)),所使用的棧的深度至少為(　　)
A.3　　　B.4　　　C.5　　　D.6
6.(2024屆嘉興基測,11)長度為5的循環(huán)隊(duì)列que,que[0]至que[4]的值依次為'a','b','c','d','e',執(zhí)行如下程序段后,輸出的最后一個字符為　(　　)
n=5;head=0;tail=4
que=['a','b','c','d','e']
while head!=tail:
　　if head%4==0:
　　　print(que[head])
　　else:
　　　tail=(tai1+1)%n
　　　que[tail]=que[head]
　　head=(head+1)%n
print(que[head])
A.b　　　B.c　　　C.d　　　D.e
7.(2024屆發(fā)展共同體聯(lián)考,9)某種特殊的隊(duì)列Q,支持以下三個操作:
操作Q1:若隊(duì)列非空,隊(duì)首元素出隊(duì),并輸出;
操作Q2:若隊(duì)列非空,隊(duì)首元素出隊(duì);
操作Q3:一個元素入隊(duì)。
以上任意一種操作后,若隊(duì)列非空,新的隊(duì)首元素仍為隊(duì)列中所有元素的最小值。
若隊(duì)列Q初始狀態(tài)為空,依次進(jìn)行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后,下列說法正確的是(　　)
A.當(dāng)前隊(duì)列中的元素個數(shù)為2
B.輸出的元素個數(shù)為2
C.第一個輸出的元素肯定比當(dāng)前隊(duì)首元素大
D.隊(duì)列初始狀態(tài)是不是空對輸出結(jié)果有影響
8.(2024浙江1月選考,8,2分)棧S從棧底到棧頂?shù)脑匾来螢?,2,3,隊(duì)列Q 初始為空。約定:U 操作是指元素出棧后入隊(duì),H 操作是指元素出隊(duì)后再入隊(duì)。經(jīng)過UUHU系列操作后,隊(duì)列中隊(duì)首到隊(duì)尾的元素依次為(　　)
A.2,1,3　　　B.3,1,2　　　C.1,3,2　　　D.2,3,1
9.(2024浙江1月選考,9,2分)數(shù)組元素a[0]至a[n-1]依次存放著n個數(shù)據(jù),現(xiàn)需要將元素a[n-1]插入在下標(biāo)為x(0≤xtemp=a[n-1]
for i in range(n-2,x-1,-1):
　　　　　　　　
a[x]=temp
A.a[i+1]=a[i]　　　　B.a[i-1]=a[i]
C.a[i]=a[i+1]　　　　D.a[i]=a[i-1]
10.(2024屆發(fā)展共同體聯(lián)考,11)有如下程序段:
s=[' ']*len(a)
head=2;q=head;top=-1
while q!=-1:
　　top+=1
　　s[top]=a[q][0]
　　q=a[q][1]
print(s[top-2])
若a=[['a',3],['b',0],['c',1],['d',-1]],則輸出的結(jié)果為(　　)
A.a　　　B.b　　　C.c　　　D.d
11.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,11)有如下Python程序段:
s=input()
stack=[0]* len(s);top=-1;presign='+';num=0
for i in range(len(s)):
if '0'<=s[i]<='9':
　　num=num*10+int(s[i])
if i==len(s)-1 or s[i] in '+-*/':
　　if presign=='+':
　　　　top+=1
　　　　stack[top]=num
　　elif presign=='-':
　　　　top+=1
　　　　stack[top]=-num
　　elif presign=='*':
　　　　top+=1
　　　　stack[top]=stack[top-1]*num
　　else:
　　　　top+=1
　　　　stack[top]=stack[top-1]
//num
　　presign=s[i]
　　num=0
print(sum(stack))　　#sum函數(shù)對stack中所有元素求和
若輸入'5*4-6+10/3',程序運(yùn)行后,輸出的結(jié)果是(　　)
A.32　　　B.24　　　C.17　　　D.8
12.(2023浙江1月選考,15,9分)有2組器件共n個,要用一臺檢測設(shè)備檢測。每個送檢器件的信息包含送達(dá)時間、檢測時長和優(yōu)先級。優(yōu)先級有m(1編寫程序模擬檢測過程,先合并2組器件的數(shù)據(jù),然后計算所有器件的平均等待時長,其中每個器件等待時長為其開始檢測時間與送達(dá)時間的時間差。(時間單位均為秒)
請回答下列問題:
(1)由題意可知,圖中器件A、B、C、D的檢測順序?yàn)锳—C—D—B,A、C、D的等待時長分別為0、1、0,B的等待時長是　　　　。
送達(dá)時間 檢測時長 優(yōu)先級
A 0 3 2
B 1 1 2
C 2 1 1
D 4 3 0
11 3 2
12 2 2
(2)定義如下merge(lst1, lst2)函數(shù),參數(shù) lst1和 lst2的每個元素由送達(dá)時間、檢測時長和優(yōu)先級3項(xiàng)構(gòu)成,lst1和 lst2均已按送達(dá)時間升序排列。函數(shù)功能是將lst2中的元素合并到lst1中,并將 lst1按送達(dá)時間升序排列,函數(shù)返回lst1。
def merge(lst1,lst2):
　　i=len(lst1)-1
　　j=len(lst2)-1
　　for t in range(len(lst2)):
　　　lst1.append([0,0,0])　　#為lst1追加一個元素[0,0,0]
　　k=len(lst1) -1
while j >=0:
　　　if i >=0 and lst1[i][0]>lst2[j][0]:
　 lst1[k]=lst1[i]
i -=1
　　　else:
lst1[k]=lst2[j]
j -=1
　　　k -=1
　return lst1
①調(diào)用merge(lst1,lst2)函數(shù),若lst1為[[0,3,2],[1,1,2],[12,2,2]],lst2為[[2,1,1],[4,3,0], [11,3,2]],則while語句中循環(huán)體的執(zhí)行次數(shù)是　　　　。
②若函數(shù)中 while語句的條件“j>=0”誤寫為“k>=0”,會導(dǎo)致某些情況下無法得到符合函數(shù)功能的結(jié)果。調(diào)用merge(lst1, lst2)函數(shù),下列4組數(shù)據(jù)中能測試出這一問題的是　　　　(單選,填字母)。
A.lst1=[[0,3,2],[4,3,0]]
lst2=[[1,1,2]]
B.lst1=[[1,1,2]]
lst2=[[0,3,2],[4,3,0]]
C.lst1=[[1,1,2],[4,3,0]]
lst2=[[0,3,2]]
D.lst1=[[4,3,0]]
lst2=[[0,3,2],[1,1,2]]
(3)實(shí)現(xiàn)模擬檢測過程并計算平均等待時長的部分Python程序如下,請在劃線處填入合適的代碼。
def proc(data,m):
　　n=len(data)
　　queinfo=[]
　　for i in range(m):
　　　queinfo.append([-1, -1])
# queinfo追加一個元素[-1,-1]
　　for i in range(n):
data[i].append(-1)　　# data[i]追加一個元素-1
　　curtime=0
waitnum=0
i=0
　　①　　
while i < n or waitnum > 0:
　 if i < n and data[i][0] <=
curtime:
　　　k=data[i][2]
　　　if queinfo[k][0]==-1:
　　　　　queinfo[k][0]=i
　　　else:
　　　　　　　②　　
　　　　　data[p][3]=i
　　　queinfo[k][1]=i
　　　waitnum+=1
　　　i+=1
　　elif waitnum >0:
k=0
while queinfo[k][0]==-1:
　　k+=1
p=queinfo[k][0]
total+=curtime-data[p][0]
curtime+=data[p][1]
　　③　　
waitnum -=1
　　else:
　　　 curtime=data[i][0]
return total / n
'''
讀取2組器件的數(shù)據(jù),分別存入列表data1和 data2中。2個列表的每個元素包含3個數(shù)據(jù)項(xiàng),分別對應(yīng)器件的送達(dá)時間、檢測時長和優(yōu)先級。data1和 data2中的數(shù)據(jù)已分別按送達(dá)時間升序排列,代碼略
讀取優(yōu)先級等級個數(shù)存入m,代碼略
'''
data=merge(data1, data2)
print(proc(data, m))
13.(2023浙江6月選考,15,9分)某工程包含n個任務(wù)(編號為0~n-1),每天可以有多個任務(wù)同時進(jìn)行。某些任務(wù)之間有依賴關(guān)系,如圖a所示,任務(wù)4依賴于任務(wù)1,任務(wù)1依賴于任務(wù)2。即任務(wù)2完成后才可以開始任務(wù)1,任務(wù)1完成后才可以開始任務(wù)4。不存在一個任務(wù)依賴于多個任務(wù),或多個任務(wù)依賴于同一個任務(wù)的情況。
現(xiàn)已對該工程的依賴關(guān)系進(jìn)行了梳理,結(jié)果如圖b所示,標(biāo)記“T”表示依賴關(guān)系需保留,標(biāo)記“F”表示依賴關(guān)系需刪除。
根據(jù)每個任務(wù)完成所需的天數(shù)和梳理后的依賴關(guān)系,編寫程序,首先刪除標(biāo)記為“F”的依賴關(guān)系,然后計算工程最快完成所需的天數(shù),并以工程最快完成所需的天數(shù)為期限,計算每個任務(wù)最晚必須開始的時間。
任務(wù)A 任務(wù)B 標(biāo)記
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任務(wù)A依賴于任務(wù)B
圖b
請回答下列問題:
(1)若某工程有6個任務(wù),任務(wù)間依賴關(guān)系如圖a所示,完成任務(wù)0~5所需天數(shù)分別為2,1,3,5,1,6,則工程最快完成需要　　天。
(2)定義如下erase(lst)函數(shù),參數(shù) lst列表的每個元素表示一個依賴關(guān)系。函數(shù)的功能是刪除標(biāo)記為“F”的依賴關(guān)系,返回保留的依賴關(guān)系的個數(shù)。
def erase(lst):
　　i=0
　　j=len(lst)-1
　　while i<=j:
　　　　if lst[i][2]=='T':
　　　　　　i+=1
　　　　else:
　　　　　　if lst[j][2]=='T':
lst[i]=lst[j]
i+=1
　　　　　　j-=1
　　return i
若lst列表依次存儲圖b所示的依賴關(guān)系,如 lst[0]為[0,5,'T'],調(diào)用erase(lst)函數(shù),則語句“l(fā)st[i]=lst[j]”的執(zhí)行次數(shù)為　　。
(3)實(shí)現(xiàn)上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
def proc(n,lst,task):
pr=[0]*n
w=[0]* n　　# w[i]存放任務(wù)最晚必須開始的時間
m=erase(lst)
for i in 　　①　　:
task[lst[i][1]][1]=lst[i][0]
pr[lst[i][0]]=1
c=[]
days=0　　# days存放工程最快完成所需的天數(shù)
for i in range(n):
if pr[i]==0:
　　k=i
　　s=0
　　while k!=-1:
　　　　c.append(k)
　　　　s+=task[k][0]
　　　　　　②　　
　　if s > days:
　　　　days=s
for i in range(n-1,-1,-1):
k=c[i]
if task[k][1]==-1:
　　w[k]=days-task[k][0]+1
else:
　　　　③　　
#輸出days,以及保存在w中的每個任務(wù)最晚必須開始的時間,代碼略
"'
工程包含的任務(wù)數(shù)存入變量n
任務(wù)間的依賴關(guān)系存入lst列表
lst[0]包含3項(xiàng),任務(wù)lst[i][0]依賴于任務(wù)lst[i][1],lst[i][2]存放保留/刪除標(biāo)記,任務(wù)數(shù)據(jù)存入task列表
task[i]包含2項(xiàng),task[i][0]為完成任務(wù)所需天數(shù),task[i][1]的初值為-1
代碼略
"'
proc(n,lst,task)
14.(2024屆Z20聯(lián)盟聯(lián)考,15)小明同學(xué)去看病,當(dāng)他在一位醫(yī)生的診室門口等待就診的時候,發(fā)現(xiàn)了叫號系統(tǒng)的頁面上有兩行病人名單。第一行名單為正常排隊(duì)等待就診的序號,第二行名單為過號或檢后再診而等待的序號。叫號的規(guī)則是先在第一行叫2個就診序號,再到第二行叫1個就診序號。小明同學(xué)回家后將剛才發(fā)現(xiàn)的叫號規(guī)則編寫了Python程序。效果如圖所示:
圖①:當(dāng)前到來的就診序號是3號,為過號或檢后再診序號,進(jìn)入第二行,先到達(dá)先就診。
圖②:當(dāng)前到來的就診序號是4號,為過號或檢后再診序號,進(jìn)入第二行。
圖③:當(dāng)前到來的就診序號是16號,為正常排隊(duì)等待就診的序號,進(jìn)入第一行,按就診序號順序排列。
圖④:開始叫號,按照正常排隊(duì)等待就診叫號2位,過號或檢后再診叫號1位,得到新的順序。
(1)請在劃線處填入合適的代碼。
(2)加框處的代碼有誤,請改正。
def output(head, a, b):
p=head
head_b=0; tail_b=len(b)
while p!=-1:
　　print(a[p][0], end="->")
　　p=a[p][1]
print()
while head_b!=tail_b:
　　print(b[head_b], end="->")
　　head_b+=1
print()
def insert(data,a,b):　　#根據(jù)掛號的序號分別進(jìn)入第一行名單或第二行名單
　 head_a=a[0][0]
　 if data>　　①　　:
　　　p=0
　　　a.append([data,-1])
　　　while p!=-1:
　　　　　if data<=a[p][0]:
　　　　　　　a[-1][1]=p
　　　　　　　a[q][1]=len(a)-1
　　　　　　　break
　　　　　else:
　　　　　　　q=p
　　　　　　　p=　　②　　
　　　if p==-1:
　　　　　a[q][1]=　　③　　
　　　output(0,a,b)
　 else:
　　　b.append(data)
　　　output(0,a,b)
#a、b賦初值,代碼略
#如圖①所示:a=[[13,1],[15,2],[17,-1]];b=[3]
while True:
　　data=int(input("請輸入取號:"))
#輸入0表示停止取號,開始叫號
　　if data==0:
　　　break
　　insert(data,a,b)
print("====開始叫號====")
p=head=0
head_b=0;tail_b=len(b)
while p!=-1 or head_b!=tail_b:
　　if p!=-1 and head_b!=tail_b:
　　　 i=0
　　　 while a[p][1]!=-1:
　　　　　print(a[p][0], end="->")
　　　　　p=a[p][1]
　　　　　i+=1
　　　 print(　　④　　, end="->")
　　　 head_b+=1
　　elif p!=-1 and head_b==tail_b:
　　　 print(a[p][0], end="->")
　　　 p=a[p][1]
　　else:
　　　 print(b[head_b], end="->")
　　　 head_b+=1
15.(2022山水聯(lián)盟開學(xué)考,15)小趙同學(xué)在某游戲平臺中獲得虛擬的食物、裝備、材料等物品,它們分別有不同的價值,現(xiàn)游戲平臺有兌換機(jī)制,即可用多個不同物品換取一個等值的物品(每個物品只能取一樣),下表為小趙同學(xué)已獲得的物品。
序號 物品名稱 數(shù)量 單價
0 靈丹 2 1
1 大力丸 1 2
2 止血草 3 5
3 忘魂花 1 7
4 雄黃 1 9
5 靈山仙芝 5 10
6 梅花鏢 1 15
7 止血草 1 20
目標(biāo)置換物品的價值:35。
已獲得物品價值依次是:1,2,5,7,9,10,15,20。
依次拿取物品序號的方案有:
取序號為[0,1,2,3,7]的物品;
取序號為[0,1,3,5,6]的物品;
取序號為[0,2,4,7]的物品;
取序號為[0,4,5,6]的物品;
取序號為[2,5,7]的物品;
取序號為[6,7]的物品。
如要換取游戲中的物品“破天錘”,需要35個金幣,有多種置換的方式,為方便計算以節(jié)省時間,小趙同學(xué)編寫了如下程序,運(yùn)行界面和代碼如下,請在劃線處填入合適的代碼。
def exchange(t,pricelist):
　　n=len(pricelist)
　　stack=[]
　　i=0
　　num=0
　　while　　　①　　　:
　　　　while t>0 and i　　　　　　if t>=int(pricelist[i]):
stack.append(i)
　　②　　
　　　　　　i+=1
　　　　　　if t==0:
　　　　　　　print("取序號為",stack,"的物品")
num+=1
　　　　if 　　　③　　　:
　　　　　　i=stack.pop()
　　　　　　t+=int(pricelist[i])
　　　　　　④　　　
　　if num==0:
　　　　print("無方案")
m=int(input("目標(biāo)置換物品的價值:"))
price=input("已獲得物品價值依次是:")
p=price.split(",")　#將輸入的內(nèi)容以“,”作分隔,并轉(zhuǎn)換為列表
print("依次拿取物品序號的方案有:")
exchange(m, p)
16.(2022名校協(xié)作體聯(lián)考,15)某校軍訓(xùn),需要按照身高由低到高排成n行5列的方陣。某班學(xué)生按照身高(100≤身高<199)由低到高編寫編號并將相關(guān)信息存在圖1所示的“stu.txt”文件中。根據(jù)教官提出的排方陣要求,排成如圖2所示的方陣,方陣各點(diǎn)顯示學(xué)生編號。
　
現(xiàn)有延遲報到學(xué)生歸隊(duì),歸隊(duì)學(xué)生編號延續(xù)該班現(xiàn)有編號依次往后,編寫程序完成下列任務(wù):輸入學(xué)生身高,輸出新的方陣布局圖。例如:輸入學(xué)生身高為168,新的方陣布局圖如圖3所示,學(xué)生在方陣的位置:3,4。
(1)若插入學(xué)生身高為160 cm,根據(jù)圖1及范例,該學(xué)生應(yīng)該在圖2方陣中的　　　行　　　　列。
(2)為實(shí)現(xiàn)上述功能,請?zhí)顚憚澗€處代碼。
f=open("stu.txt","r")
a=[]
line=f.readline().split()
i=1
while line!=[]:
　　a.append([line[0],line[1], i])
　　i+=1
　　line=f.readline().split()
n=len(a)-1
a[n][2]=-1
sg=input("請輸入插入的學(xué)生身高(cm):")
xh=str(len(a))
head=1
p=head;q=head
while　　　①　　:
　　p=q
　　q=a[q][2]
if q==head:
　　　　②　　
　　head=len(a) -1
else:
　　a.append([xh,sg,a[p][2]])
　　a[p][2]=len(a)-1
p=head
m=1
while p!=-1:
　　if m!=5:
　　　　print(a[p][0],end=" ")
　　　　m+=1
　　else:
　　　　print(a[p][0])
　　　　m=1
　　　　　　③　　
17.(2022 A9協(xié)作體返校考,15)學(xué)校舉辦了“語文作文現(xiàn)場賽”,參賽同學(xué)成績存儲在文本文件“gra.txt”中,如圖a所示(每一行記錄一位同學(xué)的姓名和成績,以“:”分隔)。陳老師利用Python程序?qū)ψ魑某煽冞M(jìn)行處理,統(tǒng)計出各個分?jǐn)?shù)等級的人數(shù),并輸出結(jié)果。程序運(yùn)行界面如圖b所示。
實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
def cla(x):　#判斷成績等級
　　if x>=50:
　　　return "A"
　　elif x>=40:
　　　return "B"
　　elif x>=30:
　　　return "C"
　　else:
　　　return "D"
gra=[]　#存儲各個整數(shù)型成績
num=[0]*4
f=open("gra.txt")
lines=f.readlines()　#將f對象的數(shù)據(jù)按行存入列表lines中
f.close()　#關(guān)閉文件
for line in lines:　#循環(huán)讀取列表lines 中的每個元素,并做相應(yīng)處理
　　a=line.strip().split(":") #去除結(jié)尾的換行符并以冒號為分隔符進(jìn)行分隔
　　gra.append(　　①　　)
for i in range(len(gra)):　#統(tǒng)計各等級人數(shù)
　　t=　　②　　
　　num[ord(t)-65]+=1
print("成績分布如下: ")
for i in range(len(num)):　#輸出統(tǒng)計結(jié)果
　　print(chr(i+65)+"等級有"+　③　+"人")
18.(2023七彩陽光開學(xué)考,15)食堂推出的三款特色菜,分別用A、B、C表示,想用投票方式統(tǒng)計出三款菜的受歡迎程度。每位投票者需要將三款菜按喜愛程度從高到低進(jìn)行排列,并投出一票。如圖a所示,小明負(fù)責(zé)將文件“投票.txt”中的選票進(jìn)行統(tǒng)計。第1張選票信息為“A,C,B”,表示投票者認(rèn)為A菜優(yōu)于C菜,C菜優(yōu)于B菜,即A菜也優(yōu)于B菜。他得到如圖b所示的投票情況。對選票進(jìn)行統(tǒng)計,得到三款菜的偏好,如圖c所示,數(shù)據(jù)第一行中的“6”說明有6張選票顯示A菜優(yōu)于B菜,“10”說明有10張選票顯示A菜優(yōu)于C菜,以此類推……將所有投票進(jìn)行統(tǒng)計,再將三款菜的得票數(shù)進(jìn)行求和,按得票數(shù)從高到低排列,分別為A菜16票,B菜11票,C菜12票,即可得到每款菜的受歡迎程度。
　　　　
　　　　
請回答下列問題:
(1)若有四款菜,投票情況如圖d所示,則第2受歡迎的菜為　　　　(填字母)菜。
(2)加框處代碼有錯誤,請改正。
(3)實(shí)現(xiàn)上述功能的 Python程序如下,請在劃線①②③處填入合適的代碼。
f=open('投票.txt')
a=[]
r=f.readline().strip()　#從文件中讀取一行,并把末尾的'\n'刪掉
while r:　#當(dāng)r非空(從文件讀取到了數(shù)據(jù))
　　a=r.split(',')
　　r=f.readline().strip()
f.close()
n=len(a[0])
p=[0]*n**2
for i in a:
　　for j in range(n-1):
　　　　x1=ord(i[j])-65
　　　　for k in range(　　①　　):
　　　　　　x2=ord(i[k])-65
　　②　　
b=[[' ',0]for i in range(n)]
for i in range(n):
　　b[i][0]=chr(i+65)
　　for j in range(n):
　　　　b[i][1]+=p[i*n+j]
i=1
while i　　x=b[i]
　　j=i-1
　　while 　　③　　:
　　　　b[j+1]=b[j]
　　　　j-=1
　　b[j+1]=x
　　i+=1
for i in range(n):
　　print('第',i+1,'受歡迎的菜為',b[i][0],',得票為',b[i][1],'票')
題組二
1.(2024屆百校起點(diǎn)調(diào)研測試,8)某二叉樹的中序遍歷為ABCDEF,則下列不可能是此二叉樹的是(　　)
　　　
　　　
2.(2024屆發(fā)展共同體聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其前序遍歷結(jié)果為BADCFGE,則字符“G”所在的位置為(　　)
A.①　　　B.②　　　C.③　　　D.④
3.(2024屆浙南名校聯(lián)盟聯(lián)考,8)有一棵二叉樹如圖所示,下列說法正確的是(　　)
A.此二叉樹是完全二叉樹
B.此二叉樹的葉子節(jié)點(diǎn)有3個
C.此二叉樹的后序遍歷為FDBECA
D.此二叉樹用一維數(shù)組表示為['A','B','C','D','E','F']
4.(2024屆名校協(xié)作體聯(lián)考,9)有一組數(shù)據(jù)4,2,6,3,1,5按序入棧,則出棧的順序可能是(　　)
A.4,2,5,3,1,6　　　　B.1,3,5,2,6,4
C.6,4,2,3,5,1　　　　D.6,2,4,3,1,5
5.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,11)執(zhí)行下列Python程序代碼,若輸入的數(shù)據(jù)為"ABCDE",則輸出的結(jié)果不可能是(　　)
from random import randint
st=[' ']* 10;top=-1;out=' '
s=input('s=')
while s:
　　flag=randint(0,1)
　　if flag==1:
　　　　top+=1;st[top]=s[0]
　　　　s=s[1:]
　　elif top !=-1:
　　　　out+=st[top];top-=1
while top !=-1:
　　out+=st[top]; top-=1
print(out)
A.CEDAB　　　　B.BDECA
C.ABCED　　　　D.DCBEA
6.(2024屆百校起點(diǎn)調(diào)研測試,11)有如下Python程序:
q=[0]* 6
q[0]=1
head=0;tail=1
while tail　　x=q[head]
　　if x%2==0:
　　　 q[tail]=x//2
　　　 tail+=1
　　else:
　　　 q[tail]=x*2
　　　 q[tail+1]=x*3
　　　 tail+=2
　　head+=1
程序運(yùn)行后, tail-head的值為(　　)
A.3　　　B.4　　　C.5　　　D.6
7.(2024屆浙南名校聯(lián)盟聯(lián)考,9)下列關(guān)于隊(duì)列和棧的說法,不正確的是(　　)
A.隊(duì)列是一種先進(jìn)先出的線性表,可在隊(duì)尾進(jìn)行插入操作
B.棧的特性是“先進(jìn)后出,后進(jìn)先出”
C.某棧的入棧的順序?yàn)閍bc,出棧順序只有3種
D.隊(duì)列和棧都是線性數(shù)據(jù)結(jié)構(gòu),都可以用數(shù)組來實(shí)現(xiàn)
8.(2024屆浙南名校聯(lián)盟聯(lián)考,11)已知字符"a"的ASCII碼值為97,有如下Python程序段:
que=[" "]*20
head,tail=0,0
for i in range(3):
que[tail]=chr(97+i)
tail+=1
st=["b" ,"c" ,"d" ,"a"]
top=3
while head < tail and top >-1:
　　if st[top]==que[head]:
　　　　head+=1
　　else:
　　　　que[tail]=st[top]
　　　　tail+=1
　　top-=1
print(que[head:tail])
執(zhí)行該程序段,則輸出的結(jié)果是(　　)
A.['c', 'd', 'c']　　　　B.['c', 'c', 'd']
C.['c', ' ', 'd']　　　　D.['c', 'd']
9.(2024屆強(qiáng)基聯(lián)盟統(tǒng)測,12)有如下Python程序段:
a=[i for i in range(1,7)]
b=[0]*6
head,tail=0,0
for i in range(1,7):
cnt=1
while cnta[tail]=a[head]
head=(head+1)%6
tail=(tail+1)%6
cnt+=1
b[a[head]-1]=i
head=(head+1)%6
執(zhí)行該程序段后,b[5]的值為(　　)
A.2　　　B.3　　　C.4　　　D.5
10.(2024浙江1月選考,12,2分)使用列表d模擬鏈表結(jié)構(gòu)(節(jié)點(diǎn)數(shù)大于0),每個節(jié)點(diǎn)包含數(shù)據(jù)區(qū)域和指針區(qū)域, h為頭指針。鏈表中各節(jié)點(diǎn)已按數(shù)據(jù)區(qū)域中數(shù)值的絕對值由小到大排列,如圖a所示。現(xiàn)要修改該鏈表各節(jié)點(diǎn)的鏈接關(guān)系,使鏈表各節(jié)點(diǎn)按數(shù)據(jù)區(qū)域中的數(shù)值由小到大排列,結(jié)果如圖b所示。實(shí)現(xiàn)該功能的程序段如下,方框中應(yīng)填入的正確代碼為(　　)
　　
t=h
p=d[h][1]
while p !=-1:
q=d[p][1]
　　　　　
p=q
d[t][1]=-1
A.
if d[p][0]>0:
　　d[q][1]=p
　　d[t][1]=q
else:
　　d[h][1]=q
　　h=p
　B.
if d[p][0]>0:
　　d[t][1]=q
　　t=q
else:
　　h=p
　　d[p][1]=t
C.
if d[p][0]>0:
　　d[t][1]=p
　　t=p
else:
　　d[p][1]=h
　　h=p
　D.
if d[p][0]>0:
　　d[t][1]=q
　　d[q][1]=p
else:
　　d[p][1]=h
　　h=q
11.(2024屆嘉興基測,15)最短路徑問題。以m*n個邊長為1的正方形組成的矩形,各頂點(diǎn)按行優(yōu)先從0開始編號,圖a所示為3*2的矩形及頂點(diǎn)編號。從頂點(diǎn)x(起點(diǎn))經(jīng)由各正方形的邊移動到頂點(diǎn)y(終點(diǎn))有多種移動路徑,編程求解所有的最短路徑。
(1)分析問題,將矩形轉(zhuǎn)換為計算機(jī)可處理的數(shù)據(jù)。可采用列表存儲矩形中各頂點(diǎn)的相鄰關(guān)系,如圖b所示。
頂點(diǎn) 相鄰頂點(diǎn)
0 [4,1]
1 [5,0,2]
2 [6,1,3]
3 [7,2]
4 [0,8,5]
...
圖b
編寫函數(shù)init,根據(jù)橫向和縱向的正方形數(shù)量,返回所有頂點(diǎn)及其所有的相鄰頂點(diǎn)數(shù)據(jù)。完善程序,在劃線處填入合適的代碼。
def init(m, n):
tot=(m+1)*(n+1)#頂點(diǎn)總數(shù)
lst=[[]for i in range(tot)]
for i in range(tot):
if i > m:
　lst[i].append(i-m-1)
if i < (m+1)*n:
　lst[i].append(i+m+1)
if i%(m+1) !=0:
　lst[i].append(i-1)
if i%(m+1)!=m:
　　　　　　　　　
return lst
(2)分析問題,查找所有從起點(diǎn)到終點(diǎn)的最短路徑。例如:查找從起點(diǎn)1到終點(diǎn)10的所有最短路徑,可先查找終點(diǎn)10的所有相鄰頂點(diǎn)(6,9,11),然后再逐個查找頂點(diǎn)6、9、11的相鄰頂點(diǎn),直到查找到起點(diǎn)1,獲得所有最短路徑,如圖c所示,共有3條長度為3的最短路徑,分別為1→2→6→10,1→5→6→10,1→5→9→10。若從起點(diǎn)4到終點(diǎn)11,共有　　　　條最短路徑。
(3)分析問題,存儲查詢到的路徑。可采用鏈表結(jié)構(gòu)保存路徑數(shù)據(jù),例如:查找從起點(diǎn)1到終點(diǎn)10的所有最短路徑,首先將終點(diǎn)10的數(shù)據(jù)[10,0,-1]保存在path[0]中,然后將其相鄰頂點(diǎn)6、9、11 的數(shù)據(jù)保存到path中,path[i][0]保存頂點(diǎn)的編號,path[i][1]保存當(dāng)前頂點(diǎn)到終點(diǎn)的距離,path[i][2]保存下一頂點(diǎn)在path中的位置,其值為-1表示當(dāng)前頂點(diǎn)為終點(diǎn)。
編寫函數(shù)print_path,輸出所有的最短路徑。完善程序,在劃線處填入合適的代碼。
def print_path(x,path,length):#為起點(diǎn)編號,length為path中有效元素個數(shù)
　cnt=0
for i in range(length):
if path[i][0]==x:
　　　cnt+=1
　　　s="最短路徑"+ str(cnt)+ " :"
　　　v=path[i]
　　　while 　　　　　　:
　　　　　s=s+ str(v[0])+ ","
　　　　　v=path[v[2]]
　　　s=s+ str(v[0])+ "。"
　　　print(s)
(4)實(shí)現(xiàn)上述功能的Python程序如下,運(yùn)行結(jié)果如圖d所示。請在劃線處填入合適的代碼。
請輸入起點(diǎn):0
請輸入終點(diǎn):10
最短路徑1:0,1,2,6,10。
最短路徑2:0,1,5,6,10。
最短路徑3:0,4,5,6,10。
最短路徑4:0,1,5,9,10。
最短路徑5:0,4,5,9,10。
最短路徑6:0,4,8,9,10。
圖d
m=3#橫向正方形數(shù)量
n=2#縱向正方形數(shù)量
mtx=init(m, n)
x=int(input("請輸入起點(diǎn):"))
y=int(input("請輸入終點(diǎn):"))
path=[[]for i in range(999)]
passed=[False]* len(mtx)　　#保存頂點(diǎn)是否已途經(jīng)
　　①　　
dis=0;head=0;tail=0
path[tail]=[y,0,-1]
tail+=1
passed[y]=True
while not found:
　　dis+=1
　　pass_dis=[False]* len(mtx)
　　tmp=tail
　　for i in range(head,tail):
v=path[i]
for d in mtx[v[0]]:
if not passed[d]:
　　path[tail]=　　②　　
　　tail+=1
　　pass_dis[d]=True
if d==x:
　　found=True
　　head=tmp
　　for i in range(len(mtx)):　　#標(biāo)記已途經(jīng)的頂點(diǎn)
　　　 if 　　③　　:
　　　　　passed[i]=True
#輸出結(jié)果
print_path(x, path,tail)
12.(2022 A9協(xié)作體返校考,16)字符串分段。輸入一串僅由小寫字母組成的字符串s,將這個字符串劃分為盡可能多的小片段,要求同一個字母只出現(xiàn)在其中的一個片段中,并按照分段順序逐行輸出分段結(jié)果。程序運(yùn)行界面如下:
請輸入一串僅包含小寫字母的字符串:asdasmhjhh
asdas
m
hjhh
(1)實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
s=input("請輸入一串僅包含小寫字母的字符串:")
c=0
p=[-1]*52　#數(shù)組p用來記錄各個小寫字母出現(xiàn)的起始位置和結(jié)束位置
#a[0]記錄a出現(xiàn)的起始位置,a[1]記錄a出現(xiàn)的結(jié)束位置,依此類推
for i in range(0,len(s)):　#記錄各字符第一次和最后一次出現(xiàn)的位置
　　a=　　①　　
　　if p[2*a]==-1:
　　　p[2*a]=i
　　else:
　　　p[2*a+1]=i
for i in range(0,26):
　　if p[2*i]>p[2*i+1]:
　　　p[2*i+1]=p[2*i]　#只出現(xiàn)一次的字符,起始位置就是結(jié)束位置
　　if p[2*i]!=-1:
　　　　c+=1
for i in range(0,c):　#將字符位置按照出現(xiàn)的起始位置升序排序
　　for j in range (25, i,-1):
　　　if p[2*j]> -1:
　　　　　if p[2*(j-1)]> p[2*j]or 　　②　　:
　　　　　p[2*(j-1)],p[2*j]=p[2*j],p[2*(j-1)]
　　　　　　p[2*(j-1)+1],p[2*j+1]=p[2*j+1],p[2*(j-1)+1]
t1,t2=p[0],p[1]　#字符串分段
for i in range(1, c):
　　if p[2*i]< t2 and p[2*i+1]> t2:
　　　　　　③　　
　　elif p[2*i]>t2:
　　　　print(s[t1:t2+1])
　　　　t1,t2=p[2*i], p[2*i+1]
print(s[t1:t2+1])
(2)運(yùn)行程序后,若輸入的字符串s為"hshjhqueeqabaa",輸出的結(jié)果一共　　行,其中第二行顯示結(jié)果為　　　　。
答案　(1)①ord(s[i])-97　或ord(s[i])-ord("a")
②p[2*(j-1)]==-1　③t2=p[2*i+1]　(2)3;queeq
13.(2022 Z20名校聯(lián)盟聯(lián)考,15)校學(xué)生會要從兩個候選人A和B中選舉一個會長,每個候選人都有自己的支持方。現(xiàn)在以輪為過程來進(jìn)行選舉,在每一輪選舉中,當(dāng)前成員可以禁止另一位成員的選舉權(quán),即讓另一位成員在這一輪和隨后的幾輪中都喪失選舉權(quán)。
在選舉過程中,一旦有選舉權(quán)的成員都來自同一個陣營,則該陣營勝利。
字母A和B分別代表兩位候選人,輸入一個字符串代表每個成員的陣營,例如輸入“ABB”,則輸出結(jié)果為B,即候選人B為會長。
說明:第一輪中,第一個成員(A)可以讓第二個成員(B)失去選舉權(quán),第二個成員(B)會被跳過,因?yàn)樗倪x舉權(quán)被禁止,第三個成員(B)可以讓第一個成員(A)失去選舉權(quán),因此在第二輪只剩下第三個成員(B)擁有選舉權(quán),則輸出結(jié)果為B,即候選人B為會長。
(1)若輸入“ABABB”,則會長為　　　　。
(2)實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
s=input("請輸入投票字符串:")
queA=[" "]*100 ; queB=[" "]*100
headA=headB=0
tailA=tailB=0
n=len(s)
for i in range(n):
　　if　　①　　:
　　　　queA[tailA]=i
　　　　tailA+=1
　　else:
　　　　queB[tailB]=i
　　　　tailB+=1
while 　　②　　:
　　if queA[headA]　　　　queA[tailA]=queA[headA]+n
　　　　tailA+=1
　　else:
　　　　queB[tailB]=queB[headB]+n
　　　　tailB+=1
　　headA+=1; headB+=1
if　　③　　:
　　print("B")
else:
　　print("A")
14.(2022 Z20名校聯(lián)盟聯(lián)考,16)“最小波動值”是經(jīng)濟(jì)管理學(xué)上的一種衡量營業(yè)情況是否穩(wěn)定的概念,當(dāng)“最小波動值”越大時,就說明營業(yè)情況越不穩(wěn)定。
經(jīng)濟(jì)管理學(xué)上對“最小波動值”的定義:
某一天的“最小波動值”=min{|該天以前某一天的營業(yè)額-該天營業(yè)額|},第一天的“最小波動值”為第一天的營業(yè)額。
若要分析某個店鋪的營業(yè)情況是否穩(wěn)定,只需要把一段時間內(nèi)每一天的“最小波動值”加起來即可。現(xiàn)根據(jù)某個店鋪一段時間內(nèi)每一天的營業(yè)額(說明:支出為0表示該天不營業(yè)),設(shè)計程序計算該店鋪的“最小波動值”之和。
(1)若營業(yè)額數(shù)據(jù)為“13,10,14,15,3,11”,則“最小波動值”之和是　　　　。
(2)實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
import pandas as pd
num=[]　#數(shù)組num按經(jīng)營時間順序存儲每天營業(yè)額
numy=[]　#數(shù)組numy按營業(yè)額降序存儲每天營業(yè)額
item=[]　#根據(jù)數(shù)組numy構(gòu)造鏈表item
df=pd.read_excel("yye.xlsx")
df=　　①　　　#篩選出營業(yè)的記錄
df["營業(yè)額"]=df.sum(axis=1)　#在df對象最后一列插入“營業(yè)額”列
df1=df.sort_values("營業(yè)額",ascending=False)
for i in df.index:
　　num.append(df["營業(yè)額"][i])
for i in df1.index:
　　numy.append(df["營業(yè)額"][i])
n=1
for i in numy:
　　item.append([i,n])
　　n+=1
item[n-2][1]=-1
head=0
k=0
　　②　　
for i in num[-1 :-len(num):-1]:
　　p=head
while item[p][0]!=i:
　　k=p
　　p=item[p][1]
f=item[p][1]
if f==-1:
　　tot+=abs(item[k][0]-item[p][0])
elif p==head:
　　tot+=abs(item[f][0]-item[p][0])
else:
　　tot+=min(abs(item[k][0]-item[p][0]) , abs(item[f][0]-item[p][0]))
if p==head:
　　head=item[head][1]
else:
　　　　③　　
print("該店鋪的最小波動值之和是",tot)
15.(2023“山水聯(lián)盟”開學(xué)考,16)臨近年關(guān),學(xué)校為活躍新年氣氛,舉辦迎新年聯(lián)歡活動,最后一個節(jié)目為“我是大贏家”抽獎活動,為增強(qiáng)互動效果,最后中大獎的中獎?wù)哂山處焸兓赢a(chǎn)生,游戲規(guī)則是:全校所有教工,每人獲得一個隨機(jī)編號,編號不得重復(fù),然后按照編號大小順時針手拉手圍成一個圈,最后一個老師與第一個老師手拉手,接下來由第1個人指定m的值,從編號為1的人開始報數(shù)(1,2,3,…),報到m的人出圈,不再參加互動游戲,接著再由出圈人的上一位老師新指定m的值,并重新開始報數(shù),逆時針報到m的人出列,游戲過程中出圈的人由老師們自己決定,如此繼續(xù),順時針出圈一個人,逆時針出圈一個人,直到圈中只剩下一個人,他就是今天的最大贏家。小明編寫了一個Python程序?qū)崿F(xiàn)上述功能,程序運(yùn)行時,輸入?yún)⒓佑螒虻娜藬?shù),每次有人出圈后,再輸入下一個指定值。
實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處輸入合適的代碼。
#刪除索引為p的游戲者
def delete(a,head,p):
if a[p][1]!=-1:
　　a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
　　　　①　　
if head==p:
　　head=a[head][2]
return head
n=int(input("請輸入?yún)⒓佑螒虻娜藬?shù)"))
a=[[i+1,i-1,i+1]for i in range(n)]
a[0][1]=n-1
a[n-1][2]=0
p=head=0
while 　　②　　:
　　m=int(input("請輸入順時針數(shù)第幾位出局"))
　　for i in range(m-1):
　　　　　　③　　
　　head=delete(a,head,p)
　　p=a[p][1]　#退回到上一位游戲者
　　if a[head][1]!=head:
　　　　m=int(input("請輸入逆時針數(shù)第幾位出局"))
　　　　for i in range(m-1):
　　　　　　p=a[p][1]
　　　　head=delete(a,head,p)
　　　　　　④　　　#退回到上一位游戲者
print(a[head])
16.(2023強(qiáng)基聯(lián)盟統(tǒng)測,16)某銀行網(wǎng)點(diǎn)有5個窗口,銀行最少要保持3個窗口營業(yè),另2個窗口初始為備用狀態(tài)。客戶按批次進(jìn)入大廳,每個客戶的業(yè)務(wù)辦理時間為1個單位,銀行每過1個時間單位就允許下一批客戶進(jìn)入。對于進(jìn)入銀行的客戶,如果某窗口正空閑,則可上前辦理業(yè)務(wù),反之,若所有窗口均有客戶,他便會排在最短的隊(duì)伍后面。當(dāng)平均每個營業(yè)窗口前的隊(duì)伍人數(shù)大于等于7人時(隊(duì)伍包括正在辦理業(yè)務(wù)的客戶在內(nèi)),銀行可臨時將備用窗口中一個或兩個改為營業(yè)窗口,當(dāng)所有窗口平均客戶少于7人時,將立即停用一個營業(yè)窗口轉(zhuǎn)為備用,窗口平均人數(shù)若繼續(xù)減少至以上情況,可再停止一個營業(yè)窗口,但最多只能有兩個窗口為備用狀態(tài)。
現(xiàn)模擬該銀行排隊(duì)程序,效果如圖所示,輸出10個人各自的等待時間單位:
請輸入共有多少批客戶:2
輸入每一批的人數(shù)4,6
(1:0)(2:0)(3:0)(4:1)(5:0)(6:0)
(7:1)(8:1)(9:1)(10:2)
輸出格式描述:(客戶編號:等待的時間)
(1)實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
mins=3　#常用窗口3個
maxs=5　#最多可開設(shè)5個窗口
lims=7　#正常服務(wù)時每個窗口平均等待的最多人數(shù)
tm=int(input('請輸入共有多少批客戶:'))
ps=list(map(int,input('輸入每一批的人數(shù)').split(',')))
sw=mins
if len(ps)!=tm:
print('輸入有誤!')
pid,cnt=0,0
head,tail=0,0
qe=[[0,0]]*1000 #創(chuàng)建等待隊(duì)列
def updatetime(s):
for j in range(len(s)):
s[j][1]+=1
for i in range(tm):
for j in range(sw):　#將輪到的人進(jìn)行出隊(duì)
　　if　①　:
　print(f'({qe[head][0]} :{qe[head][1]})',end='')
head+=l
cnt-=1
#人數(shù)減少后,檢查人數(shù)和窗口數(shù)是否符合要求并按照要求減少窗口,代碼略
if head!=tail:
　②　#更新等待隊(duì)列里每個人的等待時間
for j in range(ps[i]):
pid+=1
qe[tail]=[pid,0]
tail+=1
cnt+=1
while　③　:
sw+=1
while cnt>0 :
#最后一批人進(jìn)入銀行后,程序只需要處理等待隊(duì)列剩余人員到出隊(duì)和窗口的減少,直至人數(shù)為0,代碼略
(2)共有3批客戶,分別為22人,23人,21人,則輸出結(jié)果中,第4個人等待的時間單位是　　　　。
17.(2022浙北G2聯(lián)盟期中,16)小明來到探險島尋寶,島上共有N個寶藏(標(biāo)號為0至N-1)。每個寶藏有一條路連接下一個寶藏,寶藏號和下一個寶藏號使用鏈表存儲。小明想知道,從其中一個寶藏出發(fā),最多可以找到多少個寶藏。
例如,共有5個寶藏,輸入“1,3,4,4,1,”表示0~4各寶藏點(diǎn)連接的下一個寶藏依次是:1,3,4,4,1(如下表)。則最多可以找到4個寶藏,路徑為:0號→1號→3號→4號。
寶藏號 0 1 2 3 4
下一個寶藏號 1 3 4 4 1
程序代碼如下:
s=input("請輸入寶藏連接的情況:")
t=0;c=" ";a=[]
for i in s:
　if i!=",":
　　c+=i
　else:
　　a.append([t,int(c)])
　　c=" "
　　　　　①　　　
max=0
for head in range(0,t):　 #枚舉尋找寶藏起點(diǎn)
　g=[]
　p=head
　while p not in g:
　　g.append(p)
　　　　　②　　　
　if len(g)>max:
　　　　　③　　　
print(max)
(1)若有4個寶藏,且每個寶藏的連接情況為:2,0,0,1,那么小明最多可以挖到的寶藏數(shù)是　　　　。
(2)請將代碼補(bǔ)充完整。
專題七　數(shù)據(jù)的組織
考點(diǎn)過關(guān)練
考點(diǎn)一　數(shù)組
1.(2022浙北G2聯(lián)盟期中,15)有如下Python 程序段:
import random
a=[]
for i in range(10):
　　　 a.append(random.randint(1,100))
i=0
while i <10:
　　　 if i==0:
　　　　　　i=i+1
　　　 elif a[i-1]<=a[i]:
　　　　　　　　　①　　　
　　　 else:
　　　　　　a[i],a[i-1]=a[i-1],a[i]
　　　　　　　　　②　　　
print(a)
執(zhí)行該程序段實(shí)現(xiàn)了隨機(jī)生成一個數(shù)組,并將其元素遞增輸出的功能。劃線處的代碼應(yīng)該是(　　)
A.① i+=1　② i=1
B.① i-=1　② i=1
C.① i+=1　② i+=1
D.① i-=1　② i-=1
答案　A　
2.(2022紹興諸暨期中,3)使用列表生成的方式創(chuàng)建數(shù)組代碼如下:
a=[i*i-1 for i in range(10) if i%2==0]
則數(shù)組元素a[3]的值為(　　)
A.2　　　B. 8　　　C. 15　　　D. 35
答案　D　
3.(2022紹興諸暨期中,4)設(shè)有一個5×8的二維數(shù)組a,若按行優(yōu)先的順序存儲數(shù)組元素,則元素a[3][5]前面元素的個數(shù)為(　　)
A.21　　　B. 22　　　C. 29　　　D. 37
答案　C　
4.(2022紹興諸暨期中,13)有如下Python程序段:
a=[[0 for i in range(3)]for j in range(3)]
for i in range(3):
　for j in range(3):
　　a[i][j]=i*5+j+1
for i in range(1,3):
　for j in range(2):
　　print(a[j][i],end=" ")
程序段執(zhí)行后,輸出的結(jié)果是(　　)
A.2 3 7 8　　　　B.7 12 8 13
C.2 7 3 8　　　　D.6 7 11 12
答案　C　
5.(2022杭州期中,10)下述代碼段用于實(shí)現(xiàn)在數(shù)組a中將新數(shù)據(jù)k插入下標(biāo)為 j(0<=j<=8)的位置:
a=[8,6,12,3,5,7,11,2,10,0]
i=8
while i>=j:
　　　　(1)　　
　　　　(2)　　
　　(3)　　
橫線處的代碼由以下五部分中的三部分組成:
①a[i+1]=k　②a[i]=k　③a[i+1]=a[i]
④a[i]=a[i-1]　⑤i=i-1
下列選項(xiàng)中代碼選擇與順序正確的是(　　)
A.③⑤②　　　B.⑤③①　　　C.③⑤①　　　D.④⑤②
答案　C　
6.(2022嘉興期中,3)用 Python 程序段定義一個3行4列的二維數(shù)組(要求先將各元素的值初始化為0,再將第2行第 2 個元素重新賦值為1),以下程序段可行的是(　　)
A. arr=[[0]*3 for j in range(4)]
arr[2][2]=1
B.arr=[[0]*4]*3
arr[1][1]=1
C.arr=[[0 for i in range(4)]for j in range(3)]
arr[1][1]=1
D.arr=[[0,0,0,0]for j in range(3)]
arr[2][2]=1
答案　C　
考點(diǎn)二　鏈表
1.(2022浙南名校聯(lián)盟期末,12)一個頭指針 head=2 的單向鏈表 L=[[30,4], [10,-1], [20,0], [15,1],[21,3]]通過以下 Python 程序段,轉(zhuǎn)換為原鏈表的逆序鏈表,即頭指針 head=1,L=[[30,2], [10,3], [20,-1], [15,4],[21,0]]。
　q=-1
　p=head　#head 為原鏈表頭指針
　while p!=-1 :
　　tmp=L[p][1]
　　
　head=q
上述程序段中方框處可選的語句為:
①p=tmp　②q=p　③L[p][1]=q
則方框處語句依次為(　　)
A.③②①　　　B.③①②　　　C.①③②　　　D.①②③
答案　A
2.(2022浙北G2聯(lián)盟期中,14)用兩個列表a、b分別保存單向鏈表中的數(shù)據(jù)區(qū)域和指針區(qū)域。如圖所示,在節(jié)點(diǎn)x與節(jié)點(diǎn)y之間插入一個新節(jié)點(diǎn),操作步驟正確的是(　　)
①b[i]=b[y]　　　　　②b[i]=b[x]
③b[y]=i　　　　④b[x]=i
⑤b[i]=x　　　　⑥b[i]=y
A.③⑥　　　B.④②　　　C.①③　　　D.②④
答案　D　
3.(2023浙江開學(xué)考,10)已知一個鏈表a,其a[i][0]存儲索引i下節(jié)點(diǎn)的數(shù)據(jù)區(qū)域,a[i][1]存儲索引i下節(jié)點(diǎn)的指針區(qū)域。對于當(dāng)前鏈表中的一個節(jié)點(diǎn)p(索引為p),若要刪除p的后一個節(jié)點(diǎn)q(q=a[p][1]),則應(yīng)執(zhí)行語句(　　)
A.a[p]=a[q]
B.a[p][1]=a[q][1]
C.a[p]=a[a[q][1]]
D.a[p]=a[q];a[p][1]=a[q][1]
答案　B　
4.(2022杭州期中,12)在Python中用列表模擬鏈表結(jié)構(gòu),某程序段如下:
a=[['H',1],['a',2],['n',3],['g',4],['2',5],['0',6],['2',7],['2',0]]
p, head=3,3;q,c=-1,0;m,n=3,0
while n<4:
　　c=c+1
　　if c==m:
　　　　n=n+1;c=0
　　　　if p==head:
head=a[p][1]
a[q][1]=head
p=a[p][1]
　　　　else:
　a[q][1]=a[p][1]
　p=a[p][1]
　　else:
q=p
p=a[p][1]
#從頭節(jié)點(diǎn)開始遍歷鏈表a邏輯順序的所有節(jié)點(diǎn),并依次輸出節(jié)點(diǎn)的數(shù)據(jù),代碼略
該程序段執(zhí)行后的輸出結(jié)果為(　　)
A.ng02　　　B.g02n　　　C.2an2　　　D.22an
答案　D　
5.(2022諸暨期末,8)某單向鏈表如圖所示,在data2與data3之間插入一個新節(jié)點(diǎn)data4(p指向data2,r指向data4。列表data來記錄鏈表數(shù)據(jù)域,列表next來記錄指針域),以下選項(xiàng)中正確的執(zhí)行步驟為(　　)
①next[p]=next[r]　　　　②next[p]=r
③next[r]=p　　　　④next[r]=-1
⑤next[r]=next[p]　　　　⑥next[p]=-1
A.③⑥　　　B.⑤②　　　C.①④　　　D.⑤②④
答案　B　
6.(2022杭嘉湖金月考,15)山頂上有10個圓形排列的洞,一只狐貍和一只兔子各住一個洞。狐貍總想吃掉兔子。一天兔子對狐貍說:“你想吃我有一個條件,先把洞從1~10編上號,你先到1號洞找我;第二次隔1個洞(即3號洞)找我,第三次隔2個洞(即6號洞)找我,依此類推,次數(shù)不限。但狐貍從早到晚進(jìn)進(jìn)出出了1000次,仍沒有找到兔子。請問兔子可能躲在哪個洞里
實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
hole=[]
n=10
m=1000
#構(gòu)造一個循環(huán)鏈表,并給n個洞編號,設(shè)置洞的初始標(biāo)志為0
#鏈表的節(jié)點(diǎn)樣式為:[洞的標(biāo)志,洞的編號]
for i in range(n-1):
　　hole.append([0,i+1])
　　　　　(1)　　　　　
#狐貍開始找兔子,將進(jìn)入過的洞標(biāo)志改為1,尋找m次結(jié)束
head=0
k=head
hole[0][0]=1
for i in range(1,m):
　　for j in range(1,i+2):
　　　　　　　　(2)　　　　　
　　hole[k][0]=1
#輸出標(biāo)志仍為0的洞,即兔子可能的藏身地點(diǎn)
for i in range (len(hole)):
　　if hole[i][0]==0:
　　　　print("兔子可能躲在第"+　(3)　+"號洞")
答案　(1)hole.append([0,0])　(2)k=hole[k][1]　
(3)str(i+1)
考點(diǎn)三　隊(duì)列
1.(2024屆七彩聯(lián)盟聯(lián)考,11)有如下程序段:
s=input()
head=0;tail=0;ans=0;tmp=' '
q=[' ']*100
flag=True
for i in range(len(s)):
　if s[i]==',':
　　while head!=tail:
　　　tmp+=q[head]
head+=1
if flag and head　head+=1
flag=not flag
　　ans+=int(tmp)
　　tmp=' ';flag=True
　elif '0'<=s[i]<='9':
　　q[tail]=s[i]
　　tail+=1
輸入s為"1-500,2023900-,",執(zhí)行該程序段,變量ans的值為(　　)
A.100　　　B.22300　　　C.22351　　　D.22400
答案　D　
2.(2022杭州“六縣九校”期中,5)有A、B、C、D、E五個人依次進(jìn)入電梯,結(jié)果警告超重了,需要出去一個人才能正常運(yùn)行,按照數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的思維,應(yīng)離開電梯的人分別是(　　)
A.棧:A　隊(duì)列:E　　　　B.棧:A　隊(duì)列:A
C.棧:E　隊(duì)列:A　　　　D.棧:E　隊(duì)列:E
答案　C　
3.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,9)執(zhí)行下列Python程序段,輸出結(jié)果為(　　)
data=[1,2,3,1,2,3]
que=[0]*10
head=tail=0
for i in range(len(data)):
if data[i]%2 !=0:
　　que[tail]=data[i]
　　tail+=1
elif tail-head>1:
　　que[tail-1]+=que[head]
　　head+=l
print(que[head:tail])
A.[3,2,1]　　　　B.[1,2,3]
C.[1,3,1]　　　　D.[3,2,3]
答案　D　
4.(2024屆新陣地聯(lián)盟第二次聯(lián)考,11)有如下程序段:
m=3;n=7
head=tail=0;ans=0
vis=[0]*10;q=[0]*10
for i in range(n):
x=int(input())
if(vis[x]=0):
　ans+=1
　if(tail-head>=m):
　　vis[q[head]]=0
　　head+=1
　q[tail]=x
　tail+=1
　vis[x]=1
print(ans)
運(yùn)行該程序段,依次輸入x的值:1,2,1,5,4,4,1。則程序運(yùn)行完成后ans 的值是(　　)
A.3　　　B.4　　　C.5　　　D.6
答案　C　
5. (2024屆天域全國名校協(xié)作體聯(lián)考,12)已知列表a的長度為6,a[0]至a[5]的值依次為18,12,24,15,21,0,某程序如下所示:
head, tail=0,5
x=a[head]
head+=1
while (head+1) % len(a) !=tail:
　　 t=y=a[head]
head=(head+1) % len(a)
if x　 x,y=y,x
if x % y !=0:
　 a[tail]=x % y
　 tail=(tail+1) % len(a)
x=t
print(a[head])
程序運(yùn)行后,輸出的結(jié)果是(　　)
A.24　　　　B.12　　　
C.3　　　　D.0
答案　C　
6.(2023“山水聯(lián)盟”開學(xué)考,11)有如下Python程序代碼:
s="ABCDEF"; head=0;tail=0
que=[" "]*100
for i in range(len(s)):
if i%2==0:
　que[tail]=s[i]
else:
　que[tail]=s[len(s)-i]
tail=tail+1
for i in range(len(s)):
print(que[head], end=" ")
head=head+1
以上程序運(yùn)行后,輸出列表的情況是(　　)
A.ABCDEF　　　　B.FEDCBA
C.ACEFDB　　　　D.AFCDEB
答案　D　
考點(diǎn)四　棧
1.(2022浙南名校聯(lián)盟期末,10)一個棧的入棧序列為“6、9、5、7、8、3”,其出棧序列不可能是(　　)
A.3、8、7、5、9、6
B.7、5、9、8、6、3
C.6、5、7、9、3、8
D.5、9、6、3、7、8
答案　D　
2.(2024屆百校起點(diǎn)調(diào)研測試,9)棧q初始有三個值,經(jīng)過一系列入棧、出棧操作后,棧為空,若元素出棧的順序是1,2,3,4,5,6,7,則棧q初始的情況可能是(　　)
A.[1,2,3]　　　　B.[7,5,6]
C.[6,3,1]　　　　D.[4,7,2]
答案　C　
3.(2024屆Z20聯(lián)盟聯(lián)考,9)若元素入棧的順序是1,2,3,4,5,6,不允許連續(xù)三次入棧,則可能的出棧序列為(　　)
A.2,3,5,1,6,4　　　　B.1,2,3,6,5,4
C.2,4,3,1,6,5　　　　D.2,5,4,6,3,1
答案　C　
4.(2024屆七彩聯(lián)盟聯(lián)考,9)假設(shè)棧S的最大長度為3,其初始狀態(tài)和終止?fàn)顟B(tài)均為空,經(jīng)過一系列入棧和出棧的操作,若元素最后的出棧序列為F,E,D,C,B,A,則可能的入棧順序?yàn)?　　)
A.ABCDEF　　　　B.ACDFEB
C.BEFACD　　　　D.BFDECA
答案　D　
5.(2024屆嘉興基測,12)待入棧的序列a有多種出棧序列,以下函數(shù)用于判斷序列b是不是a的出棧序列,代碼如下:
def judge(a,b):
n=len(a);st=[-1]*n
top=-1;i=j=0
while i　top+=1
　　　①　　
　i+=1
　while top>-1 and 　　②　　:
　　top-=1
　　j+=1
return top==-1
from random import shuffle
a=[1,2,3,4,5]
b=[1,2,3,4,5]
shuffle(b)　　#將序列b的元素隨機(jī)排序
if judge(a,b):
　　print(b,'是', a,'的出棧序列')
else:
　　print(b,'不是',a,'的出棧序列')
程序運(yùn)行結(jié)果如圖所示。劃線處應(yīng)填寫的語句是(　　)
python 12.py
[2,5,4,3,1]是[1,2,3,4,5]的出棧序列
python 12.py
[5,2,3,1,4]不是[1,2,3,4,5]的出棧序列
A.①st[top]=a[i]　②st[top]==b[j]
B.①st[top]=a[i]　②st[-1]==b[j]
C.①st[top]=b[i]　②st[top]==a[j]
D.①st[top]=b[i]　②st[-1]==a[j]
答案　A　
6.(2022 Z20名校聯(lián)盟,10)某算法利用“棧”思想進(jìn)行字符串處理,其步驟如下:①創(chuàng)建長度為n的空棧,字符依次入棧;②當(dāng)達(dá)到棧滿狀態(tài)或數(shù)據(jù)全部入棧時,字符依次出棧,按照出棧順序連接成新字符串:③若還有未處理的字符,則重復(fù)步驟①②,直到全部字符處理完畢。實(shí)現(xiàn)該功能的 Python程序如下:
s=input("請輸入字符串:")
n=5;st=[" "]*n
top=-1;i=0;m=" "
while i　while 　(1)　 and i　　　(2)　
　　st[top]=s[i]
　　i+=1
　while top!=-1:
　　m+=st[top]
　　　(3)　
print("密文:" ,m)
加框處(1)(2)(3)的代碼由以下代碼組成:
①top-=1　②top+=1　③top+1④top下列選項(xiàng)中代碼順序正確的是(　　)
A.④②①　　　　B.③①②
C.③②①　　　　D.④①②
答案　C　
7.(2022諸暨海亮高中月考,10)有如下程序段:
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i　　if i < len(bt) and bt[i] is not None:
　　　　stack.append(i)
　　　　i=2*i+1
　　else:
　　　　i=stack.pop()
　　　　result.append(bt[i])
　　　　i=2*i+2
print("-".join(result))
則程序運(yùn)行后輸出的結(jié)果為(　　)
A.A-B-D-C-E-F　　　　
B.D-B-E-F-C-A
C.D-B-A-E-C-F　　　　
D.A-B-C-D-E-F
答案　C　
考點(diǎn)五　樹
1.(2024屆Z20聯(lián)盟聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其后序遍歷結(jié)果為“物技化數(shù)英語”,則中序遍歷結(jié)果為(　　)
A.語數(shù)英物化技　　　　B.物數(shù)技化語英
C.語數(shù)物化技英　　　　D.化物技英數(shù)語
答案　B　
2.(2022名校協(xié)作體,10)已知二叉樹T2的后序遍歷序列為G-D-H-E-B-I-F-C-A,中序遍歷序列為D-G-B-E-H-A-C-I-F,則二叉樹T2的前序遍歷序列為(　　)
A.A-B-D-G-E-H-C-I-F
B.A-B-D-G-E-H-C-F-I
C.A-B-D-G-E-H-F-C-I
D.該二叉樹形態(tài)不唯一,無法確定
答案　B　
3.(2024屆新陣地聯(lián)盟第二次聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其后序遍歷結(jié)果為FABGDEC,則中序遍歷結(jié)果為(　　)
A.FDAGBCE　　　　B.FDABGEC
C.AGBDFCE　　　　D.FDAGBEC
答案　A　
4.(2024屆天域全國名校協(xié)作體聯(lián)考,8)下列二叉樹中,后序遍歷結(jié)果不為CBFEAD的是(　　)
　　
　　
答案　D　
5.(2024屆七彩聯(lián)盟聯(lián)考,8)某二叉樹用一維數(shù)組表示(見表)。該二叉樹從根節(jié)點(diǎn)開始,按照從上到下,從左到右的順序依次用A-H字母表示,該二叉樹的中序遍歷為(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H
A.DBGEACFH　　　　B.DBGEACHF
C.DBEGACHF　　　　D.ABCDEFGH
答案　A　
考點(diǎn)六　大數(shù)據(jù)時代的數(shù)據(jù)的組織
1.下列關(guān)于實(shí)時查詢數(shù)據(jù)系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)的說法,不正確的是(　　)
A.在實(shí)時查詢系統(tǒng)中使用數(shù)組,時效性較差
B.在鏈表中查找數(shù)據(jù)時效性較高,插入數(shù)據(jù)時效性較低
C.跳躍表基于有序鏈表
D.跳躍表通過跨區(qū)間、跳躍性的比較,避免了依次比較,提高了效率
答案　B　
2.有如下跳躍表:
若要在原鏈表中插入元素7,則數(shù)據(jù)元素需要比較的次數(shù)為(　　)
A.1　　　B.3　　　C.4　　　D.5
答案　B　
3.下列關(guān)于Hadoop的說法,不正確的是(　　)
A.Hadoop是一種超大規(guī)模,高可靠性,高可擴(kuò)展性的數(shù)據(jù)庫
B.Hadoop是Google云計算技術(shù)的開源實(shí)現(xiàn)
C.使用Hadoop可以在POI數(shù)據(jù)的處理中獲得更方便的體驗(yàn)和更低廉的成本
D.Hadoop可以對海量地理信息進(jìn)行處理和計算
答案　A　
專題綜合練
題組一
1.(2024屆名校協(xié)作體聯(lián)考,8)某二叉樹的前序遍歷結(jié)果為GFDECAB,中序遍歷結(jié)果為DFGCAEB。關(guān)于該二叉樹,以下說法正確的是(　　)
A.該二叉樹的后序遍歷為ADFCBEG
B.該二叉樹的深度為4,節(jié)點(diǎn)C在第3層
C.該二叉樹的葉子節(jié)點(diǎn)數(shù)比非葉子節(jié)點(diǎn)數(shù)多一個
D.該二叉樹可以通過添加3個節(jié)點(diǎn)后變?yōu)橥耆鏄?br/>答案　B　
2.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,8)某二叉樹的樹形結(jié)構(gòu)如圖所示,其后序遍歷結(jié)果為FBCEAD,則前序遍歷結(jié)果為(　　)
A.ABCDEF　　　　B.FEDCBA
C.DFACBE　　　　D.FDBCAE
答案　C　
3.(2024屆強(qiáng)基聯(lián)盟統(tǒng)測,8)已知某二叉樹的后序遍歷為GDBEHFCA,中序遍歷為DGBAECHF,下列說法正確的是(　　)
A.該二叉樹中葉子節(jié)點(diǎn)有3個
B.該二叉樹的前序遍歷為ABDGCEHF
C.該二叉樹是一棵完全二叉樹,樹的高度為4
D.該二叉樹中度為1的節(jié)點(diǎn)有2個
答案　A　
4.(2024屆新陣地聯(lián)盟第二次聯(lián)考,9)棧S初始狀態(tài)為空棧,將序列3,2,5,7,1中元素逐一入棧,當(dāng)棧空或入棧元素比棧頂元素大時則入棧,否則出棧至符合條件再入棧。序列所有元素入棧完畢后,棧內(nèi)剩余元素出棧,直至棧空。則出棧的順序是(　　)
A.17523　　　　B.37521
C.37512　　　　D.32751
答案　B　
5.(2024屆天域全國名校協(xié)作體聯(lián)考,9)利用棧求逆波蘭表達(dá)式(表達(dá)式由操作數(shù)和運(yùn)算符組成)的方法是:從左往右掃描該表達(dá)式,遇到操作數(shù)時入棧;遇到運(yùn)算符時,把處于棧上方的兩個元素依次出棧,用運(yùn)算符計算,并把計算結(jié)果壓入棧中。如此反復(fù)操作,直至表達(dá)式掃描結(jié)束。當(dāng)用該算法求逆波蘭表達(dá)式abcd-*e/+f-的值時(abcdef表示不同的操作數(shù)),所使用的棧的深度至少為(　　)
A.3　　　B.4　　　C.5　　　D.6
答案　B　
6.(2024屆嘉興基測,11)長度為5的循環(huán)隊(duì)列que,que[0]至que[4]的值依次為'a','b','c','d','e',執(zhí)行如下程序段后,輸出的最后一個字符為　(　　)
n=5;head=0;tail=4
que=['a','b','c','d','e']
while head!=tail:
　　if head%4==0:
　　　print(que[head])
　　else:
　　　tail=(tai1+1)%n
　　　que[tail]=que[head]
　　head=(head+1)%n
print(que[head])
A.b　　　B.c　　　C.d　　　D.e
答案　B　
7.(2024屆發(fā)展共同體聯(lián)考,9)某種特殊的隊(duì)列Q,支持以下三個操作:
操作Q1:若隊(duì)列非空,隊(duì)首元素出隊(duì),并輸出;
操作Q2:若隊(duì)列非空,隊(duì)首元素出隊(duì);
操作Q3:一個元素入隊(duì)。
以上任意一種操作后,若隊(duì)列非空,新的隊(duì)首元素仍為隊(duì)列中所有元素的最小值。
若隊(duì)列Q初始狀態(tài)為空,依次進(jìn)行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后,下列說法正確的是(　　)
A.當(dāng)前隊(duì)列中的元素個數(shù)為2
B.輸出的元素個數(shù)為2
C.第一個輸出的元素肯定比當(dāng)前隊(duì)首元素大
D.隊(duì)列初始狀態(tài)是不是空對輸出結(jié)果有影響
答案　D　
8.(2024浙江1月選考,8,2分)棧S從棧底到棧頂?shù)脑匾来螢?,2,3,隊(duì)列Q 初始為空。約定:U 操作是指元素出棧后入隊(duì),H 操作是指元素出隊(duì)后再入隊(duì)。經(jīng)過UUHU系列操作后,隊(duì)列中隊(duì)首到隊(duì)尾的元素依次為(　　)
A.2,1,3　　　B.3,1,2　　　C.1,3,2　　　D.2,3,1
答案　D　
9.(2024浙江1月選考,9,2分)數(shù)組元素a[0]至a[n-1]依次存放著n個數(shù)據(jù),現(xiàn)需要將元素a[n-1]插入在下標(biāo)為x(0≤xtemp=a[n-1]
for i in range(n-2,x-1,-1):
　　　　　　　　
a[x]=temp
A.a[i+1]=a[i]　　　　B.a[i-1]=a[i]
C.a[i]=a[i+1]　　　　D.a[i]=a[i-1]
答案　A　
10.(2024屆發(fā)展共同體聯(lián)考,11)有如下程序段:
s=[' ']*len(a)
head=2;q=head;top=-1
while q!=-1:
　　top+=1
　　s[top]=a[q][0]
　　q=a[q][1]
print(s[top-2])
若a=[['a',3],['b',0],['c',1],['d',-1]],則輸出的結(jié)果為(　　)
A.a　　　B.b　　　C.c　　　D.d
答案　B　
11.(2024屆強(qiáng)基聯(lián)盟聯(lián)考,11)有如下Python程序段:
s=input()
stack=[0]* len(s);top=-1;presign='+';num=0
for i in range(len(s)):
if '0'<=s[i]<='9':
　　num=num*10+int(s[i])
if i==len(s)-1 or s[i] in '+-*/':
　　if presign=='+':
　　　　top+=1
　　　　stack[top]=num
　　elif presign=='-':
　　　　top+=1
　　　　stack[top]=-num
　　elif presign=='*':
　　　　top+=1
　　　　stack[top]=stack[top-1]*num
　　else:
　　　　top+=1
　　　　stack[top]=stack[top-1]
//num
　　presign=s[i]
　　num=0
print(sum(stack))　　#sum函數(shù)對stack中所有元素求和
若輸入'5*4-6+10/3',程序運(yùn)行后,輸出的結(jié)果是(　　)
A.32　　　B.24　　　C.17　　　D.8
答案　A　
12.(2023浙江1月選考,15,9分)有2組器件共n個,要用一臺檢測設(shè)備檢測。每個送檢器件的信息包含送達(dá)時間、檢測時長和優(yōu)先級。優(yōu)先級有m(1編寫程序模擬檢測過程,先合并2組器件的數(shù)據(jù),然后計算所有器件的平均等待時長,其中每個器件等待時長為其開始檢測時間與送達(dá)時間的時間差。(時間單位均為秒)
請回答下列問題:
(1)由題意可知,圖中器件A、B、C、D的檢測順序?yàn)锳—C—D—B,A、C、D的等待時長分別為0、1、0,B的等待時長是　　　　。
送達(dá)時間 檢測時長 優(yōu)先級
A 0 3 2
B 1 1 2
C 2 1 1
D 4 3 0
11 3 2
12 2 2
(2)定義如下merge(lst1, lst2)函數(shù),參數(shù) lst1和 lst2的每個元素由送達(dá)時間、檢測時長和優(yōu)先級3項(xiàng)構(gòu)成,lst1和 lst2均已按送達(dá)時間升序排列。函數(shù)功能是將lst2中的元素合并到lst1中,并將 lst1按送達(dá)時間升序排列,函數(shù)返回lst1。
def merge(lst1,lst2):
　　i=len(lst1)-1
　　j=len(lst2)-1
　　for t in range(len(lst2)):
　　　lst1.append([0,0,0])　　#為lst1追加一個元素[0,0,0]
　　k=len(lst1) -1
while j >=0:
　　　if i >=0 and lst1[i][0]>lst2[j][0]:
　 lst1[k]=lst1[i]
i -=1
　　　else:
lst1[k]=lst2[j]
j -=1
　　　k -=1
　return lst1
①調(diào)用merge(lst1,lst2)函數(shù),若lst1為[[0,3,2],[1,1,2],[12,2,2]],lst2為[[2,1,1],[4,3,0], [11,3,2]],則while語句中循環(huán)體的執(zhí)行次數(shù)是　　　　。
②若函數(shù)中 while語句的條件“j>=0”誤寫為“k>=0”,會導(dǎo)致某些情況下無法得到符合函數(shù)功能的結(jié)果。調(diào)用merge(lst1, lst2)函數(shù),下列4組數(shù)據(jù)中能測試出這一問題的是　　　　(單選,填字母)。
A.lst1=[[0,3,2],[4,3,0]]
lst2=[[1,1,2]]
B.lst1=[[1,1,2]]
lst2=[[0,3,2],[4,3,0]]
C.lst1=[[1,1,2],[4,3,0]]
lst2=[[0,3,2]]
D.lst1=[[4,3,0]]
lst2=[[0,3,2],[1,1,2]]
(3)實(shí)現(xiàn)模擬檢測過程并計算平均等待時長的部分Python程序如下,請在劃線處填入合適的代碼。
def proc(data,m):
　　n=len(data)
　　queinfo=[]
　　for i in range(m):
　　　queinfo.append([-1, -1])
# queinfo追加一個元素[-1,-1]
　　for i in range(n):
data[i].append(-1)　　# data[i]追加一個元素-1
　　curtime=0
waitnum=0
i=0
　　①　　
while i < n or waitnum > 0:
　 if i < n and data[i][0] <=
curtime:
　　　k=data[i][2]
　　　if queinfo[k][0]==-1:
　　　　　queinfo[k][0]=i
　　　else:
　　　　　　　②　　
　　　　　data[p][3]=i
　　　queinfo[k][1]=i
　　　waitnum+=1
　　　i+=1
　　elif waitnum >0:
k=0
while queinfo[k][0]==-1:
　　k+=1
p=queinfo[k][0]
total+=curtime-data[p][0]
curtime+=data[p][1]
　　③　　
waitnum -=1
　　else:
　　　 curtime=data[i][0]
return total / n
'''
讀取2組器件的數(shù)據(jù),分別存入列表data1和 data2中。2個列表的每個元素包含3個數(shù)據(jù)項(xiàng),分別對應(yīng)器件的送達(dá)時間、檢測時長和優(yōu)先級。data1和 data2中的數(shù)據(jù)已分別按送達(dá)時間升序排列,代碼略
讀取優(yōu)先級等級個數(shù)存入m,代碼略
'''
data=merge(data1, data2)
print(proc(data, m))
答案　(1)6或6秒　(2)①4　②A　(3)① total=0或其他等價表達(dá)式　②p=queinfo[k][1]或其他等價語句　
③queinfo[k][0]=data[p][3]或其他等價語句
13.(2023浙江6月選考,15,9分)某工程包含n個任務(wù)(編號為0~n-1),每天可以有多個任務(wù)同時進(jìn)行。某些任務(wù)之間有依賴關(guān)系,如圖a所示,任務(wù)4依賴于任務(wù)1,任務(wù)1依賴于任務(wù)2。即任務(wù)2完成后才可以開始任務(wù)1,任務(wù)1完成后才可以開始任務(wù)4。不存在一個任務(wù)依賴于多個任務(wù),或多個任務(wù)依賴于同一個任務(wù)的情況。
現(xiàn)已對該工程的依賴關(guān)系進(jìn)行了梳理,結(jié)果如圖b所示,標(biāo)記“T”表示依賴關(guān)系需保留,標(biāo)記“F”表示依賴關(guān)系需刪除。
根據(jù)每個任務(wù)完成所需的天數(shù)和梳理后的依賴關(guān)系,編寫程序,首先刪除標(biāo)記為“F”的依賴關(guān)系,然后計算工程最快完成所需的天數(shù),并以工程最快完成所需的天數(shù)為期限,計算每個任務(wù)最晚必須開始的時間。
任務(wù)A 任務(wù)B 標(biāo)記
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任務(wù)A依賴于任務(wù)B
圖b
請回答下列問題:
(1)若某工程有6個任務(wù),任務(wù)間依賴關(guān)系如圖a所示,完成任務(wù)0~5所需天數(shù)分別為2,1,3,5,1,6,則工程最快完成需要　　天。
(2)定義如下erase(lst)函數(shù),參數(shù) lst列表的每個元素表示一個依賴關(guān)系。函數(shù)的功能是刪除標(biāo)記為“F”的依賴關(guān)系,返回保留的依賴關(guān)系的個數(shù)。
def erase(lst):
　　i=0
　　j=len(lst)-1
　　while i<=j:
　　　　if lst[i][2]=='T':
　　　　　　i+=1
　　　　else:
　　　　　　if lst[j][2]=='T':
lst[i]=lst[j]
i+=1
　　　　　　j-=1
　　return i
若lst列表依次存儲圖b所示的依賴關(guān)系,如 lst[0]為[0,5,'T'],調(diào)用erase(lst)函數(shù),則語句“l(fā)st[i]=lst[j]”的執(zhí)行次數(shù)為　　。
(3)實(shí)現(xiàn)上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
def proc(n,lst,task):
pr=[0]*n
w=[0]* n　　# w[i]存放任務(wù)最晚必須開始的時間
m=erase(lst)
for i in 　　①　　:
task[lst[i][1]][1]=lst[i][0]
pr[lst[i][0]]=1
c=[]
days=0　　# days存放工程最快完成所需的天數(shù)
for i in range(n):
if pr[i]==0:
　　k=i
　　s=0
　　while k!=-1:
　　　　c.append(k)
　　　　s+=task[k][0]
　　　　　　②　　
　　if s > days:
　　　　days=s
for i in range(n-1,-1,-1):
k=c[i]
if task[k][1]==-1:
　　w[k]=days-task[k][0]+1
else:
　　　　③　　
#輸出days,以及保存在w中的每個任務(wù)最晚必須開始的時間,代碼略
"'
工程包含的任務(wù)數(shù)存入變量n
任務(wù)間的依賴關(guān)系存入lst列表
lst[0]包含3項(xiàng),任務(wù)lst[i][0]依賴于任務(wù)lst[i][1],lst[i][2]存放保留/刪除標(biāo)記,任務(wù)數(shù)據(jù)存入task列表
task[i]包含2項(xiàng),task[i][0]為完成任務(wù)所需天數(shù),task[i][1]的初值為-1
代碼略
"'
proc(n,lst,task)
答案　(1)8　(2)1　(3)① range(m)或 range(0, m)或 range(0, m ,1) 或 range (m -1,-1,-1)或 range(erase (lst))或 range(0, erase (lst))或 range(0, erase (lst),1)或 range(erase (lst)-1,-1,-1)　② k=task [k][1]　
③ w [k]=w [task [k][1]]- task [k][0]或 w [k]=w [c [i+1]]- task [k][0]或其他等價答案(這里面可以把 k 換成 c[i])
14.(2024屆Z20聯(lián)盟聯(lián)考,15)小明同學(xué)去看病,當(dāng)他在一位醫(yī)生的診室門口等待就診的時候,發(fā)現(xiàn)了叫號系統(tǒng)的頁面上有兩行病人名單。第一行名單為正常排隊(duì)等待就診的序號,第二行名單為過號或檢后再診而等待的序號。叫號的規(guī)則是先在第一行叫2個就診序號,再到第二行叫1個就診序號。小明同學(xué)回家后將剛才發(fā)現(xiàn)的叫號規(guī)則編寫了Python程序。效果如圖所示:
圖①:當(dāng)前到來的就診序號是3號,為過號或檢后再診序號,進(jìn)入第二行,先到達(dá)先就診。
圖②:當(dāng)前到來的就診序號是4號,為過號或檢后再診序號,進(jìn)入第二行。
圖③:當(dāng)前到來的就診序號是16號,為正常排隊(duì)等待就診的序號,進(jìn)入第一行,按就診序號順序排列。
圖④:開始叫號,按照正常排隊(duì)等待就診叫號2位,過號或檢后再診叫號1位,得到新的順序。
(1)請在劃線處填入合適的代碼。
(2)加框處的代碼有誤,請改正。
def output(head, a, b):
p=head
head_b=0; tail_b=len(b)
while p!=-1:
　　print(a[p][0], end="->")
　　p=a[p][1]
print()
while head_b!=tail_b:
　　print(b[head_b], end="->")
　　head_b+=1
print()
def insert(data,a,b):　　#根據(jù)掛號的序號分別進(jìn)入第一行名單或第二行名單
　 head_a=a[0][0]
　 if data>　　①　　:
　　　p=0
　　　a.append([data,-1])
　　　while p!=-1:
　　　　　if data<=a[p][0]:
　　　　　　　a[-1][1]=p
　　　　　　　a[q][1]=len(a)-1
　　　　　　　break
　　　　　else:
　　　　　　　q=p
　　　　　　　p=　　②　　
　　　if p==-1:
　　　　　a[q][1]=　　③　　
　　　output(0,a,b)
　 else:
　　　b.append(data)
　　　output(0,a,b)
#a、b賦初值,代碼略
#如圖①所示:a=[[13,1],[15,2],[17,-1]];b=[3]
while True:
　　data=int(input("請輸入取號:"))
#輸入0表示停止取號,開始叫號
　　if data==0:
　　　break
　　insert(data,a,b)
print("====開始叫號====")
p=head=0
head_b=0;tail_b=len(b)
while p!=-1 or head_b!=tail_b:
　　if p!=-1 and head_b!=tail_b:
　　　 i=0
　　　 while a[p][1]!=-1:
　　　　　print(a[p][0], end="->")
　　　　　p=a[p][1]
　　　　　i+=1
　　　 print(　　④　　, end="->")
　　　 head_b+=1
　　elif p!=-1 and head_b==tail_b:
　　　 print(a[p][0], end="->")
　　　 p=a[p][1]
　　else:
　　　 print(b[head_b], end="->")
　　　 head_b+=1
答案　(1)①a[0][0]或head_a　②a[p][1]　③len(a)-1
④b[head_b]　(2)i<2 and p!=-1或i<=1 and p!=-1
15.(2022山水聯(lián)盟開學(xué)考,15)小趙同學(xué)在某游戲平臺中獲得虛擬的食物、裝備、材料等物品,它們分別有不同的價值,現(xiàn)游戲平臺有兌換機(jī)制,即可用多個不同物品換取一個等值的物品(每個物品只能取一樣),下表為小趙同學(xué)已獲得的物品。
序號 物品名稱 數(shù)量 單價
0 靈丹 2 1
1 大力丸 1 2
2 止血草 3 5
3 忘魂花 1 7
4 雄黃 1 9
5 靈山仙芝 5 10
6 梅花鏢 1 15
7 止血草 1 20
目標(biāo)置換物品的價值:35。
已獲得物品價值依次是:1,2,5,7,9,10,15,20。
依次拿取物品序號的方案有:
取序號為[0,1,2,3,7]的物品;
取序號為[0,1,3,5,6]的物品;
取序號為[0,2,4,7]的物品;
取序號為[0,4,5,6]的物品;
取序號為[2,5,7]的物品;
取序號為[6,7]的物品。
如要換取游戲中的物品“破天錘”,需要35個金幣,有多種置換的方式,為方便計算以節(jié)省時間,小趙同學(xué)編寫了如下程序,運(yùn)行界面和代碼如下,請在劃線處填入合適的代碼。
def exchange(t,pricelist):
　　n=len(pricelist)
　　stack=[]
　　i=0
　　num=0
　　while　　　①　　　:
　　　　while t>0 and i　　　　　　if t>=int(pricelist[i]):
stack.append(i)
　　②　　
　　　　　　i+=1
　　　　　　if t==0:
　　　　　　　print("取序號為",stack,"的物品")
num+=1
　　　　if 　　　③　　　:
　　　　　　i=stack.pop()
　　　　　　t+=int(pricelist[i])
　　　　　　④　　　
　　if num==0:
　　　　print("無方案")
m=int(input("目標(biāo)置換物品的價值:"))
price=input("已獲得物品價值依次是:")
p=price.split(",")　#將輸入的內(nèi)容以“,”作分隔,并轉(zhuǎn)換為列表
print("依次拿取物品序號的方案有:")
exchange(m, p)
答案　①stack or i16.(2022名校協(xié)作體聯(lián)考,15)某校軍訓(xùn),需要按照身高由低到高排成n行5列的方陣。某班學(xué)生按照身高(100≤身高<199)由低到高編寫編號并將相關(guān)信息存在圖1所示的“stu.txt”文件中。根據(jù)教官提出的排方陣要求,排成如圖2所示的方陣,方陣各點(diǎn)顯示學(xué)生編號。
　
現(xiàn)有延遲報到學(xué)生歸隊(duì),歸隊(duì)學(xué)生編號延續(xù)該班現(xiàn)有編號依次往后,編寫程序完成下列任務(wù):輸入學(xué)生身高,輸出新的方陣布局圖。例如:輸入學(xué)生身高為168,新的方陣布局圖如圖3所示,學(xué)生在方陣的位置:3,4。
(1)若插入學(xué)生身高為160 cm,根據(jù)圖1及范例,該學(xué)生應(yīng)該在圖2方陣中的　　　行　　　　列。
(2)為實(shí)現(xiàn)上述功能,請?zhí)顚憚澗€處代碼。
f=open("stu.txt","r")
a=[]
line=f.readline().split()
i=1
while line!=[]:
　　a.append([line[0],line[1], i])
　　i+=1
　　line=f.readline().split()
n=len(a)-1
a[n][2]=-1
sg=input("請輸入插入的學(xué)生身高(cm):")
xh=str(len(a))
head=1
p=head;q=head
while　　　①　　:
　　p=q
　　q=a[q][2]
if q==head:
　　　　②　　
　　head=len(a) -1
else:
　　a.append([xh,sg,a[p][2]])
　　a[p][2]=len(a)-1
p=head
m=1
while p!=-1:
　　if m!=5:
　　　　print(a[p][0],end=" ")
　　　　m+=1
　　else:
　　　　print(a[p][0])
　　　　m=1
　　　　　　③　　
答案　(1)1,5　(2)①a[q][1]17.(2022 A9協(xié)作體返校考,15)學(xué)校舉辦了“語文作文現(xiàn)場賽”,參賽同學(xué)成績存儲在文本文件“gra.txt”中,如圖a所示(每一行記錄一位同學(xué)的姓名和成績,以“:”分隔)。陳老師利用Python程序?qū)ψ魑某煽冞M(jìn)行處理,統(tǒng)計出各個分?jǐn)?shù)等級的人數(shù),并輸出結(jié)果。程序運(yùn)行界面如圖b所示。
實(shí)現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。
def cla(x):　#判斷成績等級
　　if x>=50:
　　　return "A"
　　elif x>=40:
　　　return "B"
　　elif x>=30:
　　　return "C"
　　else:
　　　return "D"
gra=[]　#存儲各個整數(shù)型成績
num=[0]*4
f=open("gra.txt")
lines=f.readlines()　#將f對象的數(shù)據(jù)按行存入列表lines中
f.close()　#關(guān)閉文件
for line in lines:　#循環(huán)讀取列表lines 中的每個元素,并做相應(yīng)處理
　　a=line.strip().split(":") #去除結(jié)尾的換行符并以冒號為分隔符進(jìn)行分隔
　　gra.append(　　①　　)
for i in range(len(gra)):　#統(tǒng)計各等級人數(shù)
　　t=　　②　　
　　num[ord(t)-65]+=1
print("成績分布如下: ")
for i in range(len(num)):　#輸出統(tǒng)計結(jié)果
　　print(chr(i+65)+"等級有"+　③　+"人")
答案　①int(a[1])或int(a[-1])　②cla(gra[i])
③str(num[i])
18.(2023七彩陽光開學(xué)考,15)食堂推出的三款特色菜,分別用A、B、C表示,想用投票方式統(tǒng)計出三款菜的受歡迎程度。每位投票者需要將三款菜按喜愛程度從高到低進(jìn)行排列,并投出一票。如圖a所示,小明負(fù)責(zé)將文件“投票.txt”中的選票進(jìn)行統(tǒng)計。第1張選票信息為“A,C,B”,表示投票者認(rèn)為A菜優(yōu)于C菜,C菜優(yōu)于B菜,即A菜也優(yōu)于B菜。他得到如圖b所示的投票情況。對選票進(jìn)行統(tǒng)計,得到三款菜的偏好,如圖c所示,數(shù)據(jù)第一行中的“6”說明有6張選票顯示A菜優(yōu)于B菜,“10”說明有10張選票顯示A菜優(yōu)于C菜,以此類推……將所有投票進(jìn)行統(tǒng)計,再將三款菜的得票數(shù)進(jìn)行求和,按得票數(shù)從高到低排列,分別為A菜16票,B菜11票,C菜12票,即可得到每款菜的受歡迎程度。
　　　　
　　　　
請回答下列問題:
(1)若有四款菜,投票情況如圖d所示,則第2受歡迎的菜為　　　　(填字母)菜。
(2)加框處代碼有錯誤,請改正。
(3)實(shí)現(xiàn)上述功能的 Python程序如下,請在劃線①②③處填入合適的代碼

展開更多......

收起↑