2025年程序設計與算法分析考試試卷及答案一、單項選擇題（每題2分，共20分）1.對于遞歸函數T(n)=2T(n/2)+n2，其時間復雜度為（）A.O(n2)B.O(nlogn)C.O(n3)D.O(n2logn)2.以下哪種排序算法在最壞情況下時間復雜度為O(nlogn)？（）A.快速排序B.冒泡排序C.歸并排序D.插入排序3.若二叉搜索樹中插入元素的順序為{5,3,7,2,4,6,8}，則刪除元素5后的根節(jié)點為（）A.3B.6C.7D.44.對于圖的廣度優(yōu)先搜索（BFS），以下說法正確的是（）A.適合尋找最短路徑（邊權相同）B.必須使用棧作為輔助數據結構C.時間復雜度一定高于深度優(yōu)先搜索（DFS）D.無法處理有向圖5.動態(tài)規(guī)劃算法的核心是（）A.貪心選擇性質B.最優(yōu)子結構C.分治策略D.回溯剪枝6.哈希表采用鏈地址法處理沖突時，若負載因子α=0.75，哈希表大小為16，則平均查找長度約為（）A.1B.1.5C.2D.2.57.以下哪個問題不能用貪心算法有效解決？（）A.活動選擇問題B.最小生成樹（Kruskal算法）C.0-1背包問題D.霍夫曼編碼8.設數組A=[3,1,4,2,5]，執(zhí)行堆排序（大頂堆）的初始建堆操作后，數組變?yōu)椋ǎ〢.[5,3,4,2,1]B.[5,4,3,2,1]C.[4,3,5,2,1]D.[5,2,4,1,3]9.對于n個節(jié)點的無向連通圖，其生成樹的邊數為（）A.n-1B.nC.n+1D.2n-110.設字符串S="abacab"，其前綴函數（KMP算法中的部分匹配表）π數組為（）A.[0,0,1,0,1,2]B.[0,0,1,0,1,1]C.[0,1,1,0,1,2]D.[0,0,0,1,1,2]二、填空題（每空2分，共20分）1.設T(n)=T(n-1)+n，T(1)=1，則T(n)的時間復雜度為______。2.快速排序的平均時間復雜度為______，最壞時間復雜度為______。3.若完全二叉樹有100個節(jié)點，則葉子節(jié)點數為______。4.對于帶權有向圖，Dijkstra算法要求邊權______（填寫“非負”“非正”或“任意”）。5.矩陣鏈乘法問題中，若矩陣鏈為A1(2×3),A2(3×4),A3(4×2)，則計算順序A1×(A2×A3)的乘法次數為______。6.設哈希函數H(key)=keymod7，采用線性探測法處理沖突，依次插入關鍵字{15,22,3,10,17}，則關鍵字17的存儲地址為______（地址從0開始）。7.歸并排序的核心操作是______，其空間復雜度為______。三、算法分析題（每題10分，共30分）1.分析以下遞歸函數的時間復雜度，并給出推導過程：```pythondeffunc(n):ifn<=1:return1returnfunc(n-1)+func(n-1)```2.給定一個無序數組arr，設計一個算法判斷是否存在三個不同的索引i<j<k，使得arr[i]<arr[j]<arr[k]。要求時間復雜度O(n)，空間復雜度O(1)。3.已知二叉樹的中序遍歷序列為DBEAFC，后序遍歷序列為DEBFCA，畫出該二叉樹的結構，并寫出其前序遍歷序列。四、算法設計題（每題15分，共30分）1.設計一個算法求解“最長遞增子序列”問題。要求：（1）給出動態(tài)規(guī)劃解法的狀態(tài)定義、狀態(tài)轉移方程；（2）寫出偽代碼；（3）分析時間復雜度。2.給定一個無向圖（用鄰接表表示），設計一個算法判斷該圖是否為二分圖。要求：（1）說明算法思路；（2）寫出具體實現步驟（可用偽代碼或自然語言描述）；（3）分析時間復雜度。五、綜合應用題（20分）某電商平臺需要對用戶的購物行為數據進行分析，其中用戶的點擊序列可以表示為一個整數數組，每個元素代表商品ID。平臺希望找出所有長度為k的連續(xù)子數組的最大值，用于分析用戶的興趣熱點。例如，輸入數組nums=[1,3,-1,-3,5,3,6,7]，k=3時，輸出為[3,3,5,5,6,7]。要求：（1）設計一個時間復雜度為O(n)的算法解決該問題；（2）給出算法的詳細步驟；（3）用Python實現該算法；（4）分析算法的正確性和時間復雜度。答案一、單項選擇題1.A（主定理：a=2,b=2,f(n)=n2，n^(log_ba)=n^1，f(n)是Ω(n^(log_ba+ε))，故T(n)=Θ(f(n))=O(n2)）2.C（歸并排序最壞時間復雜度為O(nlogn)）3.C（刪除根節(jié)點5后，需找到右子樹的最小節(jié)點6，將5替換為6，原右子樹調整后根為7）4.A（BFS使用隊列，適合無權圖最短路徑）5.B（動態(tài)規(guī)劃依賴最優(yōu)子結構）6.B（鏈地址法平均查找長度≈1+α/2=1+0.75/2=1.375，接近1.5）7.C（0-1背包需動態(tài)規(guī)劃，貪心不保證最優(yōu)）8.A（初始大頂堆：父節(jié)點i，子節(jié)點2i+1和2i+2。原數組[3,1,4,2,5]，調整后根為5（索引4），交換后數組變?yōu)閇5,1,4,2,3]，再調整子樹得[5,3,4,2,1]）9.A（生成樹邊數=節(jié)點數-1）10.A（前綴函數π[i]表示S[0..i]的最長相等真前綴和后綴長度。"a"→0；"ab"→0；"aba"→1（"a"）；"abac"→0；"abaca"→1（"a"）；"abacab"→2（"ab"））二、填空題1.O(n2)（T(n)=1+2+…+n=n(n+1)/2）2.O(nlogn)；O(n2)3.50（完全二叉樹葉子節(jié)點數=?n/2?=50）4.非負（Dijkstra無法處理負權邊）5.3×4×2（A2×A3）+2×3×2（A1×結果）=24+12=366.3（H(15)=15%7=1；H(22)=22%7=1（沖突，探測2）；H(3)=3%7=3；H(10)=10%7=3（沖突，探測4）；H(17)=17%7=3（沖突，探測4→沖突，探測5→沖突，探測6→沖突，探測0→沖突，探測1→沖突，探測2→沖突，探測3？不，線性探測是逐個加1，初始地址3，沖突后依次3+1=4（已被10占用），4+1=5（空），所以17存5？原計算錯誤，正確步驟：15→1；22→1沖突→2；3→3；10→3沖突→4；17→3沖突→4沖突→5，故答案為5）（注：原填空第6題答案修正為5，初始分析有誤）7.合并兩個有序子數組；O(n)三、算法分析題1.時間復雜度為O(2?)。推導：遞歸式T(n)=2T(n-1)+O(1)，展開得T(n)=2?T(0)+(2?-1)O(1)=O(2?)。2.算法思路：維護兩個變量first和second，分別表示當前遇到的最小和次小值。遍歷數組，若當前元素>second，則存在三元組；否則更新first或second。步驟：-初始化first=+∞，second=+∞-遍歷arr中每個元素x：-若x≤first→first=x-否則若x≤second→second=x-否則→返回True（存在i<j<k）-遍歷結束后返回False時間復雜度O(n)，空間復雜度O(1)。3.二叉樹結構：后序最后一個是根A，中序中A左邊是左子樹（DBE），右邊是右子樹（FC）。左子樹后序為DEB（根B），中序DBE（B左D，右E）。右子樹后序為FC（根C），中序FC（C左F）。結構：A/\BC/\/DEF前序遍歷序列：ABDECF四、算法設計題1.（1）狀態(tài)定義：dp[i]表示以第i個元素結尾的最長遞增子序列長度。狀態(tài)轉移：dp[i]=max(dp[j]+1)（?j<i且arr[j]<arr[i]），若不存在j則dp[i]=1。（2）偽代碼：functionLIS(arr):n=len(arr)dp=[1]nmax_len=1forifrom1ton-1:forjfrom0toi-1:ifarr[j]<arr[i]:dp[i]=max(dp[i],dp[j]+1)max_len=max(max_len,dp[i])returnmax_len（3）時間復雜度：O(n2)，雙重循環(huán)。2.（1）算法思路：二分圖可通過顏色標記法判斷，用BFS或DFS給節(jié)點染色，相鄰節(jié)點顏色不同。若出現沖突則不是二分圖。（2）實現步驟：-初始化顏色數組color，-1表示未染色，0和1表示兩種顏色。-遍歷每個未染色節(jié)點u：-若u未染色，染色為0，加入隊列。-BFS遍歷u的鄰接節(jié)點v：-若v未染色，染成與u相反的顏色，加入隊列。-若v已染色且顏色與u相同，返回False。-所有節(jié)點處理完返回True。（3）時間復雜度：O(V+E)，每個節(jié)點和邊訪問一次。五、綜合應用題（1）算法選擇：滑動窗口+雙端隊列（單調隊列）。維護一個隊列保存當前窗口內可能的最大值索引，保證隊列單調遞減。（2）詳細步驟：-初始化雙端隊列deque，結果數組res。-遍歷數組nums，索引i從0到n-1：-若隊列頭部索引≤i-k（超出窗口），彈出隊首。-若當前元素nums[i]≥隊列尾部對應元素，彈出隊尾（維護單調遞減）。-將i加入隊尾。-當i≥k-1時，隊首對應元素為當前窗口最大值，加入res。（3）Python實現：```pythondefmaxSlidingWindow(nums,k):fromcollectionsimportdequeq=deque()res=[]fori,numinenumerate(nums):移除超出窗口的隊首元素whileqandq[0]<=i-k:q.popleft()維護單調遞減隊列whileqandnums[q[-1]]<=num: