高中信息技术 （高考复习）七数据的组织（习题部分）

专题七数据的组织

考点集训

考点一数组

1.(2022浙北G2联盟期中,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)

执行该程序段实现了随机生成一个数组,并将其元素递增输出的功能。划线处的代码应

该是()

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)使用列表生成的方式创建数组代码如下：

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

则数组元素a[3]的值为()

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

答案D

3.(2022绍兴诸暨期中,4)设有一个5×8的二维数组a,若按行优先的顺序存储数组元素则

元素a[3][5]前面元素的个数为()

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=〃〃)

程序段执行后,输出的结果是()

A.2378B.712813

C.2738D.671112

答案C

第2页共58页

5.(2022杭州期中,10)下述代码段用于实现在数组a中将新数据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列的二维数组(要求先将各元素的

值初始化为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.链表数据值依次为2->8->3->6->8

B.程序输出结果为4,8

C.a[0][2]的值为1,双向链表a的头节点数据值为2

D.a[l][l]的值为0,双向链表a的尾节点数据值为8

答案D

2.（2022浙北G2联盟期中,14）用两个列表a、b分别保存单向链表中的数据区域和指针区

域。如图所示,在节点X与节点y之间插入一个新节点,操作步骤正确的是（）

第4页共58页

head节点X节点y

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

新节点

a[i]Ib[i]

head节点X节点y

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

I新产点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所指节点之后插入新

节点（r所指节点）,则执行的操作是)

tail

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

A.tail所指节点的data3值赋为r所指节点的data4值

B.r所指节点的next值赋为tail

C.r所指节点的next值赋为-1

D.tail所指节点的next值赋为r,r所指节点的next值赋为-1

答案D

4.（2022绍兴诸暨期中,8）使用Python的二维列表来模拟单向链表,如下代码创建一个拥有

4个节点的链表a。

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

["rabbit",。]]

head=3

第5页共58页

依次输出各节点数据域的值,内容为（）

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新节点data4（p

指向data2,r指向data4o列表data来记录链表数据域,列表next来记录指针域）,以下选项

中正确的执行步骤为（）

φ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中可以使用列表模拟单向链表,如链表中的节点p,a[p][0]存

储p节点的数据,a[p][l]存储p指向后继节点的指针。若要在p节点之后插入新的节点x（x

作为p的新后继节点）,需要执行的语句是（）

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五个人依次进入电梯,结果警告超重

了,需要出去一个人才能正常运行,按照数据结构中栈和队列的思维,应离开电梯的人分

别是()

A.栈:A队列:EB.栈:A队列:A

C.栈:E队列:AD.栈:E队列:E

答案C

2.若用一个规模为8的数组来实现队列,已知当前队尾指针tail和队首指针head的值分别

为5和0,进行如下操作:①删除两个元素;②插入三个元素;③删除一个元素,操作完成后,

指针head和tail的值分别为()

A.2和7B.3和7

C.3和8D.4和8

答案C

3.用类实现的队列操作如下：

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())

程序执行后,队列中的元素为

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

C.apple,bananaD.banana,peach

答案D

4.(2022"山水联盟”开学考,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个元素出队。则经过TTTQTTQ

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

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

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

答案B

6.小明在使用队列解决问题的过程中,初始时（空队列）,队列的队首指针head=。,队尾指针

tail=。,经过一系列入队、出队操作后,head=4,tail=70在不考虑队列溢出的情况下,小明接

下来进行的操作序列为出队、入队、出队、出队、入队、出队,此时head和tail的值分

别为和O

答案8;9

考点四栈

1.（2022浙南名校联盟期末,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）下列有关栈和队列说法,正确的是（）

A.栈的特点是先进先出,队列的特点是先进后出

B.栈只能在一端进行插入,在另一端进行删除

C队列限定仅能在一端进行插入和删除操作

D.栈和队列均为操作受限的线性表

答案D

4.（2022绍兴诸暨期中,6）若用1表示进栈操作,用0表示出栈操作,某元素的进栈顺序是

/皿03门为了得到出栈序列飞亚11厂,则应进行的操作序列为（）

A.1101010100B.1110010100

C.1110011000D.1110100100

答案B

5.（2022Z20名校联盟,10）某算法利用“栈”思想进行字符串处理,其步骤如下:①创建长度

为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))

则程序运行后输出的结果为

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

执行该程序段后,a的值不可能是（）

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

B.[,

C.[,

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

答案D

8.（2023浙江1月选考,15,9分）有2组器件共n个,要用一台检测设备检测。每个送检器件

的信息包含送达时间、检测时长和优先级。优先级有m（l<m<6）个等级,由高到低分别用

0~m-l的整数表示。每个器件的送达时间各不相同。已送达的器件按照各优先级通道分

别排队,先到达先入队。设备每次检测都从当前各非空队列中,选取优先级最高的队列的

队首器件出队进行检测。（同一时刻出现入队和出队时,先处理入队。）

编写程序模拟检测过程,先合并2组器件的数据,然后计算所有器件的平均等待时长,其中

每个器件等待时长为其开始检测的时间与送达时间的时间差。（时间单位均为秒）

请回答下列问题：

⑴由题意可知,图中器件A、B、C、D的检测顺序为A-C-D-B1AsC、D的等待时

长分别为0、1、O,B的等待时长是O

送达时间检测时长优先级

O32

112

211

43O

1132

第13页共58页

1222

⑵定义如下merge(lstl,Is⑵函数,参数IStI和Ist2的每个元素由送达时间、检测时长和

优先级3项构成,Istl和lst2均已按送达时间升序排列。函数功能是将lst2中的元素合并

到IStI中,并将Istl按送达时间升序排列,函数返回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

①调用merge(lst1,ls⑵函数,若IStl为[[0,3,2],[l,1,2],[12,2,2]],lst2为[[2,1J,[4,3,0],[11,3,2]],

则while语句中循环体的执行次数是o

第14页共58页

②若函数中while语句的条件“j>=0”误写为“k>=0”,会导致某些情况下无法得到符合函

数功能的结果。调用merge(ɪstl,IS⑵函数,下列4组数据中能测试出这一问题的是

(单选,填字母)。

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)实现模拟检测过程并计算平均等待时长的部分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组器件的数据,分别存入列表data）和data2中。2个列表的每个元素包含3个数

据项,分别对应器件的送达时间、检测时长和优先级。datal和data2中的数据已分别按

送达时间升序排列,代码略

读取优先级等级个数存入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名校联盟,11）若一棵二叉树的中序遍历序列为BlGDHAECF,后序遍历序列

为IGHDBEFCA,则该二叉树的前序遍历序列为（）

A.ABCDEFGHIB.ABDGHICEF

C.ABDHGICEFD.ABDGIHCEF

答案D

2.（2022诸暨海亮高中月考,8）一棵二叉树的前序遍历结果为JFDECBHAlG,中序遍历结

果为DFEJAHBlCG,则该二叉树的深度为（）

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

答案B

3.（2022名校协作体,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.该二叉树形态不唯一,无法确定

答案B

4.（2022绍兴诸暨期中,9）已知一棵二叉树的前序遍历为ABDECFG,中序遍历为

DBEAFCG,则该二叉树的后序遍历序列为（）

A.DEBAFGCB.DEBFGCA

C.DBEGFCAD.DBEFGCA

答案B

5.（2022诸暨期末,9）一棵度为3,深度为4的树,最多有个节点。（）

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

答案C

6.（2022诸暨期末,10）设一棵二叉树的中序遍历序列为beefad,后序遍历序列为efcbda,则

二叉树前序遍历序列为（）

A.abcdefB.bdaefcC.abceftiD.abcfed

答案C

7.（2023浙江1月选考,8,2分）下列二叉树中,中序遍历结果为BAEDFC的是（）

考点六大数据时代的数据的组织

L下面的系统中,属于实时查询系统的是（）

第18页共58页

A.某学校的学生学籍管理系统

B.某航空公司的在线订票系统

C.某广告公司的计算机辅助设计系统

D.某印刷厂的计算机激光排版系统

答案B

2.大数据背景下的数据组织和存储方式,通常采用的技术是

A.传统存储系统

B.云存储系统

C.分布式存储系统

D.集中式存储系统

答案C

3.下列方法中,不熊有效提升内存数据库的数据处理性能的是

A.处理的数据保存在内存中并直接操作

B.增加对磁盘的数据读写

C.对数据进行分级,并在处理器缓存中存储

D.采用改进后的数据结构来组织、存储数据,如跳跃表、平衡树

答案B

4.下列关于实时查询数据系统中的数据结构的说法,于耳噂的是

A.在实时查询系统中使用数组,时效性较差

B.在链表中查找数据时效性较高,插入数据时效性较低

C.跳跃表基于有序链表

D.跳跃表通过跨区间、跳跃性的比较,避免了依次比较,提高了效率

第19页共58页

答案B

5.有如下跳跃表:

若要在原链表中插入元素7,则数据元素需要比较的次数为

A.lB.3C.4D.5

答案B

6.下列关于Hadoop的说法,下年唧的是()

A.Hadoop是一种超大规模,高可靠性,高可扩展性的数据库

B-Hadoop是Googlc云计算技术的开源实现

C.使用Hadoop可以在POl数据的处理中获得更方便的体验和更低廉的成本

D.Hadoop可以对海量地理信息进行处理和计算

答案A

专题集训

1.（2022嘉兴期中,1）以下数据结构中,不属于线形结构的是（）

A.数组B.链表C.队列D.树

答案D

2.（2023届十校联盟10月联考,10）要解决不同的实际问题,需要根据实际需要选择不同的

数据结构来组织数据。下列说法正确的是（）

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

B.火车站或者飞机场会在电子屏上滚动显示最近的班次信息,可以采用链表组织数据

C计算机操作系统中文件夹的管理,通常借助栈来组织、保存和处理数据

第20页共58页

D.用户单击浏览器的“后退”按钮可以回到刚才浏览过的网页,通常采用树结构进行网页

数据的组织

答案13

3.（2023届嘉兴基测,9）下列关于数据结构的说法,正确的是（）

A.常见的线性关系数据结构有数组、队列、栈、树和图等

B.数组和链表在操作时,其存储空间固定不变

C链表在访问、插入和删除元素时,算法效率比数组高

D.栈是一种先进后出的线性表结构

答案D

4.（2023届浙江名校联盟10月联考,9）一个栈的输入序列为“12345”,输出的第一个元素为

“4”,则输出的第三个元素不可能是（）

A.lB.2C.3D.5

答案A

5.（2023届浙江学军中学10月月考,2）新型冠状病毒肺炎（CoronaVirusDisease

2019,CoVID-19）,简称“新冠肺炎”,是一种传染性极强的流行病。一旦发现“新冠肺炎”确

诊病例或无症状感染者,就要对其进行流行病学调查（简称“流调”）。调查期间,充分利用信

息化和公安、工信大数据手段,通过病例和无症状感染者居住（工作）环境等现场调查和定

点医院驻点调查相结合,查明病例和无症状感染者活动轨迹,规范开展个案调查、密切接

触者追踪和聚集性疫情调查。

在“新冠肺炎”流调中,要表示某个患者和其下所有患者的传染关系,比较适合的数据组织

形式是（）

A.数组B.队列C.栈D.树

第21页共58页

答案D

6.（2023届强基联盟10月统测,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届浙南名校联盟IO月联考,11）如果将数学表达式中的运算数和运算符视为二叉

树的每个节点,那么我们可以构造出各种表达式二叉树,下图是一棵表达式二叉树。如果

对该二叉树进行中序遍历,并加上括号后,就可以得到中缀表达式：（9-4/2）*5+3。如果对该

二叉树实行前序遍历,则可以得到的表达式为)

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

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

答案A

8.（2023届百师联盟联考,3）公交车上有时候会出现人太多无法挤到后门下车而从前门下

车的情况,因此若一个序列在有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〃时,程序输出的结果为()

A.QUEUEB.EUEUQ

C.QEUUED.QEEUU

答案D

第23页共58页

10.(2023届丽湖衢11月质量检测,12)某公交路线的站点名称、经度、纬度和下一个站点

序号(经纬度已转换为平面坐标数据)存储在数组a中,现计算相邻两个站点距离的总和。

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届浙南名校联盟10月联考,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整数:〃).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)

若要实现下图所示的功能,则①②③处应填入的语句依次为

请输入一个整数：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])

上述程序段要遍历链表中的所有元素,划线处应添加的代码是

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）有如图所示的二叉树,关于此二叉树的说法中,描述正确的是

A.该二叉树的前序遍历为ABDGJCEFHI

B.该树中共有3个叶子节点

C若有前序遍历和后序遍历可以推导出唯一的二叉树

D.该树的深度是4

答案A

14.（2022浙江开学考,10）已知一个链表a,其a[i][0]存储索引i下节点的数据区域,a[i]山存

储索引i下节点的指针区域。对于当前链表中的一个节点p（索引为p）,若要删除p的后一

个节点q（q=a[p][l]）,则应执行语句（）

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中用列表模拟链表结构,某程序段如下：

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]

#从头节点开始遍历链表a逻辑顺序的所有节点,并依次输出节点的数据,代码略

该程序段执行后的输出结果为

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)

执行该程序段,输入字符串“abcdef⅛”,则输出的结果是()

A.acegbdfB.acegfidb

C.gecafdbD.ecafdb

答案D

17.(2022诸暨海亮高中月考,18)有个火车站的铁轨调度方法如下:火车从一方1,2,3,4…依

次进入,由于每个火车皮要去的目标车站不一样,想让车皮到站后能以最少的时间从火车

上脱离,就让最近到的车皮放在整列火车的最后。因此需要转换站来达成这样的目标,转

换站只能在同一个地方进与出。例如有四个车皮1,2,3,4进入24,3,1到站,即2号车皮目

的地最远,4号车皮倒数第二远,3号车皮倒数第三远,1号车皮最近。

为了能快速指挥车辆进出站转换,小王编写了如下程序：

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(〃无法调度〃)

break

iftop=-l:

print(s)

代码显示结果：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联盟期中,16）小明来到探险岛寻宝,岛上共有N个宝藏（标号为0至N-1）。

每个宝藏有一条路连接下一个宝藏,宝藏号和下一个宝藏号使用链表存储。小明想知道,

从其中一个宝藏出发,最多可以找到多少个宝藏。

例如，共有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」,那么小明最多可以挖到的宝藏数

是O

(2)请将代码补充完整。

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

19.(2022杭嘉湖金月考,15)山顶上有10个圆形排列的洞,一只狐狸和一只兔子各住一个

洞。狐狸总想吃掉兔子。一天兔子对狐狸说:“你想吃我有一个条件,先把洞从1-10编上

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

依此类推,次数不限。但狐狸从早到晚进进出出了IoOo次,仍没有找到兔子。请问兔子可

能躲在哪个洞里？

实现上述功能的Python程序如下,请在划线处填入合适的代码。

hole=[]

n=10

m=1000

#构造一个循环链表,并给n个洞编号,设置洞的初始标志为0

#链表的节点样式为:[洞的标志,洞的编号]

foriinrange(n-l):

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

ω

第32页共58页

#狐狸开始找兔子,将进入过的洞标志改为1,寻找m次结束

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列的数格式化为2个字符的格式,如果是一位数,在这一位

数前加空格。

实现上述功能的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山水联盟开学考,15)小赵同学在某游戏平台中获得虚拟的食物、装备、材料等

物品,它们分别有不同的价值,现游戏平台有兑换机制,即可用多个不同物品换取一个等

值的物品(每个物品只能取一样),下表为小赵同学已获得的物品。

第34页共58页

序号物品名称数量单价

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个金币,有多种置换的方式,为方便计算以节省

时间,小赵同学编写了如下程序,运行界面和代码如下,请在划线处填入合适的代码。

defexchange(t,pricelist):

第35页共58页

n=len(pricelist)

stack=∏

i=O

num=0

whileφ：

whilet>Oandi<n:

ift>=int(pricelist[i