高中信息技術(shù) （高考復(fù)習）七數(shù)據(jù)的組織（習題部分）

專題七數(shù)據(jù)的組織

考點集訓

考點一數(shù)組

1.(2022浙北G2聯(lián)盟期中,15)有如下Python程序段：

importrandom

a=□

foriinrange(10):

a.append(random.randint(1,100))

i=0

whilei<10:

ifi=0:

i=i+l

elifa[i-l]<=a[i]:

①

else:

a[i],a[M]=a[i-l],a[i]

②

print(a)

執(zhí)行該程序段實現(xiàn)了隨機生成一個數(shù)組,并將其元素遞增輸出的功能。劃線處的代碼應(yīng)

該是()

A.①i+=l②i=l

B.Φi-=l②i=l

C.①i+=l②i+=l

D.①i-=l②i-=l

第1頁共58頁

答案A

2.(2022紹興諸暨期中,3)使用列表生成的方式創(chuàng)建數(shù)組代碼如下：

a=[i*i-lforiinrange(10)ifi%2==0]

則數(shù)組元素a[3]的值為()

A.2B.8C.15D.35

答案D

3.(2022紹興諸暨期中,4)設(shè)有一個5×8的二維數(shù)組a,若按行優(yōu)先的順序存儲數(shù)組元素則

元素a[3][5]前面元素的個數(shù)為()

A.21B.22C.29D.37

答案C

4.(2022紹興諸暨期中,13)有如下Python程序段：

a=[[0foriinrange(3)]fbrjinrange(3)]

foriinrange(3):

forjinrange(3):

a[i][j]=i*5+j+l

foriinrange。,3)：

forjinrange(2):

Print(a[j][i],end=〃〃)

程序段執(zhí)行后,輸出的結(jié)果是()

A.2378B.712813

C.2738D.671112

答案C

第2頁共58頁

5.(2022杭州期中,10)下述代碼段用于實現(xiàn)在數(shù)組a中將新數(shù)據(jù)k插入下標為j(0<=j<=8)

的位置：

a=[8,6,12,3,5,7,11,2,10,0]

i=8

whilei>=j:

⑴

⑵

⑶

橫線處的代碼由以下五部分中的三部分組成：

①a[i+l]=k(2)a[i]=k③a[i+l]=a[i]

(4)a[i]=a[i-l]⑤i=i-l

下列選項中代碼選擇且順序正確的是()

A.③⑤②B.⑤③①

C.③⑤①D.④⑤②

答案C

6.(2022嘉興期中,3)用Python程序段定義一個3行4列的二維數(shù)組(要求先將各元素的

值初始化為0,再將第2行第2個元素重新賦值為1),以下程序段可行的是()

A.arr=[[0]*3forjinrange(4)]

arr[2][2]=l

B.arr=[[0]*4]*3

arr[l][l]=l

C.arr=[[0foriinrange(4)]forjinrange(3)]

arr[l][l]=l

第3頁共58頁

D.arr=[[O,O,O,O]forjinrange(3)]

arr[2][2]=l

答案C

考點二鏈表

1.（2022諸暨海亮高中月考⑼有如下程序段：

a=[[2,2,1],[8,0,4],[3,3,0],[6,-1,2],[8,1,-1]]

ans=head=3

p=a[head][2]

whilep!=-l：

ifa[ans][O]<a[p][O]：

ans=p

P=a[p][2]

print（ans,a[ans][O],sep=","）

則程序運行后,下列說法正確的是（）

A.鏈表數(shù)據(jù)值依次為2->8->3->6->8

B.程序輸出結(jié)果為4,8

C.a[0][2]的值為1,雙向鏈表a的頭節(jié)點數(shù)據(jù)值為2

D.a[l][l]的值為0,雙向鏈表a的尾節(jié)點數(shù)據(jù)值為8

答案D

2.（2022浙北G2聯(lián)盟期中,14）用兩個列表a、b分別保存單向鏈表中的數(shù)據(jù)區(qū)域和指針區(qū)

域。如圖所示,在節(jié)點X與節(jié)點y之間插入一個新節(jié)點,操作步驟正確的是（）

第4頁共58頁

head節(jié)點X節(jié)點y

—,,a[x]h[x]a(y]b[y]-*

新節(jié)點

a[i]Ib[i]

head節(jié)點X節(jié)點y

—*a[x]b[x]a[y]?1[y]一

I新產(chǎn)點I

IW]I則I

φb[i]=b[y]②b[i]=b[x]

③b[y]=i?b[x]=i

⑤b[i]=X⑥b[i]=y

A.(3)(6)B.④②C.①③D.②④

答案D

3.（2022紹興諸暨期中,7）在一個單向鏈表（如圖）中,若在尾指針tail所指節(jié)點之后插入新

節(jié)點（r所指節(jié)點）,則執(zhí)行的操作是)

tail

IdataIl∏GXl[~*∣da1a2∣ncxlHdala3∣-1~∣∣data4∣next

A.tail所指節(jié)點的data3值賦為r所指節(jié)點的data4值

B.r所指節(jié)點的next值賦為tail

C.r所指節(jié)點的next值賦為-1

D.tail所指節(jié)點的next值賦為r,r所指節(jié)點的next值賦為-1

答案D

4.（2022紹興諸暨期中,8）使用Python的二維列表來模擬單向鏈表,如下代碼創(chuàng)建一個擁有

4個節(jié)點的鏈表a。

a=[["cat",l],["dog",2],["pig",-l],

["rabbit",。]]

head=3

第5頁共58頁

依次輸出各節(jié)點數(shù)據(jù)域的值,內(nèi)容為（）

A.cat,dog,pig,rabbit

B.pig,rabbit,cat,dog

pig,dog,cat,rabbit

D.rabbit,cat,dog,pig

答案D

5.（2022諸暨期末,8）某單向鏈表如圖所示,在data2與data3之間插入一y新節(jié)點data4（p

指向data2,r指向data4o列表data來記錄鏈表數(shù)據(jù)域,列表next來記錄指針域）,以下選項

中正確的執(zhí)行步驟為（）

φnext[p]=next[r]（2）next[p]=r

（3）next[r]=P（4）next[r]=-1

⑤next[r]=next[p]⑥next[p]=-1

A.③⑥B.⑤②C.①④D.⑤②④

答案B

6.（2022衢州期末,8）在Python中可以使用列表模擬單向鏈表,如鏈表中的節(jié)點p,a[p][0]存

儲p節(jié)點的數(shù)據(jù),a[p][l]存儲p指向后繼節(jié)點的指針。若要在p節(jié)點之后插入新的節(jié)點x（x

作為p的新后繼節(jié)點）,需要執(zhí)行的語句是（）

A.a[p][l]=xJa[x][l]=a[p][l]

B.a[x][l]=a[p][l];a[p][l]=x

C.a[p][0]=x;a[x][0]=a[p][0]

D.a[x][0]=a[p][0];a[p][0]=x

第6頁共58頁

答案B

考點三隊列

1.(2022杭州“六縣九?！逼谥?5)有A、B、C、D、E五個人依次進入電梯,結(jié)果警告超重

了,需要出去一個人才能正常運行,按照數(shù)據(jù)結(jié)構(gòu)中棧和隊列的思維,應(yīng)離開電梯的人分

別是()

A.棧:A隊列:EB.棧:A隊列:A

C.棧:E隊列:AD.棧:E隊列:E

答案C

2.若用一個規(guī)模為8的數(shù)組來實現(xiàn)隊列,已知當前隊尾指針tail和隊首指針head的值分別

為5和0,進行如下操作:①刪除兩個元素;②插入三個元素;③刪除一個元素,操作完成后,

指針head和tail的值分別為()

A.2和7B.3和7

C.3和8D.4和8

答案C

3.用類實現(xiàn)的隊列操作如下：

classQueue():

def^init_(self):

self.queue=∏

defqueue_in(self,data)：

self.queue.insert(O,data)

defqueue_out(self):

iflen(self.queue):

第7頁共58頁

returnself.queue.pop()

return〃隊列已空〃

q=Queue()

q.queue_in(/zapple〃)

q.queuejn(zzorange〃)

print(q.queue_out())

q.queuejn(zzbananazz)

q.queue_in(，zpeach〃)

print(q.queue_out())

程序執(zhí)行后,隊列中的元素為

AA.〃appl[e〃,〃orange〃Br.>〃orange〃,〃peachL〃

C.apple,bananaD.banana,peach

答案D

4.(2022"山水聯(lián)盟”開學考,11)有如下Python程序代碼:

S=zzABCDEFzzJhead=Ojtail=O

que=[z/,z]*100

foriinrange(len(s)):

ifi%2=0:

quc[tail]=s[i]

else：

que[tail]=s[len(s)-i]

tail=tail÷l

第8頁共58頁

foriinrange（len（s））:

print（que[head],end=,z〃）

head=head+l

以上程序運行后,打印出列表的情況是：（）

A.ABCDEFB.FEDCBA

C.ACEFDBD.AFCDEB

答案D

5.（2023浙江1月選考,9,2分）有1個隊列,隊首到隊尾的元素依次為8,3,2,9,5o約定:T操

作是指隊列中1個元素出隊后再入隊,Q操作是指隊列中1個元素出隊。則經(jīng)過TTTQTTQ

系列操作后,隊列中隊首到隊尾的元素依次為（）

A.2,9,5B.2,5,8

C.5,8,2D.8,3,2

答案B

6.小明在使用隊列解決問題的過程中,初始時（空隊列）,隊列的隊首指針head=。,隊尾指針

tail=。,經(jīng)過一系列入隊、出隊操作后,head=4,tail=70在不考慮隊列溢出的情況下,小明接

下來進行的操作序列為出隊、入隊、出隊、出隊、入隊、出隊,此時head和tail的值分

別為和O

答案8;9

考點四棧

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

第9頁共58頁

C.6、5、7、9、3、8

D.5、9、6、3、7、8

答案D

2.（2022嘉興期中,2）有一入棧序列為“ABCD”,下面以“C”開頭的出棧序列中不正確的是

（）

A.CABDB.CBAD

C.CBDAD.CDBA

答案A

3.（2022紹興諸暨期中,5）下列有關(guān)棧和隊列說法,正確的是（）

A.棧的特點是先進先出,隊列的特點是先進后出

B.棧只能在一端進行插入,在另一端進行刪除

C隊列限定僅能在一端進行插入和刪除操作

D.棧和隊列均為操作受限的線性表

答案D

4.（2022紹興諸暨期中,6）若用1表示進棧操作,用0表示出棧操作,某元素的進棧順序是

/皿03門為了得到出棧序列飛亞11廠,則應(yīng)進行的操作序列為（）

A.1101010100B.1110010100

C.1110011000D.1110100100

答案B

5.（2022Z20名校聯(lián)盟,10）某算法利用“?！彼枷脒M行字符串處理,其步驟如下:①創(chuàng)建長度

為n的空棧,字符依次入棧;②當達到棧滿狀態(tài)或數(shù)據(jù)全部入棧時,字符依次出棧,按照出

棧順序連接成新字符串:③若還有未處理的字符,則重復(fù)步驟①②,直到全部字符處理完

畢。實現(xiàn)該功能的Python程序如下：

第10頁共58頁

s=input(〃請輸入字符串:〃)

n=5；st=[，/z]*n

top=-l；i=0；m=，/z/

whilei<len(s):

while(1)andi<len(s):

⑵

st[top]=s[i]

i+=l

whiletop!=-l:

m+=st[top]

⑶

Print(“密文：”,m)

加框處⑴⑵⑶的代碼由以下代碼組成：

①top-=l②tof>+=l③top+l<n④top<n

下列選項中代碼順序正確的是

A.④②①B.③①②

C.③②①D.④①②

答案C

6.(2022諸暨海亮高中月考,10)有如下程序段:

bt=r'A","B'',"C'',"D",None,"E","F"]

result=∏

Stack=O

i=0

第11頁共58頁

whilestackor(i<len(bt)andbt[i]isnotNone):

ifi<len(bt)andbt[i]isnotNone：

stack.append(i)

i=2*i+l

else：

i=stack.pop()

result.append(bt[i])

i=2*i+2

print(,-,z.join(result))

則程序運行后輸出的結(jié)果為

A.A-B-D-C-E-FB.D-B-E-F-C-A

C.D-B-A-E-C-FD.A-B-C?D-E?F

答案C

7.(2023浙江1月選考,12,2分)有如下PythOn程序段:

importrandom

a=['A,,,B,,,?,,,?,,,C,,,D,,,?,]

stk=[O]*len(a);top—1

foriinrange(len(a)):

op=random.randint(0,1)#隨機生成0或1

ifop=landa[i]K#'：

top+=l；stk[top]=a[i]

a[i]=?,

elifop==0andtop!=-landa[i]≈,#':

第12頁共58頁

a[i]=stk[top]；top-=l

執(zhí)行該程序段后,a的值不可能是（）

A.fA,,,B,,,?,∕?,,,C,,,D,,,?,]

B.[,

C.[,

D.[,,'A','B','C','

答案D

8.（2023浙江1月選考,15,9分）有2組器件共n個,要用一臺檢測設(shè)備檢測。每個送檢器件

的信息包含送達時間、檢測時長和優(yōu)先級。優(yōu)先級有m（l<m<6）個等級,由高到低分別用

0~m-l的整數(shù)表示。每個器件的送達時間各不相同。已送達的器件按照各優(yōu)先級通道分

別排隊,先到達先入隊。設(shè)備每次檢測都從當前各非空隊列中,選取優(yōu)先級最高的隊列的

隊首器件出隊進行檢測。（同一時刻出現(xiàn)入隊和出隊時,先處理入隊。）

編寫程序模擬檢測過程,先合并2組器件的數(shù)據(jù),然后計算所有器件的平均等待時長,其中

每個器件等待時長為其開始檢測的時間與送達時間的時間差。（時間單位均為秒）

請回答下列問題：

⑴由題意可知,圖中器件A、B、C、D的檢測順序為A-C-D-B1AsC、D的等待時

長分別為0、1、O,B的等待時長是O

送達時間檢測時長優(yōu)先級

O32

112

211

43O

1132

第13頁共58頁

1222

⑵定義如下merge(lstl,Is⑵函數(shù),參數(shù)IStI和Ist2的每個元素由送達時間、檢測時長和

優(yōu)先級3項構(gòu)成,Istl和lst2均已按送達時間升序排列。函數(shù)功能是將lst2中的元素合并

到IStI中,并將Istl按送達時間升序排列,函數(shù)返回Istlo

defmerge(lstl,lst2):

i=Ien(Istl)-1

j=len(lst2)-1

fortinrange(len(lst2)):

lstl.aρpend([0,0,0])#為Istl追加一個元素[0,0,0]

k=Ien(Istl)-1

whilej>=O:

ifi>=Oandlstl[i][O]>lst2[j][0]:

lstl[k]=Istl[i]

i-=1

else：

Istl[k]=lst2[j]

j-=l

k-=1

returnIstl

①調(diào)用merge(lst1,ls⑵函數(shù),若IStl為[[0,3,2],[l,1,2],[12,2,2]],lst2為[[2,1J,[4,3,0],[11,3,2]],

則while語句中循環(huán)體的執(zhí)行次數(shù)是o

第14頁共58頁

②若函數(shù)中while語句的條件“j>=0”誤寫為“k>=0”,會導致某些情況下無法得到符合函

數(shù)功能的結(jié)果。調(diào)用merge(?stl,IS⑵函數(shù),下列4組數(shù)據(jù)中能測試出這一問題的是

(單選,填字母)。

A.lstl=[[0,3,2],[4,3,0]]

lst2=[[1,1,2]]

B.lstl=[[1,1,2]]

lst2=[[0,3,2],[4,3,0]]

C.lstl=[[1,1,2],[4,3,0]]

lst2=[[0,3,2]]

D.lstl=[[4,3,0]]

lst2=[[0,3,2],[1,1,2]]

(3)實現(xiàn)模擬檢測過程并計算平均等待時長的部分Python程序如下,請在劃線處填入合適

的代碼。

defproc(data,m):

n=len(data)

queinfo=[]

foriinrange(m):

queinfo.append([-l,-1])

#queinfo追加一個元素[-1,-1]

foriinrangc(n):

data[i].appcnd(-l)#data[i]追加一個元素-1

curtime=0

waitnum=0

第15頁共58頁

i=0

①

whilei<norwaitnum>0:

ifi<nanddata[i][O]<=curtime:

k=data[i][2]

ifqueinfb[k][O]=-l:

queinfb[k][O]=i

else:

②

data[p][3]=i

queinfo[k][l]=i

waitnum+=1

i+=1

elifwaitnu?n>0：

k=0

whilequeinfo[k][0]==-1:

k+=l

p=queinfo[k][0]

total+=curtime-data[p][O]

curtime+=data[p][?]

③

waitnum-=1

else：

curtime=data[i][O]

returntotal/n

第16頁共58頁

讀取2組器件的數(shù)據(jù),分別存入列表data）和data2中。2個列表的每個元素包含3個數(shù)

據(jù)項,分別對應(yīng)器件的送達時間、檢測時長和優(yōu)先級。datal和data2中的數(shù)據(jù)已分別按

送達時間升序排列,代碼略

讀取優(yōu)先級等級個數(shù)存入m,代碼略

，，，

data=merge（datal,data2）

print（proc（data,m））

答案（1）6或6秒（2）①4②A⑶①total=0或其他等價表達式（g）p=queinfo[k][l]

或其他等價語句③queinfo[k][0]=data[pM3]或其他等價語句

考點五樹

1.（2022Z20名校聯(lián)盟,11）若一棵二叉樹的中序遍歷序列為BlGDHAECF,后序遍歷序列

為IGHDBEFCA,則該二叉樹的前序遍歷序列為（）

A.ABCDEFGHIB.ABDGHICEF

C.ABDHGICEFD.ABDGIHCEF

答案D

2.（2022諸暨海亮高中月考,8）一棵二叉樹的前序遍歷結(jié)果為JFDECBHAlG,中序遍歷結(jié)

果為DFEJAHBlCG,則該二叉樹的深度為（）

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

答案B

3.（2022名校協(xié)作體,10）已知二叉樹T2的后序遍歷序列為G-D-H-E-B-I-F-C-A,中序遍歷

序列為D-G-B-E-H-A-C-I-F,則二叉樹T2的前序遍歷序列為（）

A1A-B-D-G-E-H-C-I-F

BA-B-D-G-E-H-C-F-I

第17頁共58頁

C-A-B-D-G-E-H-F-C-I

D.該二叉樹形態(tài)不唯一,無法確定

答案B

4.（2022紹興諸暨期中,9）已知一棵二叉樹的前序遍歷為ABDECFG,中序遍歷為

DBEAFCG,則該二叉樹的后序遍歷序列為（）

A.DEBAFGCB.DEBFGCA

C.DBEGFCAD.DBEFGCA

答案B

5.（2022諸暨期末,9）一棵度為3,深度為4的樹,最多有個節(jié)點。（）

A.31B.32C.40D.42

答案C

6.（2022諸暨期末,10）設(shè)一棵二叉樹的中序遍歷序列為beefad,后序遍歷序列為efcbda,則

二叉樹前序遍歷序列為（）

A.abcdefB.bdaefcC.abceftiD.abcfed

答案C

7.（2023浙江1月選考,8,2分）下列二叉樹中,中序遍歷結(jié)果為BAEDFC的是（）

考點六大數(shù)據(jù)時代的數(shù)據(jù)的組織

L下面的系統(tǒng)中,屬于實時查詢系統(tǒng)的是（）

第18頁共58頁

A.某學校的學生學籍管理系統(tǒng)

B.某航空公司的在線訂票系統(tǒng)

C.某廣告公司的計算機輔助設(shè)計系統(tǒng)

D.某印刷廠的計算機激光排版系統(tǒng)

答案B

2.大數(shù)據(jù)背景下的數(shù)據(jù)組織和存儲方式,通常采用的技術(shù)是

A.傳統(tǒng)存儲系統(tǒng)

B.云存儲系統(tǒng)

C.分布式存儲系統(tǒng)

D.集中式存儲系統(tǒng)

答案C

3.下列方法中,不熊有效提升內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)處理性能的是

A.處理的數(shù)據(jù)保存在內(nèi)存中并直接操作

B.增加對磁盤的數(shù)據(jù)讀寫

C.對數(shù)據(jù)進行分級,并在處理器緩存中存儲

D.采用改進后的數(shù)據(jù)結(jié)構(gòu)來組織、存儲數(shù)據(jù),如跳躍表、平衡樹

答案B

4.下列關(guān)于實時查詢數(shù)據(jù)系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)的說法,于耳噂的是

A.在實時查詢系統(tǒng)中使用數(shù)組,時效性較差

B.在鏈表中查找數(shù)據(jù)時效性較高,插入數(shù)據(jù)時效性較低

C.跳躍表基于有序鏈表

D.跳躍表通過跨區(qū)間、跳躍性的比較,避免了依次比較,提高了效率

第19頁共58頁

答案B

5.有如下跳躍表:

若要在原鏈表中插入元素7,則數(shù)據(jù)元素需要比較的次數(shù)為

A.lB.3C.4D.5

答案B

6.下列關(guān)于Hadoop的說法,下年唧的是()

A.Hadoop是一種超大規(guī)模,高可靠性,高可擴展性的數(shù)據(jù)庫

B-Hadoop是Googlc云計算技術(shù)的開源實現(xiàn)

C.使用Hadoop可以在POl數(shù)據(jù)的處理中獲得更方便的體驗和更低廉的成本

D.Hadoop可以對海量地理信息進行處理和計算

答案A

專題集訓

1.（2022嘉興期中,1）以下數(shù)據(jù)結(jié)構(gòu)中,不屬于線形結(jié)構(gòu)的是（）

A.數(shù)組B.鏈表C.隊列D.樹

答案D

2.（2023屆十校聯(lián)盟10月聯(lián)考,10）要解決不同的實際問題,需要根據(jù)實際需要選擇不同的

數(shù)據(jù)結(jié)構(gòu)來組織數(shù)據(jù)。下列說法正確的是（）

A.一個有底的玻璃筒只能在開放的一端放取乒乓球,符合隊列的特性

B.火車站或者飛機場會在電子屏上滾動顯示最近的班次信息,可以采用鏈表組織數(shù)據(jù)

C計算機操作系統(tǒng)中文件夾的管理,通常借助棧來組織、保存和處理數(shù)據(jù)

第20頁共58頁

D.用戶單擊瀏覽器的“后退”按鈕可以回到剛才瀏覽過的網(wǎng)頁,通常采用樹結(jié)構(gòu)進行網(wǎng)頁

數(shù)據(jù)的組織

答案13

3.（2023屆嘉興基測,9）下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法,正確的是（）

A.常見的線性關(guān)系數(shù)據(jù)結(jié)構(gòu)有數(shù)組、隊列、棧、樹和圖等

B.數(shù)組和鏈表在操作時,其存儲空間固定不變

C鏈表在訪問、插入和刪除元素時,算法效率比數(shù)組高

D.棧是一種先進后出的線性表結(jié)構(gòu)

答案D

4.（2023屆浙江名校聯(lián)盟10月聯(lián)考,9）一個棧的輸入序列為“12345”,輸出的第一個元素為

“4”,則輸出的第三個元素不可能是（）

A.lB.2C.3D.5

答案A

5.（2023屆浙江學軍中學10月月考,2）新型冠狀病毒肺炎（CoronaVirusDisease

2019,CoVID-19）,簡稱“新冠肺炎”,是一種傳染性極強的流行病。一旦發(fā)現(xiàn)“新冠肺炎”確

診病例或無癥狀感染者,就要對其進行流行病學調(diào)查（簡稱“流調(diào)”）。調(diào)查期間,充分利用信

息化和公安、工信大數(shù)據(jù)手段,通過病例和無癥狀感染者居?。üぷ鳎┉h(huán)境等現(xiàn)場調(diào)查和定

點醫(yī)院駐點調(diào)查相結(jié)合,查明病例和無癥狀感染者活動軌跡,規(guī)范開展個案調(diào)查、密切接

觸者追蹤和聚集性疫情調(diào)查。

在“新冠肺炎”流調(diào)中,要表示某個患者和其下所有患者的傳染關(guān)系,比較適合的數(shù)據(jù)組織

形式是（）

A.數(shù)組B.隊列C.棧D.樹

第21頁共58頁

答案D

6.（2023屆強基聯(lián)盟10月統(tǒng)測,9）某二叉樹的后序遍歷序列為F—?—?—C—A—D,中序遍

歷序列為F—B—D—E—A—C,則其刖序遍歷序列為)

A.D—B—A—F—E—C

B.D—B—F—A—E—C

C-D-E-F-A-B-C

D.D—E—A—F—B—C

答案B

7.（2023屆浙南名校聯(lián)盟IO月聯(lián)考,11）如果將數(shù)學表達式中的運算數(shù)和運算符視為二叉

樹的每個節(jié)點,那么我們可以構(gòu)造出各種表達式二叉樹,下圖是一棵表達式二叉樹。如果

對該二叉樹進行中序遍歷,并加上括號后,就可以得到中綴表達式：（9-4/2）*5+3。如果對該

二叉樹實行前序遍歷,則可以得到的表達式為)

A.+*-9∕4253B.+*-∕42953

C.942∕-*53+D.942∕-5*3+

答案A

8.（2023屆百師聯(lián)盟聯(lián)考,3）公交車上有時候會出現(xiàn)人太多無法擠到后門下車而從前門下

車的情況,因此若一個序列在有3個或以下元素時按隊列方式離開序列,但在（3個以上）

第22頁共58頁

元素時按棧方式離開序列,則對于依次進入序列的xl,x2,x3,x4,x5,x6,離開序列的順序可

能為()

A.xl,x4,x6,x2,x3,x5

B.x4,xl,x6,x2,x3,x5

C.xl,x2,x3,x6,x4,x5

D.x6,x5,x4,x3,xl,x2

答案B

9.(2023屆浙江學軍中學10月月考,7)有如下Python程序段：

q,head,tail,ans=[,z〃]*IOO,0,0,〃”

foriinrange(len(s)):

q[tail]=s[i]

tail+=l

whilehead<tail:

ans=ans+q[head]

head+zzl

ifhead<tail:

q[tail]=q[head]

tail+=l

head+=l

pr?nt(ans)

當s的值為字符串〃QUEUE〃時,程序輸出的結(jié)果為()

A.QUEUEB.EUEUQ

C.QEUUED.QEEUU

答案D

第23頁共58頁

10.(2023屆麗湖衢11月質(zhì)量檢測,12)某公交路線的站點名稱、經(jīng)度、緯度和下一個站點

序號(經(jīng)緯度已轉(zhuǎn)換為平面坐標數(shù)據(jù))存儲在數(shù)組a中,現(xiàn)計算相鄰兩個站點距離的總和。

importmath

a=r廊橋”,3,2,3],[“徐在”,6,11,2],[“北門”[3,8,7],[“上通”,3,7[]]

head=0js=0

p=a[head][3]

while(1)：

s÷zzmath.sqrt((a[p][l]-a[head][l])**2+(a[p][2]-a[head][2])**2)

⑵

⑶

print(s)

上述程序段劃線處可選的代碼為：

①a[head][3]!=7②head=P

③p=a[head][3]④head!=-1

貝IJ⑴、(2)、⑶處的代碼依次為()

A.①②③B.④②③

C.④③②D.①③②

答案A

11.(2023屆浙南名校聯(lián)盟10月聯(lián)考,12)有如下Python程序段：

deftravel(lnk,head)：

p=hcad

〃〃

S=

whileφ：

第24頁共58頁

s+=Str(Ink[p][0])+〃-〉〃

p=lnk[p][l]

s+=str(lnk[p][O])

print(s)

user=[[7,2],[15,0],[5,3],[l,-l]]

head=l

nuπι=int(input(〃請輸入一yIk整數(shù):〃).strip())

p=head

ifhead--1ornum>user[p][O]:

user,append([num,head])

head=len(user)-l

else:

whileuser[p][l]!=-land(g):

p=user[p][l]

user,append([num,user[p][1]])

③

travel(user,head)

若要實現(xiàn)下圖所示的功能,則①②③處應(yīng)填入的語句依次為

請輸入一個整數(shù)：6

15->7->6->5->l

A.①lnk[p][l]!=T

②num<=user[p][O]

③USer[p][l]=Ien(USer)T

B.①lnk[p][邛=T

第25頁共58頁

②num〈=USer[user[p][l]][O]

(3)user[p][l]=len(user)-l

C.①p!=T

②num〈二USer[user[p][l]][O]

(3)user[p][l]=len(user)-l

D.①p!=T

②num<=uSeHP][0]

③USer[p][l]=Ien(USer)

答案B

12.(2022紹興魯迅中學期中,12)有如下Python程序段：

a=[[3,2],[2,3],[7,l],[l,0]]

p=head=O

whilea[p][l]!=head:

print(a[p][O],end="->〃)

print(a[p][O])

上述程序段要遍歷鏈表中的所有元素,劃線處應(yīng)添加的代碼是

A.p+=1

B.a[p][l]+=1

C.p=a[p][l]

D.a[p][l]=a[a[p][l]][l]

答案C

第26頁共58頁

13.（2022浙江開學考,9）有如圖所示的二叉樹,關(guān)于此二叉樹的說法中,描述正確的是

A.該二叉樹的前序遍歷為ABDGJCEFHI

B.該樹中共有3個葉子節(jié)點

C若有前序遍歷和后序遍歷可以推導出唯一的二叉樹

D.該樹的深度是4

答案A

14.（2022浙江開學考,10）已知一個鏈表a,其a[i][0]存儲索引i下節(jié)點的數(shù)據(jù)區(qū)域,a[i]山存

儲索引i下節(jié)點的指針區(qū)域。對于當前鏈表中的一個節(jié)點p（索引為p）,若要刪除p的后一

個節(jié)點q（q=a[p][l]）,則應(yīng)執(zhí)行語句（）

A?a[p]=a[q]

B.a[p][l]=a[q][l]

C.a[p]=a[a[q][l]]

D.a[p]=a[q]ja[p][l]=a[q][l]

答案B

15.（2022杭州期中,12）在Python中用列表模擬鏈表結(jié)構(gòu),某程序段如下：

a=[fH,,l],[,a,2],[,n,3],[,g,,4],Γ2',5],['0',6],['2',7],['2',0]]

p,head=3,3；q,c=-l,0；m,n=3,0

whilen<4:

第27頁共58頁

c=c÷l

ifc=m：

n=n+l;C=O

ifp==head:

head=a[p][l]

a[q][l]=head

P=a[p][l]

else:

a[q][l]=a[p][l]

P=a[p][l]

else：

q=p

P=a[p][l]

#從頭節(jié)點開始遍歷鏈表a邏輯順序的所有節(jié)點,并依次輸出節(jié)點的數(shù)據(jù),代碼略

該程序段執(zhí)行后的輸出結(jié)果為

A.ng02B.g02nC.2an2D.22an

答案D

16.(2022七彩陽光返?？?12)有如下Python程序段：

s=input('請輸入一串小寫字母')

head=O;tail=O;top=-l

sl=[zz,,]*((len(s)+l)∕∕2)

s2=[z,,,]*(len(s)∕∕2)

foriinrange(len(s)):

第28頁共58頁

ifi%2=0:

s![tail]=s[i]

tail+=1

else：

top+=1

s2[top]=s[i]

〃〃

x=

whilehead<tailandtop>-1:

x=s1[head]÷x

head+=l

x=x÷s2[top]

top-=l

print(x)

執(zhí)行該程序段,輸入字符串“abcdef?”,則輸出的結(jié)果是()

A.acegbdfB.acegfidb

C.gecafdbD.ecafdb

答案D

17.(2022諸暨海亮高中月考,18)有個火車站的鐵軌調(diào)度方法如下:火車從一方1,2,3,4…依

次進入,由于每個火車皮要去的目標車站不一樣,想讓車皮到站后能以最少的時間從火車

上脫離,就讓最近到的車皮放在整列火車的最后。因此需要轉(zhuǎn)換站來達成這樣的目標,轉(zhuǎn)

換站只能在同一個地方進與出。例如有四個車皮1,2,3,4進入24,3,1到站,即2號車皮目

的地最遠,4號車皮倒數(shù)第二遠,3號車皮倒數(shù)第三遠,1號車皮最近。

為了能快速指揮車輛進出站轉(zhuǎn)換,小王編寫了如下程序：

a=[l,2,3,4,5,6]#待進站車皮

第29頁共58頁

b=[3,2,l,6,5,4]#出站順序

stack=[O]*len(a)

top=0

stack[top]=a[0]

S=Str(a[0])+〃進〃

ha=l；hb=0

whiletop>-landhb<len(b):

whiletop>-landφ：

s=s+str(stack[top])+z，出〃

top-=l

②

ifha<len(a):

top+=l

stack[top]=a[ha]

s=s+str(a[ha])+“進〃

ha+=l

elifha==len(a)andtop>-land③：

Print(〃無法調(diào)度〃)

break

iftop=-l:

print(s)

代碼顯示結(jié)果：1進2進3進3出2出1出4進5進6進6出5出4出。

⑴修改加框處代碼O

⑵將劃線處代碼補充完整,使功能完善。

第30頁共58頁

答案（l）top>-landhb<=len（b）⑵①StaCk[top]==b[hb]②hb+=l③stack[top]!=b[hb]

18.（2022浙北G2聯(lián)盟期中,16）小明來到探險島尋寶,島上共有N個寶藏（標號為0至N-1）。

每個寶藏有一條路連接下一個寶藏,寶藏號和下一個寶藏號使用鏈表存儲。小明想知道,

從其中一個寶藏出發(fā),最多可以找到多少個寶藏。

例如，共有5個寶藏,輸入“1,3,4,4,1,”表示0-4各寶藏點連接的下一個寶藏依次

是:1,3,4,4,1（如下表）。則最多可以找到4個寶藏,路徑為：0號→1號―3號-4號。

寶藏號01234

下一個寶藏號13441

程序代碼如下：

s=input（”請輸入寶藏連接的情況：”）

t=0jc=""ja=[]

foriins:

ifi!=T:

c+=i

else:

a.append([t,i∏t(c)])

〃〃

C=

①

max=0

forheadinrange(0,t):#枚舉尋找寶藏起點

g=[]

p=head

whilepnoting：

第31頁共58頁

g.append(p)

②

iflen(g)>max:

③

print(max)

⑴若有4個寶藏,且每個寶藏的連接情況為20,0」,那么小明最多可以挖到的寶藏數(shù)

是O

(2)請將代碼補充完整。

答案(1)4⑵①t+=l②p=a[p][l]③maX=Ien(g)

19.(2022杭嘉湖金月考,15)山頂上有10個圓形排列的洞,一只狐貍和一只兔子各住一個

洞。狐貍總想吃掉兔子。一天兔子對狐貍說:“你想吃我有一個條件,先把洞從1-10編上

號,你先到1號洞找我;第二次隔1個洞(即3號洞)找我,第三次隔2個洞(即6號洞)找我,

依此類推,次數(shù)不限。但狐貍從早到晚進進出出了IoOo次,仍沒有找到兔子。請問兔子可

能躲在哪個洞里？

實現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。

hole=[]

n=10

m=1000

#構(gòu)造一個循環(huán)鏈表,并給n個洞編號,設(shè)置洞的初始標志為0

#鏈表的節(jié)點樣式為:[洞的標志,洞的編號]

foriinrange(n-l):

hole.appcnd([0,i+l])

ω

第32頁共58頁

#狐貍開始找兔子,將進入過的洞標志改為1,尋找m次結(jié)束

head=O

k=head

hole[0][0]=l

foriinrange(l,m):

forjinrange(l,i+2):

(2)

hole[k][0]=l

#輸出標志仍為0的洞,即兔子可能藏身地點

foriinrange(len(hole)):

ifhole[i][0]=0:

Print("兔子可能躲在第"+⑶+”號洞")

答案(1)hole.append([0,0])

(2)k=hole[k][l](3)str(i+l)

20.(2022紹興魯迅中學期中,15)編程輸出一個考場30個考生的座位號,座位號要求S型

排列如圖。

11224

211142326

310152227

49162128

58172029

61830

說明:f{a[i][∏2}'可以將i行j列的數(shù)格式化為2個字符的格式,如果是一位數(shù),在這一位

數(shù)前加空格。

實現(xiàn)上述功能的Python程序如下,請在劃線處填入合適的代碼。

第33頁共58頁

defsxing(n,m):#考場座位n行,m列

a=[[①]forjinrange(n)]

s=l

foriinrange(m):

ifi%2=0:

forjinrange(n):

②

s+=l

else:

forjinrangc((3))：

a[j][i]=s

s÷=l

returna

n,m=6,5

a=sxin虱n,m)

foriinrange(n):#輸出座位示意圖

st=〃〃

forjinrange(m):

st=st+"〃+F{a[i][j]^},

print(st)

答案①0foriinrange(m)②a[j][i]=s③n-1,-1,-1

21.(2022山水聯(lián)盟開學考,15)小趙同學在某游戲平臺中獲得虛擬的食物、裝備、材料等

物品,它們分別有不同的價值,現(xiàn)游戲平臺有兌換機制,即可用多個不同物品換取一個等

值的物品(每個物品只能取一樣),下表為小趙同學已獲得的物品。

第34頁共58頁

序號物品名稱數(shù)量單價

0靈丹21

1大力丸12

2止血草35

3忘魂花17

4雄黃19

5靈山仙芝510

6梅花鏢115

7止血草120

目標置換物品的價值：35。

已獲得物品價值依次是:1,2,5,7,9,10,15,20。

依次拿取物品序號的方案有：

取序號為［0,1,2,3,刀的物品；

取序號為［0,1,3,5,6］的物品；

取序號為［0,2,4,7］的物品；

取序號為［0,4,5,6］的物品；

取序號為［2,5,刀的物品；

取序號為［6,7］的物品。

如要換取游戲中的物品“破天錘”,需要35個金幣,有多種置換的方式,為方便計算以節(jié)省

時間,小趙同學編寫了如下程序,運行界面和代碼如下,請在劃線處填入合適的代碼。

defexchange(t,pricelist):

第35頁共58頁

n=len(pricelist)

stack=∏

i=O

num=0

whileφ：

whilet>Oandi<n:

ift>=int(pricelist[i