2023年11月台州一模信息技术卷完美解析

绝密★考试结束前（23 年 11 月）
台州市 2023 年 11 月第一次质量评估试题 技术试题
第一部分 信息技术完美解析（共 50 分）
一、选择题（本大题共 12 小题，每小题 2 分，共 24 分。每小题列出的四个备选项中只有一个是符合 题目要求的，不选、多选、错选均不得分）
1.下列关于数据、信息和知识的说法，正确的是
A.数据的表现形式只有数字和文字
B.同一种信息的获取途径和方法可以不同
C.通过搜索引擎搜索出来的内容都是知识
D.信息的价值不会因为时间的变化而改变
(
【答案】
B
【解析】
本题主要考查数据、信息和知识的理解。
选项
A
，数据的表现形式除数字和文字外，还包括音频、图像、视频等；
选项
B
，正确；
选项
C
，通过搜索引擎搜索出来的内容可以是数据、信息
、知识等；
选项
D
，信息具有时效性，价值会因为时间的变化
而改变。
)
阅读下列材料，回答第 2 至 4 题：
杭州亚组委推出的“亚运会票务管理系统”，用户可使用移动终端等设备，通过浏览器进行实名注册 登录，选择相应赛事及座位号后，使用电子支付方式进行支付，即完成购票。生成的电子票会发送至用户 终端设备。系统使用了 web 漏洞自动防护技术，降低网页篡改、数据泄露等风险，并且采取多种加密技术 保护个人信息。亚组委也在线下设置了多个门票代售网点，方便群众购买纸质门票。用户持电子票或纸质 门票均可到会场检票设备扫票入场。
2.下列关于该系统组成的说法，正确的是
A.该票务系统属于系统软件
B.该系统网络架构模式采用 C/S 架构
C.移动终端属于该系统的硬件设备
D.该系统的用户是购票成功的人员
(
【答案】
C
【解析】
本题主要考查信息系统组成相关知识的理解。
选项
A
，该票务系统属于应用软件，应用软件是为了某种特定用途而开发的软件，可以满足不同领域、不
同问题的应用需求，如办公软件、工具软件、管理软件等；
选项
B
，通过浏览器进行实名注册登录，访问确定为系统网络架构模式采用
B/S
架构；
选项
C
，正确；
选项
D
，用户除包括信息系统的使用者，还有计算机和非计算机设备的操作与维护人员、程序设计员、数
据库管理员、系统分析员等。
)
台州市技术选考试题 第 1 页 共 15 页
3.结合上述材料，下列关于信息系统功能和应用的说法，不正确的是
A.用户注册过程包含了系统的数据收集和输入功能
B.线上购票跨越时空限制，给用户带来了方便
C.用户的购票数据保存在检票设备中，方便其快速人场
D.设置线下代售网点，是一种解决“数字鸿沟” 的方法
(
【答案】
C
【解析】
本题主要考查信息系统功能和应用的理解。
选项
C
，用户的购票数据保存在服务器的数据库中，说法。
)
4.下列关于该信息系统安全的说法，正确的是
A.加密技术的使用是为了保证系统数据的完整性
B.用户在登录该系统时获得的短信验证码属于静态口令
C.管理员和普通用户的用户权限不同，是身份认证技术应用的一种体现
D.漏洞自动防护技术的使用，是为了降低系统被黑客及病毒入侵的风险
(
【答案】
D
【解析】
本题主要考查信息系统安全相关知识的理解与记忆。
选项
A
，加密技术的使用是为了保证系统数据的安全
性；
选项
B
，用户在登录该系统时获得的短信验证码属于动态口令；
选项
C
，管理员和普通用户的用户权限不同
，是访问控制技术应用的一种体现，说法不正确；
选项
D
，正确。
)
5.下列关于人工智能的说法，不正确的是
A.某应用中的语音识别技术属于人工智能的应用
B.人工智能技术对经济发展、社会进步都有巨大的推动作用
C.通过模仿人类大脑中神经元之间的复杂交互来进行认知推理，属于符号主义的表现
D.AlphaGo Zero 不依赖人类棋手数据而在自我博弈中不断提升棋力，属于强化学习机制
(
【答案】
C
【解析】
本题主要考查人工智能概念的理解，人工智能方法的辨识。
选项
C
，通过模仿人类大脑中神经元之间的复杂交互来进行认知推理，属于联结主义的表现。
)
6.某多选题有 A 、B 、C 三个选项，程序阅卷时，各选项采用 True和 False 来表示是否进行了选择（例如： 变量 a 的值为 True 时，表示选择了 A 选项；变量 b 的值为 False ，则表示未选择 B 选项） 。若该题正确 答案为“BC” ，下列表达式中能判定考生该题答案全部正确的是
A. a and b and c
B. a or b and c
C. not a and b and c
D. not a or b and c
台州市技术选考试题 第 2 页 共 15 页
(
【答案】
B
【解析】
本题主要考查逻辑运算符的运用。
考生该题答案全部正确，即
a
值为
False
，
b
，
c
值为
True
同时成立，确定答案为
C
。
)
7.斐波那契数列(1 、1 、2 、3 、5 、8 、13 、21 、34……) ，其特点是从第三项开始，每一项都是前面两项的和。 用流程图描述“求斐波那契数列第 n 项值(n>2)”的部分算法如第 7 题图所示，则虚线框中应该填入的是
第 7 题图
(
【答案】
B
【解析】
本题主要考查流程图分析及迭代算法。
循环体中
i←i+1
语句顺序不影响运行结
果，主要考虑
a
，
b
，
c
值的迭代过程，将
b
值及计算出的
c
值依次
赋值给
a
，
b
，然后通过新的
a
，
b
值计算出
c
值，确定答案为
B
。
)
8.使用数组存储某二叉树的形式如第 8 题图所示，下列描述正确的是
A.该二叉树的后序遍历为 BDCA
B.该二叉树的深度为 2
C.该二叉树是一棵完全二叉树
D.该二叉树的叶子节点个数为 3
(
【答案】
A
【解析】
本题考查二叉树。
结合存储结构，画出二叉树
，所以后序遍历屎
BDCA
，深度是
3
，不是完全二叉树，叶子节点数
2
。所以选
A
。
)
9.有如下 Python 程序段：
台州市技术选考试题 第 3 页 共 15 页
kcy=int(input())
i=0;j=len(a)-1
s=""
while i<=j:
m=(i+j+1)//2
if key==a[m]:
break
if keyj=m- 1
else:
i=i+1
s+=str(a[m])+","
print(s[:- 1])
若数组元素 a 的值为[6,15,18,20,25,30,35,38,41,46]，输入正整数 key 值，执行该程序段，输出的值可能是
A.30,20 B.30,41,38 C. 25,15,6 D. 25,38,41
(
【答案】
B
【解析】
本题考查二分查找。
a
种一共
10
个元素，下标从
0
到
9
，画出二叉树
，第一个访问的一定是
a[5]
即
30
，
因此排除
CD
选项。
A
选项，仅访问
a[5]
和
a[3]
，从
图中看出是不可能的。
)
10.定义如下函数：
def DK(n):
if n<8:
(
#
①
)return str(n)
else:
rm=str(n%8)
return rm+DK(n//8)
以下关于该函数的说法正确的是
A.该函数使用了枚举算法
B.DK(43)返回的值为"53"
C.该函数的功能是将十进制数 n 转换为八进制数
D.调用该函数时,无论 n 为任何正整数值,①处语句均只执行 1 次
(
【答案】
D
【解析一】
本题考查递归算法。
B
选项，
DK
(43)-->3+
DK
(5)-->35
。
C
选项，
43
的八进制应该是
53
，所以功能是转换成八进制的逆结果。
【解析二】
)
台州市技术选考试题 第 4 页 共 15 页
(
本题考查递归算法的相关知识。
A
选项该函数使用了递归算法不属于枚举算法，
A
选项错误；
B
选项“
DK
(43)
”返回
值是
35
，
B
选项错误。
C
选项该函数并没有实现十进制转八进制的功能，
比如“
DK
(43)
”转成
八进制应该是
53
，但结果却是
35
，
C
选项错误；故答案选
D
。
D
选项中①处语句属于终止递推的边界
语句，故只执行一次。
)
11.利用冗余压缩的方法对字符串进行压缩,例 如字符串“aabbbcccd” ，压缩后“a2b3c3d1”。实现上述压缩功 能的 Python 程序如下:
s=input("请输入长度大于 1 的待压缩字符串:")
ys=s[0]; k=1
for i in range(1,len(s)):
print("压缩后的结果为:",ys)
在程序方框处应填入的代码是
A.
if s[i]==s[i- 1]:
k+=1
else:
ys=ys+st(k)+s[i]
k=1
if i==len(s)-1:
ys+=str(k)
C.
if s[i]==s[i- 1]:
k+= 1
elifi!=len(s)- 1:
ys=ys+st(k)+s[i]
k= 1
else:
ys+=str(k)
B.
if s[i]==s[i- 1]:
k+=1
else:
ys=ys+st(k)+s[i]
k=1
if i==len(s)-1:
ys+=str(k)
D.
if i!=len(s)- 1 and s[i]!=s[i- 1]:
ys=ys+st(k)+s[i]
k= 1
elif s[i]==s[i- 1]:
k+= 1
else:
ys+=str(k+1)
(
【答案】
B
【解析一】
本题考查字符串的压缩。
A
选项，最后一串字符都相同，
else
语句不执行，
if
i
==
len
(s)-
1
就无法执行。
C
选项，例
如
aab
情况，最终
i=2
时，遇
b
字符，执行运行
else
语句，
ys
结果是
a2
，无法给出
b
字符。
D
选项，
ys
+=
str
(k+1)
错
误，
k
才
表示字符的个数。
【解析二】
本题考查栈字符串压缩的相关知识。
本题虽然说是一个字符串压缩的问题，但其实是一道对分支结构
if
语句理解的问题。解
本题有一个关键问
题就是对最后连续相同字符怎么处理，例如字符串
aabbb
进行压缩后是
a2b3
，当
i
遍历到最后一个元素
b
的时候，发现和前一个元素
b
相等，由于
ACD
选项均只使用了一个
if
语句来做判断，这样只会有一个入口，
)
台州市技术选考试题 第 5 页 共 15 页
就是 k+1，而不再对 ys进行累加。只有 B 选项在最后进行 k+1 以后，再去用一个 if 语句判断是否遍历到最 后一个元素了，如果是则对 ys 进行累加，故 B 选项正确。
12.有如下 Python 程序段：
s=input("请输入一个仅由小写英文字母组成的字符串:")
st=[""]*len(s); top=-l
t=[-1]*26
for i in range(len(s)):
id=ord(s[i])-97
if t[id]==- 1:
top+= 1
st[top]=s[i]
t[id]=top
else:
first=t[id]
while top>=first and top!=-1:
num=ord(st[top])-97
t[num]=- 1; top-= 1
print(st[:top+1])
若从键盘输入的值为"hellopython" ，则输出的值为
A.['o','n']
B.['h','e','n']
C.['h','e','l','o','p','y','t','n']
D.['h','e','o','p','y','t','h','o','n']
(
【答案】
A
【解析一】
本题考查栈。
t[
id
]
表示
26
个字母中第
id
个字母出现在栈中的最后位置。当某字
母未出现时，入栈，并将在栈中的最后位
置记录在
t
中。否则将比该字符在栈中位置之后（包含自己）的元素全部出栈，并将
t
值设置为
-1
。根据上
述思想，栈的变化是
[h,e,l]-->[h,e]-->[h,e,o,p,y,t]-->[]-->[o
,n]
。
【解析二】
本题考查栈基本操作的相关知识。
本题算法思想是将字母入栈的同时记录字母的状
态，如果出现重复字母入栈的情况，则开始出栈，一直出
栈到重复字母本身，或者栈内为空为止。例如字符串“
hellopython
”，首先字母“
h
”、“
e
”、“
l
”入栈，
遇到重复字母“
l
”则出栈一次，然后继续入栈“
o
”、“
p
”、“
y
”、“
t
”，遇到重复字母“
h
”则全部出
栈，最后入栈字母“
o
”、“
n
”程序结束，故答案选
A
。详解如下：
)
台州市技术选考试题 第 6 页 共 15 页
二、非选择题（本大题共 3 小题，其中第 13 小题 8 分，第 14 小题 8 分，第 15 小题 10 分）
13.小峰做了一个“搭建学生寝室管理系统”的实验，该系统可通过人脸识别、指纹识别、校园卡等方式模 拟进出寝室管理，并将进出数据发送给服务器。通过浏览器可以查看学生在寝、离寝情况。小峰选择的 硬件有：智能终端、IoT 模块、摄像头、指纹采集仪、射频识别设备、进出口闸机、服务器等。该系统 结构示意图如第 13 题图所示，其中 Web 服务器端程序采用 Flask Web 框架开发。
第 13 题图
（1）下列硬件设备中，属于执行器的有 （单选，填字母： A.摄像头 / B.指纹采集仪 / C.射频识
别设备 / D.进出口闸机）。
（2）下列关于该系统应用软件的网络架构，说法正确的是 （单选，填字母：A.客户端无需安装专 用软件，升级维护方便 / B.对服务器要求较低 / C.能够降低系统通信开销）。
（3）下列功能需要在服务器端程序中实现的是 （多选，填字母：A.原始指纹数据的采集 / B.在 数据库中查找指纹特征数据 / C.闸机的开关 / D.根据浏览器的请求返回数据）。
（注:全部选对的得 2 分，选对但不全的得 1 分，不选或有选错的得 0 分）
（4）小峰基于 Flask Web 框架编写服务器端程序，部分代码如下。编写完后，若要通过浏览器获取视图 函数 entry()返回的页面，则访问的 URL 是 http:// 。
#导入 Flask 框架模块及其它相关模块，代码略
app= Flask(__ name__ )
@app.route('/ ')
def index():
#在模板文件上显示从数据库读取的入寝、离寝学生数据，代码略
@app.route('/dorm', methods=['GET', 'POST')
def entry():
#从数据库读取对应班级学生的在寝、离寝数据，并返回页面，代码略
#服务器其它功能，代码略
台州市技术选考试题 第 7 页 共 15 页
if_name_ =='_main_'
app.run(host = ' 10.16.1.18', port = 8080)
（5）小峰对系统进行动态测试，使用校园卡刷卡，闸机能正常打开，在浏览器中查看系统首页，页面中 标题、表格等内容能正常显示，但却未显示刷卡数据，刷新后仍不变(Web 服务器数据库的数据读写 功能正常)。从服务器端的程序角度说明造成上述问题的原因有 、 （注：回答 2 项，1 项正确得 1 分）。
(
【答案】
（
1
）
D
（
1
分）
（
2
）
A
（
1
分）
（
3
）
BD
（
2
分）
（
4
）
10.16.1.18
:8080/dorm
（
2
分）
（
5
）
①
index
模块
(
主页路由对应的模块
)
中从数据库中读取数据代码有误
②
index
模块
(
主页路由对应的模块
)
中将参数传递给模板文件的代码有误
③主页模板文件中，显示服务器传递的数据代码有误
④其他模块中，将在宿、离宿数据写入数据库代码有误
(
只说代码有误不给分，需要指出具体哪个位置及哪个内容的代码有误
)
（
2
分）
【解析】
本题考查信息系统搭建的综合知识。
（
1
）执行器是负责输出的硬件设备，选项中
ABC
均属于输入设备，只有进出口闸机属于输出设备，故选
D
。
（
2
）根据题干中：通过浏览器可以查看学生在寝、离寝情况，可知该系统采用
B/S
开发模式，因此不需要
安装客户端程序。而选项
BC
是
C/S
开发模式的特点，故选
A
。
（
3
）指纹数据的采集和闸机的开关，只需要通过智能终端的程序控制即可实现。在数据库中查找指纹特征
数据、根据浏览器的请求返回数据，这两个功能都需要在
Web
服务器的配合下使用。
（
4
）由于路由和视图函数是配合使用的，根据代码
可知，视图函数
entry()
的前面就是其路由的子页面
“/dorm
”，
然后根据
IP
地址（
host
）和
port
端口号，可以确定答案。
（
5
）只要理由合理均可给分，但须指出具体原因。
)
14.小明通过调查问卷收集了食堂满意度情况数据，保存在“data.csv”文件中，如第 14 题图 a 所示。
第 14 题图 a
第 14 题图 b
台州市技术选考试题 第 8 页 共 15 页
第 14 题图 c
为统计分析每个调查项目不同选项的人数及不满意率，编写 Python程序。回答下列问题：
（1）统计每一项调查内容的总票数、满意、一般及不满意人数，程序运行结果如第 14 题图 b 所示，请
在划线处填入合适的代码。
import pandas as pd
import matplotlib.pyplot as plt
plt.rcParams["font.sans-serif"]=["SimHei"] df=pd.read_csv("data.csv",encoding="utf-8")
cols=df.columns[1:]
poll=len(df)
#导入 pandas 模块
#导入 pyplot 模块
#设置图表显示中文字体
#读取 csv 文件中的数据
data={("调查项目":[],"总票数":[],"满意":[],"一般":[],"不满意":[]}
for colname in cols:
dfc=df.groupby( ① ,as_index=False)["序号"].count()
data["调查项目"].append(colname)
data["总票数"].append(poll)
for j in dfc.index:
name=dfc.at[j,colname]
data[name].append( ② )
df2=pd.DataFrame(data)
print(df2)
（2）计算每个项目的“不满意率”(=“不满意”/“总票数” * 100) ，并使用柱形图分析每个项目的“不满意率” 情况，如第 14 题图 c 所示，请在划线处填入合适的代码。
df2["不满意率(%)"]= ①
x= ②
y=df2["不满意率（%）"]
plt.figure(figsize=(8,4))
plttitle("食堂调查问卷不满意率（%）情况")
plt.bar(x,y,label="不满意率（%）")
plt.legend()
(
plt
.
show
()
【答案】
（
1
）
①
colname
（
2
分）
②
dfc.at[j,"
序号
"]
或
dfc["
序号
"][j]
或
dfc.
序号
[j]
（
2
分）
（
2
）
①
df2["
不满意
"]/df2["
总票数
"]*100
或
df2["
不满意
"]/poll*100
或
df2.
不满意
/df2.
总票数
*100
或
df2.
不
满意
/poll*100
或其它等价答案
（
2
分）
②
df2["
调查项目
"]
或
df2.
调查项目
（
2
分）
【解析一】
本题考查
pandas
数据处理
)
台州市技术选考试题 第 9 页 共 15 页
（1） ① 根据 14 题图 b 的结果，再结合代码（本以为会用筛选），遍历每个项目，进行分组后计数，可 以得到相应的结果。所以这里填的是 colname
② "满意","一般","不满意" 的相应数据，存放在"序号"列对应的位置：dfc.at[j,"序号"]，这里不是更改 数据，dfc["序号"][j] 或 dfc.序号[j]亦可。
（2） ① 利用其中二列的数据，就可以得到新增列的相应数据：df2["不满意"]/df2["总票数"]*100 ② 根据第 14 题图 c ，这里应该是：df2["调查项目"]
【解析二】
本题考查 pandas及字典、列表等相关知识。
（1）①本题的几个关键变量形式如下：
cols ，保存 df 中除第一列以外的所有列标题，即:[‘饭菜质量’,’饭菜价格’,’菜品花样’,’餐厅环境’,’服务质量’, ’ 餐厅整体’]
data={"调查项目" :[],"总票数":[],"满意":[],"一般":[],"不满意":[]}
用于存放项目名称，及各项目分类统计后的计数值。
部分代码解析如下：
for colname in cols: #遍历 cols 中的每个列标题
dfc=df.groupby( ① ,as_index=False)["序号"].count() #按相应列标题分组计数
data["调查项目"].append(colname) #将本次统计的项目追加到字典 data
data["总票数"].append(poll) #data 中追加该项目的总票数
for j in dfc.index: #遍历分组后数据行索引
name=dfc.at[j,colname] #获取 dfc 中第j 行 colname 列的值，如“一般”等
data(name.append( ② ) #相应统计结果追加到字典
df2=pd.DataFrame(data) #将字典转换为 DataFrame 对象。
①空依题意，应按各列分别进行分组计数，因此外循环依次遍历项目，每取一个项目 colname 就以它为 分组字段进行计数，①处填 colname
②以 name 为键，追加该项目的计数结果，②处填：dfc.at[j,”序号”],注意此时的序号列是统计结果，例 如， 以“饭菜质量”为分组字段进行分组后，统计结果如下图所示：
最终字典 data 中数据形式如下：
（2） ①由题干提示可知，此空填：df2["不满意"]/poll*100
② 观察图 c 可知，x 轴数据来自“调查项目” ，填：df2["调查项目"]
本题统计时没有按常理出牌，对不常操作的同学来讲，要描述出不同变量的结构比较困难。也提醒各 位同学，pandas 模块的复习要理论与实践相结合。
15.某工厂的业务较多，每个业务 i 都有对应的截止时间ti 以及收益 vi ，工厂每天最多能完成 k 个业务，且 每个业务所需的加工时长相同。由于业务量多，有时候无法完成所有的业务，因此工厂管理者需要对一 段时间内的业务进行规划安排， 以实现工厂累计收益的最大化。
例如工厂 3 天内的业务明细如第 15 题图 a 所示，已知工厂每天能够完成的业务量 k 为 2 。为了实 现 3 天的累计收益最大化 ，工厂安排的业务方案如第 15 题图 b 所示，这样工厂能够获得最大累计收 益为 105。
台州市技术选考试题 第 10 页 共 15 页
编写程序，实现在任意时间段内，根据每个业务的截止时间和收益，统计工厂在该时间段内的最大 累计收益。
第 15 题图 a 第 15 题图 b
请回答下列问题：
（1）如第 15 题图 a 所示，若工厂每天能够完成的业务量 k 为 3，则工厂在 3 天内获得的最大收益为 。
（2）定义如下 insert(lst,head,pos)函数，参数 lst 是一个由列表模拟的链表结构数据，其每个节点由收益数 据和指向下一个位置的指针组成；参数 head 是其中一条链表的头指针，由该指针构建的链表已经按 收益数据升序排列；参数 pos 是某个节点的指针。函数功能是将 pos 节点插入到 head 指针指向的链 表中，并保持链表按收益数据升序排列，最后返回头指针数据。
def insert(lst,head,pos):
p=head
while p!=- 1 and lst[p][0]q=p
p=lst[p][1]
if p==head:
lst[pos][1]=head
head=pos
else:
lst[pos][1]=p
▲
return head
①若函数加框处代码误写为“lst[p][0]②请在划线处填入合适的代码。
（3）实现对每个业务完成时间的合理安排，使得工厂获得最大累计收益的部分 Python 程序如下，请在划
线处填入合适的代码。
def pushlst(info,lst,cur,v):
if info[cur][1]lst.append([v,-1]) pos=len(lst)- 1
if info[cur][0]==- 1: ①
#cur 表示当前时间
#安排在当天的业务数量未满
#列表 lst 追加一个元素
台州市技术选考试题 第 11 页 共 15 页
else:
info[cur][0]=insert(lst,info[cur][0],pos)
info[cur][1]+=1
else:
pos=info[cur][0]
ifv#如果 cur>0，尝试将当前业务提至前一天完成，代码略
else:
tmpv=lst[pos][0] #获取原安排中收益最少的业务收益
lst[pos][0]=v
p=lst[pos][1]
info[cur][0]=insert(lst, ② ,pos)
#如果 cur>0 ，尝试将原安排中收益最少的业务提至前一天完成，代码略
'''
先输入规划安排的天数 n 和每天能够处理的最大业务量 k，代码略。
依次输入 m 个业务的截止时间 t（t ≤n ）和收益 v ，存储在数组 tran 中，如：[[1,25][1,10][2,15]]，表 示共有 3 个业务，第一个业务的截止时间为 1，收益为 25 …… ，代码略
'''
info=[]; lst=[]; k=0
for i in range(n):
info.append([-1,0])
while kcur=tran[k][0]; v=tran[k][1] pushlst(info,lst,cur- 1,v)
k+=1
s=0
for i in range(n):
p=info[i][0]
while p!=- 1:
s+= ③
p=lst[p][1]
print("最大收益为：",s)
#列表 info 追加一个元素
#获取截止时间和对应收益
(
【答案】
（
1
）
135
（
1
分）
（
2
）
①
B
（
1
分）
②
lst[q][1]=pos
（
2
分）
（
3
）
①
infor[cur][0]=pos
或
infor[cur][0]=len
(lst)-1
（
2
分）
②
p
（
2
分）
③
lst[p][0]
（
2
分）
【解析一】
本题综合考查单链表的初始化和插入等操作。
第（
1
）题根据题意模拟，先将所有业务按戒指时间分组并排序，如下表所示：
截止时间
任务收益
)
台州市技术选考试题 第 12 页 共 15 页
1 10 ，15 ，25
2 15 ，20 ，25 ，30
3 5
(
当
k=3
时，尝试将第
2
天中收益最小的业务
15
提前到
第
1
天完成，即顶替第一天中收益为
10
的业务，如
)
(
下表所示：
)
截止时间 任务收益
1 10 ，15 ，15 ，25
2 15 ，20 ，25 ，30
3 5
(
如此，每天最多完成
3
个业务，最大收益为当下所有业务收益之和
135
。
)
(
第（
2
）题的代码功能相对独立，考察在有序链表中数据的插入，并维护链表有序的特性，是常见的考察方
)
(
向。第①问加框处代码改写后，
由于不再判
断
p!=-1
，即无法保证该节点是否存在。在遍历的过程中若链表
)
(
为空，或访问尾节点后继续向后遍历都会出现
这种情况。在所有选项中，只有
B
选项表示的链表，要求将
)
(
节点
pos
=0
、值为
5
，插入到头节点
head
=2
的有序链表
2→3→4→
中会出现遍历结束后
p=-1
的情况，因此
)
(
答案为
B
；第②问是常规的节点插入，当
p!=
head
时，满足
q→p
的关系，即
p
是
q
的后继、
q
是
p
的
前驱。
)
While 循环结束后 lst[q][0](
即答案为
lst
[q][1] =
pos
。
)
(
第（
3
）题考察多链表数组的维护。
info
数组存储了
n
个链表的头节点索引和链表长度，
info
数组的结构如
)
(
下：
info
=[
[
head
1,
len
1],
[
head
2,
len
2],
… ,
[
headn
,
lenn
] ]
，其中
info
[i][0]
表示截止时间为
i
的所有业务所组成
)
(
链表的头节点索引（链表按业务收益升序，即该索引
指向收益最低的业务
），
info
[i][1]
表示已记录了截止时
)
(
间为
i
的业务的数量，最大为
k
。在该结构下，第①空链表为空
时，直接将该节点作为头节点插入到链表中，
)
答案 info[cur][0] = pos；第②空删除原头节点之后， 以头节点的后继索引作为该链表新的头指针执行 pos 节
点的插入， 由于 p= lst[pos][1]（pos 是原链表的头指针），因此②答案为 p；第③空依次遍历 n 个链表累加
(
收益，答案
lst
[p][0]
。
)
台州市技术选考试题 第 13 页 共 15 页
【解析一】
本题考查基本数据结构链表的基础操作。
（1）根据截止时间梳理各个业务，如下表所示
业务序号 截止时间 收益 vi 完成时间 业务序号 截止时间 收益 vi
3 1 25 第一天完成 3 1 25
5 1 10 2 2 15
7 1 15 7 1 15
4 2 30 第二天完成 4 2 30
6 2 20 6 2 20
8 2 25 8 2 25
1 3 5 第三天完成 1 3 5
表 1 表 2
当 k=3 时，截止时间为 2 的业务多一个，剔除序号 2 的业务并将其安排到前一天，替换掉收益最低的序号 为 5 的业务。得到总的收益率最大为 135
（2）①根据题干描述，insert 函数的功能是将 pos节点插人到 head 指针指向的升序链表中， while p!=- 1 and lst[p][0]q=p
p=lst[p][1]
上述代码段的功能用来遍历链表，查找插入 pos 节点的位置。如将循环条件改为“lst[p][0l② 第二空所在的代码段实现的功能是将 pos节点，插入到链表，具体解析如下
.......
if p==head: #说明 pos 节点插入的 head 之前
lst[pos][1]=head #pos 节点的指针域指向 head
head=pos #更新 head 的位置
else:
lst[pos][1]=p #在 q 、p 之间插入 pos 节点,pos 节点的指针域指向 p
lst[q][1] =pos #q 节点的指针域指向 pos
..........
(1) 在第①②空所在的代码段中， 自定义函数 pushlst 的功能将每天的业务以升序链表的形式存储。n 天的业务生成 n 个链表，info[cur][0]表示每个链表的头指针，infoc[cur][1]表示每天安排的业务数量。具体代 码解析如下：
def pushlst(info,lst,cur,v):#cur 表示当前时间
if info[cur][1]lst.append([v,- 1])#列表 lst 追加一个元素
pos=len(lst)- 1 #pos 表示新节点的位置
if info[cur][0]==- 1: #表示第 cur+1 天的链表没有安排业务
info[cur][0] = pos #将 pos 节点作为当前链表的头结点
else:
info[cur][0]=insert(lst,info[cur][0],pos) #否则，将将 pos 节点插入到 lst 链表 info[cur][1]+=1 #第 cur+1 天的业务数量+1
else: #表示第 cur+1 天完成的任务已经达到 k 个
pos=info[cur][0] #pos 记录第 cur+1 天业务链表头指针
台州市技术选考试题 第 14 页 共 15 页
(
ifv
<
lst
[
pos
][0]:#v<
lst
[
pos
][0]
表面当前业务的效益少于头结点业务的效益
#
如果
cur
>0,
尝试将当前业务提至前一天完成
,
代码略
else
:
tmpv
=
lst
[
pos
][0] #
获取原安排中收益最
少的业务收益
lst
[
pos
][0]=v #
修改
pos
结点业务的效益
p=
lst
[
pos
][1] #p
指向下一个节点
info
[
cur
][0]=
insert
(
lst
,p,
pos
) #
从
p
节点开始遍历，将
pos
节点插入第
cur
+1
天
的链表中
#
如果
cur
>0
，尝试将原安排中收益最少的业务提至前一天完成，代码略
③最后一空所在代码段用来计算
n
天的总效益，
p
指向每一链表的头指针，通过遍历每一个链表，
s
记录
已经安排的所有业务的效益和，所以答案为
lst
[p][0]
。
)
台州市技术选考试题 第 15 页 共 15 页