2025年程序設(shè)計與編程能力考核相關(guān)知識考試試卷及答案一、單項選擇題（共10題，每題2分，共20分）1.以下關(guān)于時間復雜度的描述中，正確的是（）A.對于長度為n的數(shù)組，冒泡排序的最壞時間復雜度為O(n)B.快速排序的平均時間復雜度為O(nlogn)，因此其所有情況下的時間復雜度均不超過O(nlogn)C.二分查找在有序數(shù)組中的時間復雜度為O(logn)，其空間復雜度為O(1)D.歸并排序的空間復雜度為O(1)答案：C解析：冒泡排序最壞情況（逆序）時間復雜度為O(n2)，A錯誤；快速排序在最壞情況下（如已排序數(shù)組選第一個元素為樞軸）時間復雜度退化為O(n2)，B錯誤；歸并排序需要額外O(n)的輔助空間，D錯誤；二分查找僅需常數(shù)級額外空間，C正確。2.設(shè)有一個棧S，初始為空。依次執(zhí)行操作push(1)、push(2)、pop()、push(3)、push(4)、pop()、pop()，最終棧中剩余的元素是（）A.[1,3]B.[1]C.[3]D.[1,2]答案：B解析：操作過程：push(1)→[1]；push(2)→[1,2]；pop()→[1]；push(3)→[1,3]；push(4)→[1,3,4]；pop()→[1,3]；pop()→[1]。3.以下關(guān)于二叉樹的說法中，錯誤的是（）A.完全二叉樹的葉子節(jié)點只能出現(xiàn)在最后兩層B.滿二叉樹一定是完全二叉樹C.二叉搜索樹中，左子樹所有節(jié)點的值均小于根節(jié)點，右子樹所有節(jié)點的值均大于根節(jié)點D.平衡二叉樹（AVL樹）的左右子樹高度差的絕對值不超過1答案：C解析：二叉搜索樹的定義是左子樹所有節(jié)點值≤根節(jié)點（或<，取決于具體實現(xiàn)），右子樹所有節(jié)點值≥根節(jié)點（或>），但嚴格小于/大于的描述不準確（可能存在重復值），C錯誤。4.用動態(tài)規(guī)劃解決最長公共子序列（LCS）問題時，狀態(tài)轉(zhuǎn)移方程中，若兩個序列的第i和第j個元素相等，則dp[i][j]=（）A.dp[i-1][j-1]+1B.max(dp[i-1][j],dp[i][j-1])C.dp[i-1][j]+dp[i][j-1]D.dp[i-1][j-1]答案：A解析：LCS中，當s1[i]=s2[j]時，當前字符屬于公共子序列，因此狀態(tài)由前i-1和j-1的狀態(tài)轉(zhuǎn)移而來，長度加1。5.以下代碼段的輸出結(jié)果是（）```pythondeffunc(a):a=a+2returnax=5func(x)print(x)```A.5B.7C.0D.報錯答案：A解析：Python中整數(shù)是不可變類型，函數(shù)參數(shù)傳遞為值傳遞，func內(nèi)部修改a不影響外部x的值。6.對長度為n的有序數(shù)組進行順序查找（從左到右逐個比較），在等概率情況下，平均查找長度為（）A.(n+1)/2B.n/2C.lognD.n答案：A解析：順序查找成功時，第i個元素需要i次比較，平均為(1+2+…+n)/n=(n+1)/2。7.以下關(guān)于哈希表的說法中，正確的是（）A.哈希沖突是指不同關(guān)鍵字映射到同一哈希地址的現(xiàn)象B.開放定址法解決沖突時，插入新元素不會影響已有元素的存儲位置C.鏈地址法的空間利用率一定高于開放定址法D.哈希函數(shù)的設(shè)計與數(shù)據(jù)無關(guān)，只需保證計算高效答案：A解析：B錯誤，開放定址法（如線性探測）插入時可能需要移動已有元素；C錯誤，鏈地址法需要額外指針空間，空間利用率可能更低；D錯誤，哈希函數(shù)需根據(jù)數(shù)據(jù)分布設(shè)計（如整數(shù)用取模，字符串用多項式滾動哈希）。8.以下排序算法中，不穩(wěn)定的是（）A.冒泡排序B.歸并排序C.快速排序D.插入排序答案：C解析：快速排序在分區(qū)過程中可能交換相同元素的相對順序（如[3,2,3]以第一個3為樞軸，排序后第二個3可能出現(xiàn)在第一個3左側(cè)），導致不穩(wěn)定。9.給定圖的鄰接表表示，若要計算每個頂點的入度，需要（）A.遍歷所有頂點的出邊B.遍歷所有頂點的入邊C.僅遍歷目標頂點的鄰接表D.無法通過鄰接表直接計算入度答案：A解析：鄰接表通常存儲出邊，計算入度需遍歷所有頂點的出邊，統(tǒng)計每個頂點被指向的次數(shù)。10.以下關(guān)于遞歸和迭代的說法中，錯誤的是（）A.遞歸算法的空間復雜度可能更高（因函數(shù)調(diào)用棧）B.所有遞歸算法都可以轉(zhuǎn)換為迭代算法C.尾遞歸優(yōu)化可以將遞歸的空間復雜度降為O(1)D.迭代算法的時間復雜度一定低于遞歸算法答案：D解析：時間復雜度取決于具體實現(xiàn)，迭代和遞歸可能復雜度相同（如斐波那契數(shù)列遞歸未優(yōu)化時為O(2?)，迭代為O(n)），但并非絕對。二、填空題（共5題，每題4分，共20分）1.對于一個包含n個元素的堆（小根堆），其根節(jié)點的值為最小值，任意非根節(jié)點i（i≥1）的父節(jié)點索引為______（假設(shè)索引從0開始）。答案：(i-1)//22.給定字符串s="abacab"，其前綴函數(shù)（KMP算法中的部分匹配表）π數(shù)組的值為______（按順序?qū)懗龈魑恢弥担?。答案：[0,0,1,0,1,2]解析：π[i]表示子串s[0..i]的最長相等真前綴和后綴的長度。s[0]無真前綴→0；s[1]="ab"最長前后綴無→0；s[2]="aba"最長前后綴"a"→1；s[3]="abac"無→0；s[4]="abaca"最長前后綴"a"→1；s[5]="abacab"最長前后綴"ab"→2。3.用Prim算法構(gòu)造帶權(quán)連通圖的最小生成樹時，初始時選擇任意頂點加入樹，后續(xù)每一步選擇連接樹內(nèi)外頂點的______邊，直到所有頂點加入樹。答案：權(quán)值最小的4.給定數(shù)組nums=[3,1,4,1,5,9,2,6]，使用基數(shù)排序（按十進制個位、十位依次排序），第一輪（個位排序）后的數(shù)組順序為______。答案：[1,1,2,3,4,5,6,9]解析：個位分別為3→3，1→1，4→4，1→1，5→5，9→9，2→2，6→6。按個位升序排列后順序為1（索引1）、1（索引3）、2（索引6）、3（索引0）、4（索引2）、5（索引4）、6（索引7）、9（索引5）。5.設(shè)某二叉樹的前序遍歷序列為ABDECFG，中序遍歷序列為DBEAFGC，則該二叉樹的后序遍歷序列為______。答案：DEBFGCA解析：前序根為A，中序中A左側(cè)DBE為左子樹，右側(cè)FGC為右子樹。左子樹前序BDE→根B，中序DBE→D左、E右；右子樹前序CFG→根C，中序FGC→F左、G右。后序遍歷順序：D→E→B→F→G→C→A。三、算法設(shè)計題（共3題，每題15分，共45分）1.編寫一個函數(shù)，輸入一個整數(shù)數(shù)組nums和一個整數(shù)k，找出數(shù)組中和為k的最長連續(xù)子數(shù)組的長度。若不存在這樣的子數(shù)組，返回0。要求時間復雜度為O(n)。示例：輸入：nums=[1,-1,5,-2,3],k=3輸出：4（子數(shù)組[1,-1,5,-2]的和為3，長度4）答案：```pythondeflongest_subarray(nums,k):prefix_sum=0sum_map={0:-1}記錄前綴和及最早出現(xiàn)的索引max_len=0foriinrange(len(nums)):prefix_sum+=nums[i]檢查是否存在prefix_sum-k的前綴和if(prefix_sum-k)insum_map:current_len=i-sum_map[prefix_sum-k]ifcurrent_len>max_len:max_len=current_len僅記錄該前綴和第一次出現(xiàn)的索引（保證最長）ifprefix_sumnotinsum_map:sum_map[prefix_sum]=ireturnmax_len```解析：利用前綴和+哈希表。sum_map存儲前綴和到最早出現(xiàn)的索引的映射。當前綴和為s時，若存在s-k的前綴和，則中間子數(shù)組和為k。記錄最早出現(xiàn)的索引可保證子數(shù)組最長。時間復雜度O(n)，空間復雜度O(n)。2.給定一個二叉樹的根節(jié)點root，判斷其是否為平衡二叉樹。平衡二叉樹的定義是：任意節(jié)點的左右子樹的高度差的絕對值不超過1，且左右子樹均為平衡二叉樹。答案：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root):defheight(node):ifnotnode:return0left_h=height(node.left)ifleft_h==-1:左子樹不平衡，直接返回return-1right_h=height(node.right)ifright_h==-1:右子樹不平衡，直接返回return-1ifabs(left_h-right_h)>1:當前節(jié)點不平衡return-1returnmax(left_h,right_h)+1返回當前子樹高度returnheight(root)!=-1```解析：后序遍歷計算子樹高度，若某子樹高度差超過1則標記為不平衡（返回-1）。若最終根節(jié)點的高度不為-1，則樹平衡。時間復雜度O(n)，空間復雜度O(h)（h為樹高，最壞O(n)）。3.設(shè)計一個算法，將字符串s中的每個單詞反轉(zhuǎn)，但保留單詞的順序和標點符號的位置。單詞由字母組成，標點符號包括逗號、句號、感嘆號、問號（,.!?），且標點符號不會出現(xiàn)在單詞內(nèi)部。示例：輸入：s="Hello,world!I'maprogrammer."輸出：",elloH!dlrowm'Ia.remmargorp"答案：```pythondefreverse_words_with_punctuation(s):punctuation={',','.','!','?'}words=[]current_word=[]分割單詞和標點forcins:ifcinpunctuation:ifcurrent_word:words.append(('word',''.join(current_word)))current_word=[]words.append(('punct',c))else:current_word.append(c)ifcurrent_word:處理末尾單詞words.append(('word',''.join(current_word)))反轉(zhuǎn)單詞并重組result=[]fortyp,valinwords:iftyp=='word':result.append(val[::-1])else:result.append(val)return''.join(result)```解析：首先遍歷字符串，將字符分為單詞和標點兩類存儲。單詞部分反轉(zhuǎn)后，按原順序重組。時間復雜度O(n)，空間復雜度O(n)。四、程序改錯題（共1題，10分）以下代碼試圖實現(xiàn)計算斐波那契數(shù)列的第n項（n≥1），但存在錯誤。請找出所有錯誤并修正。錯誤代碼：```pythondeffibonacci(n):ifn==1orn==2:return1a,b=1,1foriinrange(3,n):c=a+ba=bb=creturnb```答案：錯誤1：循環(huán)范圍錯誤。當n=3時，range(3,3)為空，循環(huán)不執(zhí)行，返回b=1（正確應(yīng)為2）。錯誤2：斐波那契數(shù)列第n項的索引邏輯錯誤。原代碼中循環(huán)從3到n-1（因range(3,n)不包含n），導致計算次數(shù)不足。修正后代碼：```pythondeffibonacci(n):ifn==1orn==2:return1a,b=1,1foriinrange(3,n+1):循環(huán)到n，包含nc=a+ba=bb=creturnb```解析：斐波那契數(shù)列第3項為2，原代碼中當n=3時，循環(huán)range(3,3)不執(zhí)行，返回b=1（錯誤）。修正后循環(huán)范圍為range(3,n+1)，確保計算n-2次（n≥3時需要n-2次迭代）。例如，n=3時循環(huán)執(zhí)行1次（i=3），計算c=2，返回b=2（正確）。五、綜合應(yīng)用題（共1題，15分）設(shè)計一個LRU（最近最少使用）緩存，支持以下操作：-get(key)：獲取key對應(yīng)的值，若不存在返回-1，且訪問后該key變?yōu)樽罱褂谩?put(key,value)：插入或更新key的值。若緩存容量已滿，刪除最久未使用的key，再插入新key。要求使用雙向鏈表和哈希表實現(xiàn)，時間復雜度O(1)。答案：```pythonclassListNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.size=0self.cache={}哈希表：key→ListNode雙向鏈表頭尾哨兵節(jié)點self.head=ListNode()self.tail=ListNode()self.head.next=self.tailself.tail.prev=self.headdefmove_to_head(self,node):從當前位置移除node.prev.next=node.nextnode.next.prev=node.prev插入頭部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedefadd_to_head(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedefremove_tail(self):node=self.tail.prevdelself.cache[node.key]node.prev.next=self.tailself.tail.prev=node.prevreturnnodedefget(self,key:int)->int:ifkeynotinself.cache: