链表+算法综合二
班级 姓名
1.【202304杭州二模】为分析数据中各元素的变化情况，进行如下定义：
若在数组d中满足d[a]<...d[i+1]>...>d[b]，则从下标a到下标b区间的数据称为一个波峰，下标a到b的距离即为一个波峰的长度(长度≥3）。例如：数组d元素为“78,46,50,37,5,42,6,6,23”，存在2个波峰，分别是从d[1]到d[4]和d[4]到d[6]，波峰长度分别为4和3。
编写程序分析数据，找出所有波峰，按波峰长度降序排序（若波峰长度相同，则按开始下标升序），并输出波峰长度和开始到结束元素下标；若不存在，则输出“不存在波峰”，运行结果如图所示。
请回答下列问题：
(1)根据题意，若数组d元素“23,14,35,31,13,20,3,40,10,10,9”，则最长的波峰长度为 。
(2)执行该程序，若数组d元素为“2,1,1,2”，则处while语句中循环体的执行次数是 。
(3)实现上述功能的程序代码如下，请在划线处填入合适的代码。
#读取待处理数据，保存在数组d中，并显示输出，代码略
mt,i,n=[],1,len(d)
while iwhile ii+=1 ; st=i-1
while id[i-1]:
i+=1
if ① :
continue #跳出本轮循环，然后继续进行下一轮循环
while ii+=1
ln=i-st
if len(mt)==0:
mt.append([ln,st,-1]) #为mt追加一个列表元素
head=0 ; q=head
else:
p=head
while p!=-1 and ② :
q=p ; p=mt[p][2]
if p==head:
mt.append([ln,st,head]) ; head=len(mt)-1
else:
mt.append([ln,st,p])
③
if len(mt)==0:
print("不存在波峰")
else:
print("输出结果(长度:开始下标～结束下标):") ; p=head
while p!=-1:
print(mt[p][0],":",mt[p][1]," ～",mt[p][0]+mt[p][1]-1) ; p=mt[p][2]
(4)使用以下代码替换加框处代码，可以减少链表mt遍历次数的是 （单选，填字母）。
A.if mt[q][0]>ln: B.if mt[q][0]p=mt[q][2] p=mt[q][2]
else: else:
p=head p=head
2.【202304嘉兴二模】某工厂安排了若干条生产计划， 数据存储在Excel文件“task.xlsx”中，数据格式如下图所示，数据以链表形式存储，现要对生产计划进行合理性检查。
检查结果分为如下三种情况（以完成的任务数m=5为例说明）：
①安排合理：完成的任务数大于等于m,且执行过程中无重复任务。例如：计划1完成任务的顺序为：
任务0→任务6→任务4→任务1→任务5→结束（-1），共安排了5个任务。
②任务不足：完成的任务数小于m。例如：计划2完成任务的顺序为：
任务6→任务2→任务0→任务1→结束（-1），只安排了4个任务，出错任务为任务1。
③任务重复：任务安装中存在重复任务。例如：计划3 完成任务的顺序为：
任务7→任务3→任务5→任务1→任务0→任务3→结束，其中任务3重复，出错任务为任务0。
(1)根据题意，上图中计划4的检查结果为 (单选，填字母:A.安排合理/B.任务不足/C.任务重复)。
(2)主程序如下，请在划线处填入合适代码
import pandas as pd
m=int(input('请输入需完成的最少任务数：'))
df=pd.read_excel('task .xlsx')
name=list(df.columns[2:]) #取任务名称
plan=list(df. 计划号 ) #取计划号
task=list(df.values)
#task中的 保存df中的数据，不含标题。格式如右上图所示
for i in range(len(task)):
head=task[i][1]
①
stat,k=check_up(link,head)
if stat==2:
print(plan[i],' ：安排合理，共完成 ',k,' 项任务 ')
elif ② :
print(plan[i],' ：任务重复，出错任务为 ',name[k])
else:
print(plan[i],' ：任务不足，出错任务为',name[k])
(3)函数check_up的功能是用于检查一条生产计划是否合理 ，并返回检查结果请在划线处填入合适代码。
def check_up(link,head):
cnt=1 ; p=link[head] ; pre=p
①
while p!=-1 and p not in finished:
finished.append(p) ; pre = p
②
cnt+=1
if p==-1:
if cntreturn 1,pre
else:
return 2,cnt
elif p in finished:
return 0,pre链表+算法综合二
班级 姓名
1.【202304杭州二模】
(1)4
(2)①2 或 2次
(3)①i==n or d[i]==d[i-1]或等价表达式
②(lnmt[p][1]) 少括号，不得分
③mt[q][2]=len(mt)-1
(4)A
2.【202304嘉兴二模】
(1)C
(2)①link=task[i][2:] ②stat==0
(3)①finished=[head] ②p=link[p]
