浙江版高中信息技术复习练习专题七数据的组织课件

高考

技术第一部分信息技术专题七数据的组织浙江省专用考点一数组1.(2022浙北G2联盟期中,15)有如下Python程序段:importrandoma=[]foriinrange(10):a.append(random.randint(1,100))i=0whilei<10:ifi==0:i=i+1elifa[i-1]<=a[i]:①

else:a[i],a[i-1]=a[i-1],a[i]②

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

应该是

(

)A.①i+=1②i=1B.①i-=1②i=1C.①i+=1②i+=1D.①i-=1②i-=1答案

A

2.(2022绍兴诸暨期中,3)使用列表生成的方式创建数组代码如下:a=[i*i-1foriinrange(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)]forjinrange(3)]foriinrange(3):forjinrange(3):a[i][j]=i*5+j+1foriinrange(1,3):forjinrange(2):print(a[j][i],end="")程序段执行后,输出的结果是

(

)A.2378B.712813C.2738D.671112答案

C

5.(2022杭州期中,10)下述代码段用于实现在数组a中将新数据k插入下标为j(0<=j<=8)

的位置:a=[8,6,12,3,5,7,11,2,10,0]i=8whilei>=j:

(1)

(2)

(3)

横线处的代码由以下五部分中的三部分组成:①a[i+1]=k②a[i]=k③a[i+1]=a[i]④a[i]=a[i-1]⑤i=i-1下列选项中代码选择与顺序正确的是

(

)A.③⑤②B.⑤③①C.③⑤①D.④⑤②答案

C

6.(2022嘉兴期中,3)用Python程序段定义一个3行4列的二维数组(要求先将各元素的

值初始化为0,再将第2行第2个元素重新赋值为1),以下程序段可行的是

(

)A.arr=[[0]*3forjinrange(4)]arr[2][2]=1B.arr=[[0]*4]*3arr[1][1]=1C.arr=[[0foriinrange(4)]forjinrange(3)]arr[1][1]=1D.arr=[[0,0,0,0]forjinrange(3)]arr[2][2]=1答案

C

考点二链表1.(2022浙南名校联盟期末,12)一个头指针head=2的单向链表L=[[30,4],[10,-1],[20,

0],[15,1],[21,3]]通过以下Python程序段,转换为原链表的逆序链表,即头指针head=1,

L=[[30,2],[10,3],[20,-1],[15,4],[21,0]]。q=-1p=head#head为原链表头指针whilep!=-1:tmp=L[p][1]

head=q上述程序段中方框处可选的语句为:①p=tmp②q=p③L[p][1]=q则方框处语句依次为

(

)A.③②①B.③①②C.①③②D.①②③答案

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

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

(

)

①b[i]=b[y]②b[i]=b[x]③b[y]=i④b[x]=i⑤b[i]=x⑥b[i]=yA.③⑥B.④②C.①③D.②④答案

D

3.(2023浙江开学考,10)已知一个链表a,其a[i][0]存储索引i下节点的数据区域,a[i][1]存

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

一个节点q(q=a[p][1]),则应执行语句

(

)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中用列表模拟链表结构,某程序段如下: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,0whilen<4:c=c+1ifc==m:n=n+1;c=0ifp==head:head=a[p][1]a[q][1]=headp=a[p][1]else:a[q][1]=a[p][1]p=a[p][1]else:q=pp=a[p][1]#从头节点开始遍历链表a逻辑顺序的所有节点,并依次输出节点的数据,代码略该程序段执行后的输出结果为

(

)A.ng02B.g02nC.2an2D.22an答案

D

5.(2022诸暨期末,8)某单向链表如图所示,在data2与data3之间插入一个新节点data4(p

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

中正确的执行步骤为

(

)

①next[p]=next[r]②next[p]=r③next[r]=p④next[r]=-1⑤next[r]=next[p]⑥next[p]=-1A.③⑥B.⑤②C.①④D.⑤②④答案

B

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

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

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

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

兔子可能躲在哪个洞里?实现上述功能的Python程序如下,请在划线处填入合适的代码。hole=[]n=10m=1000#构造一个循环链表,并给n个洞编号,设置洞的初始标志为0#链表的节点样式为:[洞的标志,洞的编号]foriinrange(n-1):hole.append([0,i+1])

(1)#狐狸开始找兔子,将进入过的洞标志改为1,寻找m次结束head=0k=headhole[0][0]=1foriinrange(1,m):forjinrange(1,i+2):

(2)

hole[k][0]=1#输出标志仍为0的洞,即兔子可能的藏身地点foriinrange(len(hole)):ifhole[i][0]==0:print("兔子可能躲在第"+

(3)

+"号洞")答案

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

(2)k=hole[k][1]

(3)str(i+1)

考点三队列1.(2024届七彩联盟联考,11)有如下程序段:s=input()head=0;tail=0;ans=0;tmp=''q=['']*100flag=Trueforiinrange(len(s)):ifs[i]==',':whilehead!=tail:tmp+=q[head]head+=1ifflagandhead<tail:head+=1flag=notflagans+=int(tmp)tmp='';flag=Trueelif'0'<=s[i]<='9':q[tail]=s[i]tail+=1输入s为"1-500,2023900-,",执行该程序段,变量ans的值为

(

)A.100B.22300C.22351D.22400答案

D

2.(2022杭州“六县九校”期中,5)有A、B、C、D、E五个人依次进入电梯,结果警告

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

的人分别是

(

)A.栈:A队列:EB.栈:A队列:AC.栈:E队列:AD.栈:E队列:E答案

C

3.(2024届强基联盟联考,9)执行下列Python程序段,输出结果为

(

)data=[1,2,3,1,2,3]que=[0]*10head=tail=0foriinrange(len(data)):ifdata[i]%2!=0:que[tail]=data[i]tail+=1eliftail-head>1:que[tail-1]+=que[head]head+=lprint(que[head:tail])A.[3,2,1]B.[1,2,3]C.[1,3,1]D.[3,2,3]答案

D

4.(2024届新阵地联盟第二次联考,11)有如下程序段:m=3;n=7head=tail=0;ans=0vis=[0]*10;q=[0]*10foriinrange(n):x=int(input())if(vis[x]=0):ans+=1if(tail-head>=m):vis[q[head]]=0head+=1q[tail]=xtail+=1vis[x]=1print(ans)运行该程序段,依次输入x的值:1,2,1,5,4,4,1。则程序运行完成后ans的值是

(

)A.3B.4C.5D.6答案

C

5.(2024届天域全国名校协作体联考,12)已知列表a的长度为6,a[0]至a[5]的值依次为1

8,12,24,15,21,0,某程序如下所示:head,tail=0,5x=a[head]head+=1while(head+1)%len(a)!=tail:t=y=a[head]head=(head+1)%len(a)ifx<y:x,y=y,xifx%y!=0:a[tail]=x%ytail=(tail+1)%len(a)x=tprint(a[head])程序运行后,输出的结果是

(

)A.24B.12

C.3D.0答案

C

6.(2023“山水联盟”开学考,11)有如下Python程序代码:s="ABCDEF";head=0;tail=0que=[""]*100foriinrange(len(s)):ifi%2==0:que[tail]=s[i]else:que[tail]=s[len(s)-i]tail=tail+1foriinrange(len(s)):print(que[head],end="")head=head+1以上程序运行后,输出列表的情况是

(

)A.ABCDEFB.FEDCBAC.ACEFDBD.AFCDEB答案

D

考点四栈1.(2022浙南名校联盟期末,10)一个栈的入栈序列为“6、9、5、7、8、3”,其出栈序

列不可能是

(

)A.3、8、7、5、9、6B.7、5、9、8、6、3C.6、5、7、9、3、8D.5、9、6、3、7、8答案

D

2.(2024届百校起点调研测试,9)栈q初始有三个值,经过一系列入栈、出栈操作后,栈为

空,若元素出栈的顺序是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联盟联考,9)若元素入栈的顺序是1,2,3,4,5,6,不允许连续三次入栈,则可

能的出栈序列为

(

)A.2,3,5,1,6,4B.1,2,3,6,5,4C.2,4,3,1,6,5D.2,5,4,6,3,1答案

C

4.(2024届七彩联盟联考,9)假设栈S的最大长度为3,其初始状态和终止状态均为空,经

过一系列入栈和出栈的操作,若元素最后的出栈序列为F,E,D,C,B,A,则可能的入栈顺

序为

(

)A.ABCDEFB.ACDFEBC.BEFACDD.BFDECA答案

D

5.(2024届嘉兴基测,12)待入栈的序列a有多种出栈序列,以下函数用于判断序列b是不

是a的出栈序列,代码如下:defjudge(a,b):n=len(a);st=[-1]*ntop=-1;i=j=0whilei<n:top+=1①

i+=1whiletop>-1and②

:top-=1j+=1returntop==-1fromrandomimportshufflea=[1,2,3,4,5]b=[1,2,3,4,5]shuffle(b)#将序列b的元素随机排序ifjudge(a,b):print(b,'是',a,'的出栈序列')else:print(b,'不是',a,'的出栈序列')程序运行结果如图所示。划线处应填写的语句是

(

)python12.py[2,5,4,3,1]是[1,2,3,4,5]的出栈序列python12.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.(2022Z20名校联盟,10)某算法利用“栈”思想进行字符串处理,其步骤如下:①创建

长度为n的空栈,字符依次入栈;②当达到栈满状态或数据全部入栈时,字符依次出栈,

按照出栈顺序连接成新字符串:③若还有未处理的字符,则重复步骤①②,直到全部字

符处理完毕。实现该功能的Python程序如下:s=input("请输入字符串:")n=5;st=[""]*ntop=-1;i=0;m=""whilei<len(s):while

(1)

andi<len(s):(2)

st[top]=s[i]i+=1whiletop!=-1:m+=st[top](3)

print("密文:",m)加框处(1)(2)(3)的代码由以下代码组成:①top-=1②top+=1③top+1<n④top<n下列选项中代码顺序正确的是

(

)A.④②①B.③①②C.③②①D.④①②答案

C

7.(2022诸暨海亮高中月考,10)有如下程序段:bt=["A","B","C","D",None,"E","F"]result=[]stack=[]i=0whilestackor(i<len(bt)andbt[i]isnotNone):ifi<len(bt)andbt[i]isnotNone:stack.append(i)i=2*i+1else:i=stack.pop()result.append(bt[i])i=2*i+2print("-".join(result))则程序运行后输出的结果为

(

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

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

D.A-B-C-D-E-F答案

C

考点五树1.(2024届Z20联盟联考,8)某二叉树的树形结构如图所示,其后序遍历结果为“物技化

数英语”,则中序遍历结果为

(

)

A.语数英物化技B.物数技化语英C.语数物化技英D.化物技英数语答案

B

2.(2022名校协作体,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-FB.A-B-D-G-E-H-C-F-IC.A-B-D-G-E-H-F-C-ID.该二叉树形态不唯一,无法确定答案

B

3.(2024届新阵地联盟第二次联考,8)某二叉树的树形结构如图所示,其后序遍历结果为

FABGDEC,则中序遍历结果为

(

)

A.FDAGBCEB.FDABGECC.AGBDFCED.FDAGBEC答案

A

4.(2024届天域全国名校协作体联考,8)下列二叉树中,后序遍历结果不为CBFEAD的是

(

)

答案

D

5.(2024届七彩联盟联考,8)某二叉树用一维数组表示(见表)。该二叉树从根节点开始,

按照从上到下,从左到右的顺序依次用A-H字母表示,该二叉树的中序遍历为

(

)

01234567891011121314

ABCDE

F

G

HA.DBGEACFHB.DBGEACHFC.DBEGACHFD.ABCDEFGH答案

A

考点六大数据时代的数据的组织1.下列关于实时查询数据系统中的数据结构的说法,不正确的是

(

)A.在实时查询系统中使用数组,时效性较差B.在链表中查找数据时效性较高,插入数据时效性较低C.跳跃表基于有序链表D.跳跃表通过跨区间、跳跃性的比较,避免了依次比较,提高了效率答案

B

2.有如下跳跃表:

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

(

)A.1B.3C.4D.5答案

B

3.下列关于Hadoop的说法,不正确的是

(

)A.Hadoop是一种超大规模,高可靠性,高可扩展性的数据库B.Hadoop是Google云计算技术的开源实现C.使用Hadoop可以在POI数据的处理中获得更方便的体验和更低廉的成本D.Hadoop可以对海量地理信息进行处理和计算答案

A

题组一1.(2024届名校协作体联考,8)某二叉树的前序遍历结果为GFDECAB,中序遍历结果为

DFGCAEB。关于该二叉树,以下说法正确的是

(

)A.该二叉树的后序遍历为ADFCBEGB.该二叉树的深度为4,节点C在第3层C.该二叉树的叶子节点数比非叶子节点数多一个D.该二叉树可以通过添加3个节点后变为完全二叉树答案

B

2.(2024届强基联盟联考,8)某二叉树的树形结构如图所示,其后序遍历结果为

FBCEAD,则前序遍历结果为

(

)

A.ABCDEFB.FEDCBAC.DFACBED.FDBCAE答案

C

3.(2024届强基联盟统测,8)已知某二叉树的后序遍历为GDBEHFCA,中序遍历为DG-

BAECHF,下列说法正确的是

(

)A.该二叉树中叶子节点有3个B.该二叉树的前序遍历为ABDGCEHFC.该二叉树是一棵完全二叉树,树的高度为4D.该二叉树中度为1的节点有2个答案

A

4.(2024届新阵地联盟第二次联考,9)栈S初始状态为空栈,将序列3,2,5,7,1中元素逐一

入栈,当栈空或入栈元素比栈顶元素大时则入栈,否则出栈至符合条件再入栈。序列

所有元素入栈完毕后,栈内剩余元素出栈,直至栈空。则出栈的顺序是

(

)A.17523B.37521C.37512D.32751答案

B

5.(2024届天域全国名校协作体联考,9)利用栈求逆波兰表达式(表达式由操作数和运

算符组成)的方法是:从左往右扫描该表达式,遇到操作数时入栈;遇到运算符时,把处于

栈上方的两个元素依次出栈,用运算符计算,并把计算结果压入栈中。如此反复操作,

直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时(abcdef表示不

同的操作数),所使用的栈的深度至少为

(

)A.3B.4C.5D.6答案

B

6.(2024届嘉兴基测,11)长度为5的循环队列que,que[0]至que[4]的值依次为'a','b','c','d','e',

执行如下程序段后,输出的最后一个字符为

(

)n=5;head=0;tail=4que=['a','b','c','d','e']whilehead!=tail:ifhead%4==0:print(que[head])else:tail=(tai1+1)%nque[tail]=que[head]head=(head+1)%nprint(que[head])A.bB.cC.dD.e答案

B

7.(2024届发展共同体联考,9)某种特殊的队列Q,支持以下三个操作:操作Q1:若队列非空,队首元素出队,并输出;操作Q2:若队列非空,队首元素出队;操作Q3:一个元素入队。以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。若队列Q初始状态为空,依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后,下列

说法正确的是

(

)A.当前队列中的元素个数为2B.输出的元素个数为2C.第一个输出的元素肯定比当前队首元素大D.队列初始状态是不是空对输出结果有影响答案

D

8.(2024浙江1月选考,8,2分)栈S从栈底到栈顶的元素依次为1,2,3,队列Q初始为空。约

定:U操作是指元素出栈后入队,H操作是指元素出队后再入队。经过UUHU系列操作

后,队列中队首到队尾的元素依次为

(

)A.2,1,3B.3,1,2C.1,3,2D.2,3,1答案

D

9.(2024浙江1月选考,9,2分)数组元素a[0]至a[n-1]依次存放着n个数据,现需要将元素a

[n-1]插入在下标为x(0≤x<n-1)的位置,例如:n为5,数组a为[0,3,4,6,7],x为2,插入操作后a

为[0,3,7,4,6]。实现该功能的程序段如下,方框中应填入的正确代码为

(

)temp=a[n-1]foriinrange(n-2,x-1,-1):a[x]=tempA.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届发展共同体联考,11)有如下程序段:s=['']*len(a)head=2;q=head;top=-1whileq!=-1:top+=1s[top]=a[q][0]q=a[q][1]print(s[top-2])若a=[['a',3],['b',0],['c',1],['d',-1]],则输出的结果为

(

)A.aB.bC.cD.d答案

B

11.(2024届强基联盟联考,11)有如下Python程序段:s=input()stack=[0]*len(s);top=-1;presign='+';num=0foriinrange(len(s)):if'0'<=s[i]<='9':num=num*10+int(s[i])ifi==len(s)-1ors[i]in'+-*/':ifpresign=='+':top+=1stack[top]=numelifpresign=='-':top+=1stack[top]=-numelifpresign=='*':top+=1stack[top]=stack[top-1]*numelse:top+=1stack[top]=stack[top-1]//numpresign=s[i]num=0print(sum(stack))#sum函数对stack中所有元素求和若输入'5*4-6+10/3',程序运行后,输出的结果是

(

)A.32B.24C.17D.8答案

A

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

件的信息包含送达时间、检测时长和优先级。优先级有m(1<m<6)个等级,由高到低

分别用0~m-1的整数表示。每个器件的送达时间各不相同。已送达的器件按照各优

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

级最高的队列的队首器件出队进行检测。(同一时刻出现入队和出队时,先处理入

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

中每个器件等待时长为其开始检测时间与送达时间的时间差。(时间单位均为秒)请回答下列问题:(1)由题意可知,图中器件A、B、C、D的检测顺序为A—C—D—B,A、C、D的等待时

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

。

送达时间检测时长优先级A032B112C211D430

11321222(2)定义如下merge(lst1,lst2)函数,参数lst1和lst2的每个元素由送达时间、检测时长和

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

到lst1中,并将lst1按送达时间升序排列,函数返回lst1。defmerge(lst1,lst2):i=len(lst1)-1j=len(lst2)-1fortinrange(len(lst2)):lst1.append([0,0,0])#为lst1追加一个元素[0,0,0]k=len(lst1)-1whilej>=0:ifi>=0andlst1[i][0]>lst2[j][0]:lst1[k]=lst1[i]i-=1else:lst1[k]=lst2[j]j-=1k-=1returnlst1①调用merge(lst1,lst2)函数,若lst1为[[0,3,2],[1,1,2],[12,2,2]],lst2为[[2,1,1],[4,3,0],[11,3,

2]],则while语句中循环体的执行次数是

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

符合函数功能的结果。调用merge(lst1,lst2)函数,下列4组数据中能测试出这一问题的

是

(单选,填字母)。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)实现模拟检测过程并计算平均等待时长的部分Python程序如下,请在划线处填入合

适的代码。defproc(data,m):n=len(data)queinfo=[]foriinrange(m):queinfo.append([-1,-1])#queinfo追加一个元素[-1,-1]foriinrange(n):data[i].append(-1)#data[i]追加一个元素-1curtime=0waitnum=0i=0①

whilei<norwaitnum>0:ifi<nanddata[i][0]<=curtime:k=data[i][2]ifqueinfo[k][0]==-1:queinfo[k][0]=ielse:②

data[p][3]=iqueinfo[k][1]=iwaitnum+=1i+=1elifwaitnum>0:k=0whilequeinfo[k][0]==-1:k+=1p=queinfo[k][0]total+=curtime-data[p][0]curtime+=data[p][1]③

waitnum-=1else:curtime=data[i][0]returntotal/n'''读取2组器件的数据,分别存入列表data1和data2中。2个列表的每个元素包含3个数据

项,分别对应器件的送达时间、检测时长和优先级。data1和data2中的数据已分别按送达时间升序排列,代码略读取优先级等级个数存入m,代码略'''data=merge(data1,data2)print(proc(data,m))答案

(1)6或6秒

(2)①4②A

(3)①total=0或其他等价表达式②p=queinfo[k][1]

或其他等价语句

③queinfo[k][0]=data[p][3]或其他等价语句13.(2023浙江6月选考,15,9分)某工程包含n个任务(编号为0~n-1),每天可以有多个任务

同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任

务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个

任务依赖于多个任务,或多个任务依赖于同一个任务的情况。现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”

的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期

限,计算每个任务最晚必须开始的时间。任务A任务B标记05T54F41T12T23F注:任务A依赖于任务B图b请回答下列问题:(1)若某工程有6个任务,任务间依赖关系如图a所示,完成任务0~5所需天数分别为2,1,3,

5,1,6,则工程最快完成需要

天。(2)定义如下erase(lst)函数,参数lst列表的每个元素表示一个依赖关系。函数的功能是

删除标记为“F”的依赖关系,返回保留的依赖关系的个数。deferase(lst):i=0j=len(lst)-1whilei<=j:iflst[i][2]=='T':i+=1else:iflst[j][2]=='T':lst[i]=lst[j]i+=1j-=1returni若lst列表依次存储图b所示的依赖关系,如lst[0]为[0,5,'T'],调用erase(lst)函数,则语句

“lst[i]=lst[j]”的执行次数为

。(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。defproc(n,lst,task):pr=[0]*nw=[0]*n#w[i]存放任务最晚必须开始的时间m=erase(lst)foriin①

:task[lst[i][1]][1]=lst[i][0]pr[lst[i][0]]=1c=[]days=0#days存放工程最快完成所需的天数foriinrange(n):ifpr[i]==0:k=is=0whilek!=-1:c.append(k)s+=task[k][0]②

ifs>days:days=sforiinrange(n-1,-1,-1):k=c[i]iftask[k][1]==-1:w[k]=days-task[k][0]+1else:③

#输出days,以及保存在w中的每个任务最晚必须开始的时间,代码略"'工程包含的任务数存入变量n任务间的依赖关系存入lst列表lst[0]包含3项,任务lst[i][0]依赖于任务lst[i][1],lst[i][2]存放保留/删除标记,任务数据存

入task列表task[i]包含2项,task[i][0]为完成任务所需天数,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联盟联考,15)小明同学去看病,当他在一位医生的诊室门口等待就诊的

时候,发现了叫号系统的页面上有两行病人名单。第一行名单为正常排队等待就诊的

序号,第二行名单为过号或检后再诊而等待的序号。叫号的规则是先在第一行叫2个

就诊序号,再到第二行叫1个就诊序号。小明同学回家后将刚才发现的叫号规则编写

了Python程序。效果如图所示:图①:当前到来的就诊序号是3号,为过号或检后再诊序号,进入第二行,先到达先就

诊。图②:当前到来的就诊序号是4号,为过号或检后再诊序号,进入第二行。图③:当前到来的就诊序号是16号,为正常排队等待就诊的序号,进入第一行,按就诊序号顺序排列。图④:开始叫号,按照正常排队等待就诊叫号2位,过号或检后再诊叫号1位,得到新的顺

序。

(1)请在划线处填入合适的代码。(2)加框处的代码有误,请改正。defoutput(head,a,b):p=headhead_b=0;tail_b=len(b)whilep!=-1:print(a[p][0],end="->")p=a[p][1]print()whilehead_b!=tail_b:print(b[head_b],end="->")head_b+=1print()definsert(data,a,b):#根据挂号的序号分别进入第一行名单或第二行名单head_a=a[0][0]ifdata>①

:p=0a.append([data,-1])whilep!=-1:ifdata<=a[p][0]:a[-1][1]=pa[q][1]=len(a)-1breakelse:q=pp=②

ifp==-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]whileTrue:data=int(input("请输入取号:"))#输入0表示停止取号,开始叫号ifdata==0:breakinsert(data,a,b)print("====开始叫号====")p=head=0head_b=0;tail_b=len(b)whilep!=-1orhead_b!=tail_b:ifp!=-1andhead_b!=tail_b:i=0whilea[p][1]!=-1:print(a[p][0],end="->")p=a[p][1]i+=1print(④

,end="->")head_b+=1elifp!=-1andhead_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<2andp!=-1或i<=1andp!=-115.(2022山水联盟开学考,15)小赵同学在某游戏平台中获得虚拟的食物、装备、材料

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

个等值的物品(每个物品只能取一样),下表为小赵同学已获得的物品。序号物品名称数量单价0灵丹211大力丸122止血草353忘魂花174雄黄195灵山仙芝5106梅花镖1157止血草120目标置换物品的价值: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个金币,有多种置换的方式,为方便计算以

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

码。defexchange(t,pricelist):n=len(pricelist)stack=[]i=0num=0while①

:whilet>0andi<n:ift>=int(pricelist[i]):stack.append(i)②

i+=1ift==0:print("取序号为",stack,"的物品")num+=1if③

:i=stack.pop()t+=int(pricelist[i])④

ifnum==0:print("无方案")m=int(input("目标置换物品的价值:"))price=input("已获得物品价值依次是:")p=price.split(",")#将输入的内容以“,”作分隔,并转换为列表print("依次拿取物品序号的方案有:")exchange(m,p)答案①stackori<n或len(stack)!=0ori<n或等价答案②t=t-int(pricelist[i])或等价答

案③len(stack)!=0或等价答案④i+=116.(2022名校协作体联考,15)某校军训,需要按照身高由低到高排成n行5列的方阵。某班学生按照身高(100≤身高<199)由低到高编写编号并将相关信息存在图1所示的“stu.txt”文件中。根据教官提出的排方阵要求,排成如图2所示的方阵,方阵各点显示学生编号。

现有延迟报到学生归队,归队学生编号延续该班现有编号依次往后,编写程序完成下

列任务:输入学生身高,输出新的方阵布局图。例如:输入学生身高为168,新的方阵布

局图如图3所示,学生在方阵的位置:3,4。(1)若插入学生身高为160cm,根据图1及范例,该学生应该在图2方阵中的

行

列。(2)为实现上述功能,请填写划线处代码。f=open("stu.txt","r")a=[]line=f.readline().split()i=1whileline!=[]:a.append([line[0],line[1],i])i+=1line=f.readline().split()n=len(a)-1a[n][2]=-1sg=input("请输入插入的学生身高(cm):")xh=str(len(a))head=1p=head;q=headwhile

①

:p=qq=a[q][2]ifq==head:②

head=len(a)-1else:a.append([xh,sg,a[p][2]])a[p][2]=len(a)-1p=headm=1whilep!=-1:ifm!=5:print(a[p][0],end="")m+=1else:print(a[p][0])m=1③

答案

(1)1,5

(2)①a[q][1]<sgandq!=-1或int(a[q][1])<int(sg)andq!=-1②a.append

([xh,sg,head])或a.append([xh,sg,p])或a.append([xh,sg,q])或等价答案③p=a[p][2]17.(2022A9协作体返校考,15)学校举办了“语文作文现场赛”,参赛同学成绩存储在

文本文件“gra.txt”中,如图a所示(每一行记录一位同学的姓名和成绩,以“:”分隔)。

陈老师利用Python程序对作文成绩进行处理,统计出各个分数等级的人数,并输出结

果。程序运行界面如图b所示。

实现上述功能的Python程序如下,请在划线处填入合适的代码。defcla(x):#判断成绩等级ifx>=50:return"A"elifx>=40:return"B"elifx>=30:return"C"else:return"D"gra=[]#存储各个整数型成绩num=[0]*4f=open("gra.txt")lines=f.readlines()#将f对象的数据按行存入列表lines中f.close()#关闭文件forlineinlines:#循环读取列表lines中的每个元素,并做相应处理a=line.strip().split(":")#去除结尾的换行符并以冒号为分隔符进行分隔gra.append(①

)foriinrange(len(gra)):#统计各等级人数t=②

num[ord(t)-65]+=1print("成绩分布如下:")foriinrange(len(num)):#输出统计结果print(chr(i+65)+"等级有"+③

+"人")答案①int(a[1])或int(a[-1])②cla(gra[i])③str(num[i])18.(2023七彩阳光开学考,15)食堂推出的三款特色菜,分别用A、B、C表示,想用投票

方式统计出三款菜的受欢迎程度。每位投票者需要将三款菜按喜爱程度从高到低进

行排列,并投出一票。如图a所示,小明负责将文件“投票.txt”中的选票进行统计。第

1张选票信息为“A,C,B”,表示投票者认为A菜优于C菜,C菜优于B菜,即A菜也优于B

菜。他得到如图b所示的投票情况。对选票进行统计,得到三款菜的偏好,如图c所示,

数据第一行中的“6”说明有6张选票显示A菜优于B菜,“10”说明有10张选票显示A

菜优于C菜,以此类推……将所有投票进行统计,再将三款菜的得票数进行求和,按得票

数从高到低排列,分别为A菜16票,B菜11票,C菜12票,即可得到每款菜的受欢迎程度。

请回答下列问题:(1)若有四款菜,投票情况如图d所示,则第2受欢迎的菜为

(填字母)菜。(2)加框处代码有错误,请改正。(3)实现上述功能的Python程序如下,请在划线①②③处填入合适的代码。f=open('投票.txt')a=[]r=f.readline().strip()#从文件中读取一行,并把末尾的'\\n'删掉whiler:#当r非空(从文件读取到了数据)a=r.split(',')r=f.readline().strip()f.close()n=len(a[0])p=[0]*n**2foriina:forjinrange(n-1):x1=ord(i[j])-65forkinrange(①

):x2=ord(i[k])-65②

b=[['',0]foriinrange(n)]foriinrange(n):b[i][0]=chr(i+65)forjinrange(n):b[i][1]+=p[i*n+j]i=1whilei<n:x=b[i]j=i-1while③

:b[j+1]=b[j]j-=1b[j+1]=xi+=1foriinrange(n):print('第',i+1,'受欢迎的菜为',b[i][0],',得票为',b[i][1],'票')答案

(1)D

(2)a.append(r.split(','))

(3)①j+1,n②p[x1*n+x2]+=1③j>=0andx

[1]>b[j][1]或j>=0andx[1]>=b[j][1]1.(2024届百校起点调研测试,8)某二叉树的中序遍历为ABCDEF,则下列不可能是此二

叉树的是

(

)

题组二答案

C

2.(2024届发展共同体联考,8)某二叉树的树形结构如图所示,其前序遍历结果为BAD-

CFGE,则字符“G”所在的位置为

(

)

A.①B.②C.③D.④答案

C

3.(2024届浙南名校联盟联考,8)有一棵二叉树如图所示,下列说法正确的是

(

)

A.此二叉树是完全二叉树B.此二叉树的叶子节点有3个C.此二叉树的后序遍历为FDBECAD.此二叉树用一维数组表示为['A','B','C','D','E','F']答案

C

4.(2024届名校协作体联考,9)有一组数据4,2,6,3,1,5按序入栈,则出栈的顺序可能是

(

)A.4,2,5,3,1,6B.1,3,5,2,6,4C.6,4,2,3,5,1D.6,2,4,3,1,5答案

D

5.(2024届强基联盟联考,11)执行下列Python程序代码,若输入的数据为"ABCDE",则输

出的结果不可能是

(

)fromrandomimportrandintst=['']*10;top=-1;out=''s=input('s=')whiles:flag=randint(0,1)ifflag==1:top+=1;st[top]=s[0]s=s[1:]eliftop!=-1:out+=st[top];top-=1whiletop!=-1:out+=st[top];top-=1print(out)A.CEDABB.BDECAC.ABCEDD.DCBEA答案

A

6.(2024届百校起点调研测试,11)有如下Python程序:q=[0]*6q[0]=1head=0;tail=1whiletail<len(q)-1:x=q[head]ifx%2==0:q[tail]=x//2tail+=1else:q[tail]=x*2q[tail+1]=x*3tail+=2head+=1程序运行后,tail-head的值为

(

)A.3B.4C.5D.6答案

A

7.(2024届浙南名校联盟联考,9)下列关于队列和栈的说法,不正确的是

(

)A.队列是一种先进先出的线性表,可在队尾进行插入操作B.栈的特性是“先进后出,后进先出”C.某栈的入栈的顺序为abc,出栈顺序只有3种D.队列和栈都是线性数据结构,都可以用数组来实现答案

C

8.(2024届浙南名校联盟联考,11)已知字符"a"的ASCII码值为97,有如下Python程序段:que=[""]*20head,tail=0,0foriinrange(3):que[tail]=chr(97+i)tail+=1st=["b","c","d","a"]top=3whilehead<tailandtop>-1:ifst[top]==que[head]:head+=1else:que[tail]=st[top]tail+=1top-=1print(que[head:tail])执行该程序段,则输出的结果是

(

)A.['c','d','c']B.['c','c','d']C.['c','','d']D.['c','d']答案

A

9.(2024届强基联盟统测,12)有如下Python程序段:a=[iforiinrange(1,7)]b=[0]*6head,tail=0,0foriinrange(1,7):cnt=1whilecnt<i:a[tail]=a[head]head=(head+1)%6tail=(tail+1)%6cnt+=1b[a[head]-1]=ihead=(head+1)%6执行该程序段后,b[5]的值为

(

)A.2B.3C.4D.5答案

B

10.(2024浙江1月选考,12,2分)使用列表d模拟链表结构(节点数大于0),每个节点包含数

据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值的绝对值由小到

大排列,如图a所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中

的数值由小到大排列,结果如图b所示。实现该功能的程序段如下,方框中应填入的正

确代码为

(

)

t=hp=d[h][1]whilep!=-1:q=d[p][1]p=qd[t][1]=-1答案

C

11.(2024届嘉兴基测,15)最短路径问题。以m*n个边长为1的正方形组成的矩形,各顶

点按行优先从0开始编号,图a所示为3*2的矩形及顶点编号。从顶点x(起点)经由各正

方形的边移动到顶点y(终点)有多种移动路径,编程求解所有的最短路径。

(1)分析问题,将矩形转换为计算机可处理的数据。可采用列表存储矩形中各顶点的相

邻关系,如图b所示。顶点相邻顶点0[4,1]1[5,0,2]2[6,1,3]3[7,2]4[0,8,5]...图b编写函数init,根据横向和纵向的正方形数量,返回所有顶点及其所有的相邻顶点数

据。完善程序,在划线处填入合适的代码。definit(m,n):tot=(m+1)*(n+1)

#顶点总数lst=[[]foriinrange(tot)]foriinrange(tot):ifi>m:lst[i].append(i-m-1)ifi<(m+1)*n:lst[i].append(i+m+1)ifi%(m+1)!=0:lst[i].append(i-1)ifi%(m+1)!=m:

returnlst(2)分析问题,查找所有从起点到终点的最短路径。例如:查找从起点1到终点10的所有

最短路径,可先查找终点10的所有相邻顶点(6,9,11),然后再逐个查找顶点6、9、11的相邻顶点,直到查找到起点1,获得所有最短路径,如图c所示,共有3条长度为3的最短路

径,分别为1→2→6→10,1→5→6→10,1→5→9→10。若从起点4到终点11,共有

条最短路径。

(3)分析问题,存储查询到的路径。可采用链表结构保存路径数据,例如:查找从起点1到终点10的所有最短路径,首先将终点10的数据[10,0,-1]保存在path[0]中,然后将其相邻

顶点6、9、11的数据保存到path中,path[i][0]保存顶点的编号,path[i][1]保存当前顶点

到终点的距离,path[i][2]保存下一顶点在path中的位置,其值为-1表示当前顶点为终

点。编写函数print_path,输出所有的最短路径。完善程序,在划线处填入合适的代码。defprint_path(x,path,length):#为起点编号,length为path中有效元素个数cnt=0foriinrange(length):ifpath[i][0]==x:cnt+=1s="最短路径"+str(cnt)+":"v=path[i]while

:s=s+str(v[0])+","v=path[v[2]]s=s+str(v[0])+"。"print(s)(4)实现上述功能的Python程序如下,运行结果如图d所示。请在划线处填入合适的代码。请输入起点:0请输入终点: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。图dm=3

#横向正方形数量n=2

#纵向正方形数量mtx=init(m,n)x=int(input("请输入起点:"))y=int(input("请输入终点:"))path=[[]foriinrange(999)]passed=[False]*len(mtx)#保存顶点是否已途经①

dis=0;head=0;tail=0path[tail]=[y,0,-1]tail+=1passed[y]=Truewhilenotfound:dis+=1pass_dis=[False]*len(mtx)tmp=tailforiinrange(head,tail):v=path[i]fordinmtx[v[0]]:ifnotpassed[d]:path[tail]=②

tail+=1pass_dis[d]=Trueifd==x:found=Truehead=tmpforiinrange(len(mtx)):#标记已途经的顶点if③

:passed[i]=True#输出结果print_path(x,path,tail)答案

(1)lst[i].append(i+1)

(2)4

(3)v[2]!=-1或v[2]>=0

(4)①found=False②[d,dis,

i]③pass_dis[i]或pass_dis[i]==True12.(2022A9协作体返校考,16)字符串分段。输入一串仅由小写字母组成的字符串s,将

这个字符串划分为尽可能多的小片段,要求同一个字母只出现在其中的一个片段中,

并按照分段顺序逐行输出分段结果。程序运行界面如下:请输入一串仅包含小写字母的字符串:asdasmhjhhasdasmhjhh(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。s=input("请输入一串仅包含小写字母的字符串:")c=0p=[-1]*52#数组p用来记录各个小写字母出现的起始位置和结束位置#a[0]记录a出现的起始位置,a[1]记录a出现的结束位置,依此类推foriinrange(0,len(s)):#记录各字符第一次和最后一次出现的位置a=①

ifp[2*a]==-1:p[2*a]=ielse:p[2*a+1]=iforiinrange(0,26):ifp[2*i]>p[2*i+1]:p[2*i+1]=p[2*i]#只出现一次的字符,起始位置就是结束位置ifp[2*i]!=-1:c+=1foriinrange(0,c):#将字符位置按照出现的起始位置升序排序forjinrange(25,i,-1):ifp[2*j]>-1:ifp[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]#字符串分段foriinrange(1,c):ifp[2*i]<t2andp[2*i+1]>t2:③

elifp[2*i]>t2:print(s[t1:t2+1])t1,t2=p[2*i],p[2*i+1]print(s[t1:t2+1])(2)运行程序后,若输入的字符串s为"hshjhqueeqabaa",输出的结果一共

行,其中第

二行显示结果为

。答案

(1)①ord(s[i])-97或ord(s[i])-ord("a")②p[2*(j-1)]==-1③t2=p[2*i+1]

(2)3;queeq13.(2022Z20名校联盟联考,15)校学生会要从两个候选人A和B中选举一个会长,每个

候选人都有自己的支持方。现在以轮为过程来进行选举,在每一轮选举中,当前成员

可以禁止另一位成员的选举权,即让另一位成员在这一轮和随后的几轮中都丧失选举

权。在选举过程中,一旦有选举权的成员都来自同一个阵营,则该阵营胜利。字母A和B分别代表两位候选人,输入一个字符串代表每个成员的阵营,例如输入

“ABB”,则输出结果为B,即候选人B为会长。说明:第一轮中,第一个成员(A)可以让第二个成员(B)失去选举权,第二个成员(B)会被

跳过,因为他的选举权被禁止,第三个成员(B)可以让第一个成员(A)失去选举权,因此在第二轮只剩下第三个成员(B)拥有选举权,则输出结果为B,即候选人B为会长。(1)若输入“ABABB”,则会长为

。(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。s=input("请输入投票字符串:")queA=[""]*100;queB=[""]*100headA=headB=0tailA=tailB=0n=len(s)foriinrange(n):if①

:queA[tailA]=itailA+=1else:queB[tailB]=itailB+=1while②

:ifqueA[headA]<queB[headB]:queA[tailA]=queA[headA]+ntailA+=1else:queB[tailB]=queB[headB]+ntailB+=1headA+=1;headB+=1if③

:print("B")else:print("A")答案

(1)A

(2)①s[i]=="A"②headA!=tailAandheadB!=tailB③headA==tailA14.(2022Z20名校联盟