2025年初級算法考試試題及答案一、單項選擇題（每題2分，共20分）1.對于長度為n的無序數(shù)組，使用選擇排序進行升序排列時，元素交換操作的次數(shù)最多為（）。A.n-1B.nC.n2/2D.nlogn2.以下哪種算法的時間復雜度與輸入數(shù)據(jù)的初始順序無關？（）A.快速排序B.插入排序C.冒泡排序D.歸并排序3.若二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為BADCE，則后序遍歷序列為（）。A.BDECAB.BEDACC.BDAECD.BEDCA4.對長度為10的有序數(shù)組進行二分查找，最壞情況下需要比較的次數(shù)為（）。A.3B.4C.5D.65.以下關于哈希表的描述中，錯誤的是（）。A.哈希沖突是指不同關鍵字映射到同一哈希地址的現(xiàn)象B.鏈地址法處理沖突時，哈希表的裝載因子可以大于1C.開放定址法處理沖突時，刪除操作需要標記“已刪除”而不是直接清空D.哈希函數(shù)的設計目標是使關鍵字均勻分布，減少沖突6.若用鄰接表存儲一個有向圖，圖中共有n個頂點和m條邊，則該鄰接表的空間復雜度為（）。A.O(n)B.O(m)C.O(n+m)D.O(n×m)7.執(zhí)行以下遞歸函數(shù)f(5)的輸出結(jié)果是（）。deff(n):ifn<=1:return1returnf(n-1)+f(n-2)A.5B.8C.13D.218.對序列[3,1,4,1,5,9,2,6]進行基數(shù)排序（按個位優(yōu)先），第一趟排序后的序列為（）。A.[1,1,2,3,4,5,6,9]B.[3,1,4,1,5,9,2,6]（無變化）C.[1,3,1,4,5,9,2,6]D.[9,5,4,3,6,2,1,1]9.以下動態(tài)規(guī)劃問題中，狀態(tài)轉(zhuǎn)移方程正確的是（）。A.斐波那契數(shù)列：dp[n]=dp[n-1]×dp[n-2]B.最長遞增子序列：dp[i]=max(dp[j]+1)（j<i且nums[j]<nums[i]）C.0-1背包問題：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])（j<w[i]時）D.編輯距離：dp[i][j]=min(dp[i-1][j],dp[i][j-1])（當word1[i]≠word2[j]時）10.若某算法的時間復雜度為O(2?)，則以下哪種n的取值會導致算法無法在合理時間內(nèi)完成？（）A.n=20B.n=30C.n=40D.n=50二、填空題（每題3分，共30分）11.對數(shù)組[7,2,5,8,3,1]進行升序冒泡排序，第三趟（每趟從左到右比較）結(jié)束后，數(shù)組的狀態(tài)為________。12.若完全二叉樹的第6層（根為第1層）有8個葉子節(jié)點，則該樹的總節(jié)點數(shù)最少為________。13.已知一個有序數(shù)組為[2,5,7,10,14,17,20]，使用二分查找法查找元素14時，需要比較的元素依次是________。14.執(zhí)行KMP算法時，模式串“ABABC”的部分匹配值（前綴函數(shù)）數(shù)組為________。15.用棧實現(xiàn)隊列時，若入隊操作均在棧A中完成，出隊操作需要將棧A的元素全部彈出并壓入棧B，則最壞情況下，n次連續(xù)出隊操作的時間復雜度為________。16.對于帶權無向圖，若邊的權值均為正數(shù)，使用Dijkstra算法求單源最短路徑時，優(yōu)先隊列（最小堆）中保存的是________。17.計算字符串“algorithm”和“altruism”的最長公共子序列（LCS）長度為________。18.若用堆結(jié)構(gòu)維護一個動態(tài)集合，支持插入和刪除最大值操作，則該堆應是________（大頂堆/小頂堆）。19.對n個元素進行歸并排序時，遞歸調(diào)用的深度（遞歸層數(shù)）為________（假設n是2的冪）。20.若哈希函數(shù)為H(key)=keymod7，采用線性探測法處理沖突，將序列[15,23,31,9,18]依次插入哈希表后，元素18的存儲地址為________。三、編程題（共50分）21.（10分）編寫一個Python函數(shù)，輸入一個整數(shù)列表nums（可能包含重復元素），輸出所有不重復的三元組[a,b,c]，使得a+b+c=0，且a≤b≤c。22.（15分）給定一個單鏈表的頭節(jié)點head，編寫Python代碼實現(xiàn)鏈表的反轉(zhuǎn)（要求迭代和遞歸兩種方法）。23.（15分）設計一個算法，計算兩個正整數(shù)的最大公約數(shù)（GCD），要求同時支持遞歸（歐幾里得算法）和迭代實現(xiàn)，并分析兩種方法的時間復雜度。24.（10分）輸入一個字符串s（僅包含小寫字母），輸出s中最長的回文子串。要求時間復雜度不超過O(n2)。參考答案一、單項選擇題1.A（選擇排序每趟選最小元素交換，最多n-1次交換）2.D（歸并排序時間復雜度始終為O(nlogn)）3.D（前序確定根A，中序分左右子樹BAD和CE；遞歸推導后序為BEDCA）4.B（二分查找最壞次數(shù)為?log?(n+1)?，n=10時為4）5.C（開放定址法刪除需標記，但直接清空會破壞后續(xù)查找路徑）6.C（鄰接表存儲n個頂點表和m條邊表，總空間O(n+m)）7.B（f(5)=f(4)+f(3)=3+5=8）8.A（基數(shù)排序個位優(yōu)先，按個位排序后序列為1(1),1(1),2(2),3(3),4(4),5(5),6(6),9(9)）9.B（A應為加法，C中j≥w[i]時才取max，D需考慮替換操作）10.C（2??≈1萬億次，遠超合理時間）二、填空題11.[2,3,1,5,7,8]（第一趟后[2,5,3,1,7,8]，第二趟后[2,3,1,5,7,8]，第三趟后[2,3,1,5,7,8]？需重新計算：原始數(shù)組[7,2,5,8,3,1]。第一趟比較5次，交換后[2,5,7,3,1,8]（最后是8）；第二趟比較4次，交換后[2,5,3,1,7,8]；第三趟比較3次，交換后[2,3,1,5,7,8]。答案應為[2,3,1,5,7,8]）12.39（完全二叉樹前5層滿時有2?-1=31個節(jié)點，第6層最少8個葉子，總節(jié)點31+8=39）13.10,17,14（中間元素10，14>10，查右半；中間元素17，14<17，查左半；找到14）14.[0,0,1,2,0]（“A”→0；“AB”→0；“ABA”前綴A和后綴A→1；“ABAB”前綴AB和后綴AB→2；“ABABC”無公共前后綴→0）15.O(n)（均攤分析，每個元素最多入棧和出棧各一次，總時間O(n)）16.待處理節(jié)點的當前最短距離（優(yōu)先隊列按距離排序，每次取最小距離節(jié)點）17.4（公共子序列如“a”,“l(fā)”,“o”,“i”或“a”,“l(fā)”,“r”,“i”）18.大頂堆（堆頂為最大值，刪除時取堆頂）19.log?n（每次分半，遞歸深度為log?n）20.4（H(15)=15%7=1；H(23)=23%7=2；H(31)=31%7=3；H(9)=9%7=2（沖突，探測3→3已占，探測4→存儲4；H(18)=18%7=4（沖突，探測5→存儲5？需重新計算：15→1；23→2；31→3；9→2（沖突，線性探測下一個地址3，3被31占，再下一個4，存儲4；18→18%7=4（地址4被9占，探測5，存儲5）。答案應為5？原計算錯誤，正確步驟：哈希表地址0-6。插入15→1；23→2；31→3；9→9%7=2（沖突），探測地址3（被31占），探測地址4（空），存入4；18→18%7=4（沖突），探測地址5（空），存入5。故答案為5）三、編程題21.參考代碼：```pythondefthree_sum(nums):nums.sort()res=[]n=len(nums)foriinrange(n):ifnums[i]>0:break已排序，正數(shù)之和無法為0ifi>0andnums[i]==nums[i-1]:continue去重left,right=i+1,n-1whileleft<right:s=nums[i]+nums[left]+nums[right]ifs==0:res.append([nums[i],nums[left],nums[right]])跳過重復的left和rightwhileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifs<0:left+=1else:right-=1returnres```22.迭代法與遞歸法：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next迭代法defreverse_list_iter(head):prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev遞歸法defreverse_list_recur(head):ifnotheadornothead.next:returnheadnew_head=reverse_list_recur(head.next)head.next.next=headhead.next=Nonereturnnew_head```23.最大公約數(shù)實現(xiàn)：```python遞歸（歐幾里得算法）defgcd_recur(a,b):ifb==0:returnareturngcd_recur(b,a%b)迭代法defgcd_iter(a,b):whileb!=0:a,b=b,a%breturna時間復雜度分析：兩種方法均基于模運算，時間復雜度為O(logmin(a,b))，與歐幾里得算法的步驟數(shù)相關。```24.最長回文子串（中心擴展法）：```pythondeflongest_palindrome(s):ifnots:return""n=len(s)start,end=0,0defexpand(l,r):whilel>=0andr<nands[l]==s[r]:l-=1r+=1returnrl-1實際長度為(r-1)-(l+1)+1=r-l-1