資源簡介

絕密★考試結束前（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. B.
if s[i]==s[i-1]: if s[i]==s[i-1]:
k+=1 k+=1
else: else:
ys=ys+st(k)+s[i] ys=ys+st(k)+s[i]
k=1 k=1
if i==len(s)-1: if i==len(s)-1:
ys+=str(k) ys+=str(k)
C. D.
if s[i]==s[i-1]: if i!=len(s)-1 and s[i]!=s[i-1]:
k+=1 ys=ys+st(k)+s[i]
elif i!=len(s)-1: k=1
ys=ys+st(k)+s[i] elif s[i]==s[i-1]:
k=1 k+=1
else: else:
ys+=str(k) 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 #導入 pandas模塊
import matplotlib.pyplot as plt #導入 pyplot模塊
plt.rcParams["font.sans-serif"]=["SimHei"] #設置圖表顯示中文字體
df=pd.read_csv("data.csv",encoding="utf-8") #讀取 csv文件中的數據
cols=df.columns[1:]
poll=len(df)
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]調用 insert(lst,head,pos)函數，下列 4組數據中能測試出這一問題的是 （單選，填字母）。
②請在劃線處填入合適的代碼。
（3）實現對每個業務完成時間的合理安排，使得工廠獲得最大累計收益的部分 Python程序如下，請在劃
線處填入合適的代碼。
def pushlst(info,lst,cur,v): #cur表示當前時間
if info[cur][1]lst.append([v,-1]) #列表 lst 追加一個元素
pos=len(lst)-1
if info[cur][0]==-1:
①
臺州市技術選考試題 第 11 頁 共 15 頁
else:
info[cur][0]=insert(lst,info[cur][0],pos)
info[cur][1]+=1
else:
pos=info[cur][0]
if v#如果 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]) #列表 info 追加一個元素
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)
【答案】
（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=[ [head1, len1], [head2, len2], … , [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節點的數據域大于鏈表中所有的節點時，循環無法正常結束，導致程序出錯。而選項 B，pos指向的
第一個節點的數據域大于鏈表中的其它節點，正好滿足上述情況。
② 第二空所在的代碼段實現的功能是將 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 頁
if v#如果 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 頁

展開更多......

收起↑