資源簡介

絕密★考試結束前（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 頁

展開更多......

收起↑