計(jì)算機(jī)2025年計(jì)算機(jī)算法設(shè)計(jì)專項(xiàng)考考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共10分。請(qǐng)將答案填在答題紙上對(duì)應(yīng)位置）1.對(duì)于算法A和B，若A的時(shí)間復(fù)雜度為O(n^2)，B的時(shí)間復(fù)雜度為O(nlogn)，在什么情況下算法B總是優(yōu)于算法A？A.當(dāng)n足夠大時(shí)B.當(dāng)n較小時(shí)C.當(dāng)n趨向于無(wú)窮大時(shí)，B的執(zhí)行時(shí)間總小于AD.算法B的性能僅取決于n的具體值2.在以下數(shù)據(jù)結(jié)構(gòu)中，哪一種最適合表示一個(gè)無(wú)向連通圖，并且支持高效的添加和刪除邊操作？A.鄰接矩陣B.鄰接表C.順序棧D.順序隊(duì)列3.快速排序算法在什么情況下性能最差，接近于冒泡排序？A.列表已經(jīng)基本有序時(shí)B.列表完全無(wú)序時(shí)C.列表長(zhǎng)度非常短時(shí)D.列表長(zhǎng)度等于某個(gè)特定素?cái)?shù)時(shí)4.使用深度優(yōu)先搜索（DFS）遍歷一棵樹(shù)，并且采用非遞歸實(shí)現(xiàn)，通常需要使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)輔助？A.隊(duì)列B.棧C.鏈表D.堆5.動(dòng)態(tài)規(guī)劃算法的核心思想是？A.分治策略B.貪心選擇C.遞歸調(diào)用D.優(yōu)化子問(wèn)題的解以構(gòu)造原問(wèn)題的最優(yōu)解二、判斷題（每小題1分，共5分。請(qǐng)將答案填在答題紙上對(duì)應(yīng)位置，正確填“√”，錯(cuò)誤填“×”）1.如果算法A的時(shí)間復(fù)雜度為O(n^2)，算法B的時(shí)間復(fù)雜度為O(n^3)，那么算法A的執(zhí)行時(shí)間一定小于算法B的執(zhí)行時(shí)間。（）2.在具有n個(gè)頂點(diǎn)的無(wú)向圖中，鄰接矩陣一定是一個(gè)n×n的對(duì)稱矩陣。（）3.二分查找算法適用于任何線性結(jié)構(gòu)的數(shù)據(jù)，只要該數(shù)據(jù)是有序的。（）4.對(duì)于任何問(wèn)題，使用動(dòng)態(tài)規(guī)劃都比使用貪心算法更好。（）5.圖的廣度優(yōu)先搜索（BFS）是沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn)，如果所有節(jié)點(diǎn)都被訪問(wèn)，則說(shuō)明該圖是連通的。（）三、算法設(shè)計(jì)題（共4小題，共35分）1.（8分）設(shè)計(jì)一個(gè)算法，找出一個(gè)無(wú)向圖中所有長(zhǎng)度為2的簡(jiǎn)單路徑（即不重復(fù)經(jīng)過(guò)任何邊的路徑）。輸入為一個(gè)圖的鄰接表表示，輸出為所有滿足條件的路徑列表。描述算法的主要思路，并用偽代碼表示核心部分。2.（9分）給定一個(gè)由小寫(xiě)字母組成的字符串S和一個(gè)非空模式串P。設(shè)計(jì)一個(gè)算法，找出模式串P在字符串S中所有出現(xiàn)的位置（從0開(kāi)始計(jì)數(shù)）。要求描述KMP（Knuth-Morris-Pratt）算法的核心思想，特別是計(jì)算部分匹配表（也稱為“失敗函數(shù)”或“前綴函數(shù)”）的步驟，并給出該步驟的偽代碼。3.（9分）有一個(gè)爬樓梯問(wèn)題：假設(shè)樓梯有n階，每次可以爬1階或者2階，請(qǐng)問(wèn)共有多少種不同的爬法？設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法解決這個(gè)問(wèn)題。請(qǐng)明確狀態(tài)定義、狀態(tài)轉(zhuǎn)移方程，并用偽代碼表示算法的核心部分。4.（9分）設(shè)計(jì)一個(gè)算法，找出一個(gè)無(wú)向連通圖中所有割點(diǎn)（ArticulationPoints）。輸入為一個(gè)圖的鄰接表表示，輸出為所有割點(diǎn)的列表。描述算法的主要思路（可以基于深度優(yōu)先搜索），并用偽代碼表示核心部分。四、代碼實(shí)現(xiàn)與分析題（共2小題，共30分）1.（15分）實(shí)現(xiàn)快速排序算法。請(qǐng)使用C++或Java語(yǔ)言編寫(xiě)代碼，完成快速排序的核心遞歸函數(shù)。要求在代碼中包含對(duì)基準(zhǔn)元素（pivot）的選擇策略（例如，選擇中位數(shù)作為基準(zhǔn)），并在注釋中簡(jiǎn)要說(shuō)明選擇該策略的原因。此外，請(qǐng)對(duì)該快速排序算法（基于您選擇的基準(zhǔn)選擇策略）在最壞情況下的時(shí)間復(fù)雜度進(jìn)行分析。2.（15分）實(shí)現(xiàn)Dijkstra算法，用于在一個(gè)帶有非負(fù)權(quán)值的連通無(wú)向圖中，找出從給定源頂點(diǎn)s到所有其他頂點(diǎn)的最短路徑。請(qǐng)使用C++或Java語(yǔ)言編寫(xiě)代碼，完成Dijkstra算法的核心部分?？梢允褂绵徑泳仃嚮蜞徑颖肀硎据斎氲膱D。要求在代碼中明確說(shuō)明您使用的優(yōu)先級(jí)隊(duì)列（如最小堆）的實(shí)現(xiàn)方式（例如，使用數(shù)組實(shí)現(xiàn)、使用標(biāo)準(zhǔn)庫(kù)中的優(yōu)先級(jí)隊(duì)列等），并簡(jiǎn)要分析您選擇該實(shí)現(xiàn)方式的原因。試卷答案一、選擇題1.A2.B3.A4.B5.D二、判斷題1.×2.√3.×4.×5.√三、算法設(shè)計(jì)題1.算法思路：遍歷圖的每個(gè)頂點(diǎn)u。對(duì)于頂點(diǎn)u，找到其所有鄰接頂點(diǎn)v。對(duì)于每個(gè)鄰接頂點(diǎn)v，找到v的所有鄰接頂點(diǎn)w。如果頂點(diǎn)w與頂點(diǎn)u不同，且頂點(diǎn)w尚未出現(xiàn)在從u出發(fā)的當(dāng)前路徑中，則構(gòu)成一條長(zhǎng)度為2的路徑<u,v,w>。將此路徑加入結(jié)果列表。注意去重，避免路徑方向不同但內(nèi)容相同的路徑被重復(fù)記錄。偽代碼核心部分：```FunctionFindPaths(graph):paths=[]foreachvertexuingraph:neighbors_u=graph.getNeighbors(u)foreachvertexvinneighbors_u:ifv!=u:neighbors_v=graph.getNeighbors(v)foreachvertexwinneighbors_v:ifw!=vandw!=u:path=[u,v,w]paths.add(path)returnpaths```2.核心思想：KMP算法利用已經(jīng)匹配成功的部分信息，避免將指針回溯。通過(guò)構(gòu)建部分匹配表（PartialMatchTable,PMT），該表記錄了模式串的前綴和后綴相等的最長(zhǎng)長(zhǎng)度。在匹配過(guò)程中，當(dāng)不匹配發(fā)生時(shí)，根據(jù)PMT將模式串的指針移動(dòng)到合適的位置，而不是將整個(gè)模式串向后移動(dòng)。計(jì)算PMT步驟偽代碼核心部分：```FunctionComputePMT(P):m=length(P)pmt=[0]*mlen=0//最長(zhǎng)相等前后綴的長(zhǎng)度i=1whilei<m:ifP[i]==P[len]:len+=1pmt[i]=leni+=1else:iflen!=0:len=pmt[len-1]//注意：此處部分教材寫(xiě)作len=pmt[len]//但更常見(jiàn)的寫(xiě)法是保留上面的len+=1和else分支//此處采用更標(biāo)準(zhǔn)的保留len+=1的寫(xiě)法，即len=pmt[len-1]iflen>0else0//但為清晰，此處按經(jīng)典PMT構(gòu)建邏輯：whilelen>0andP[i]!=P[len]:len=pmt[len-1]else:pmt[i]=0i+=1returnpmt```3.狀態(tài)定義：`dp[i]`表示到達(dá)第i階樓梯的總爬法數(shù)。狀態(tài)轉(zhuǎn)移方程：`dp[i]=dp[i-1]+dp[i-2]`（從i-1階跨1階上來(lái)，或從i-2階跨2階上來(lái)）。初始條件：`dp[0]=1`(在地面，一種狀態(tài))，`dp[1]=1`(爬1階，一種狀態(tài))。偽代碼核心部分：```FunctionClimbingStairs(n):ifn==0:return1ifn==1:return1dp=[0]*(n+1)dp[0]=1dp[1]=1forifrom2ton:dp[i]=dp[i-1]+dp[i-2]returndp[n]```4.主要思路（基于DFS）：使用深度優(yōu)先搜索遍歷圖。在DFS過(guò)程中，維護(hù)兩個(gè)數(shù)組：`disc[u]`表示頂點(diǎn)u的發(fā)現(xiàn)時(shí)間（DFS訪問(wèn)u的順序號(hào)），`low[u]`表示從頂點(diǎn)u能到達(dá)的最小發(fā)現(xiàn)時(shí)間（包括u自身及其后代）。對(duì)于樹(shù)邊(u,v)，`low[v]`總是比`disc[u]`小1。對(duì)于回邊(u,v)（v是u的祖先），`low[v]`可能大于等于`disc[u]`。如果存在一個(gè)非根頂點(diǎn)u，滿足以下任一條件：*u是根，且u至少有兩個(gè)子女。*u不是根，且u的一個(gè)子女v滿足`low[v]>=disc[u]`。則u是一個(gè)割點(diǎn)。算法結(jié)束時(shí)，所有滿足上述條件的頂點(diǎn)u即為所有割點(diǎn)。偽代碼核心部分：```FunctionFindArticulationPoints(graph):disc=[]low=[]parent=[]ap=[]//存儲(chǔ)割點(diǎn)time=0foreachvertexuingraph:disc[u]=-1low[u]=-1parent[u]=-1foreachvertexuingraph:ifdisc[u]==-1:APUtil(u)returnapFunctionAPUtil(u):globaltime,disc,low,parent,ap,graphdisc[u]=low[u]=++timechildren=0foreachvertexvingraph.getNeighbors(u):ifdisc[v]==-1:parent[v]=uchildren+=1APUtil(v)low[u]=min(low[u],low[v])//檢查割點(diǎn)條件ifparent[u]==-1andchildren>1:ap.add(u)ifparent[u]!=-1andlow[v]>=disc[u]:ap.add(u)elseifv!=parent[u]:low[u]=min(low[u],disc[v])```四、代碼實(shí)現(xiàn)與分析題1.C++/Java代碼實(shí)現(xiàn)（以C++為例，使用中位數(shù)三數(shù)取中法選擇基準(zhǔn)）：```c++//快速排序核心遞歸函數(shù)-C++示例//選擇基準(zhǔn)：中位數(shù)法（取左、中、右三個(gè)元素的中位數(shù)）#include<vector>#include<algorithm>//std::swapvoidquickSortHelper(std::vector<int>&arr,intleft,intright){if(left>=right)return;//選擇基準(zhǔn)：中位數(shù)三數(shù)取中法intmid=left+(right-left)/2;intpivot=arr[mid];//將中位數(shù)放到最右端（或左端），便于后續(xù)操作std::swap(arr[mid],arr[right]);intstoreIndex=left;//將小于基準(zhǔn)的元素移到基準(zhǔn)的左側(cè)for(inti=left;i<right;++i){if(arr[i]<pivot){std::swap(arr[i],arr[storeIndex]);storeIndex++;}}//將基準(zhǔn)放到正確的位置std::swap(arr[storeIndex],arr[right]);//遞歸對(duì)基準(zhǔn)左右兩側(cè)的子數(shù)組進(jìn)行排序quickSortHelper(arr,left,storeIndex-1);quickSortHelper(arr,storeIndex+1,right);}//對(duì)外提供的快速排序接口voidquickSort(std::vector<int>&arr){if(arr.empty())return;quickSortHelper(arr,0,arr.size()-1);}```最壞情況時(shí)間復(fù)雜度分析：最壞情況發(fā)生在每次劃分都能只得到一個(gè)元素比另一個(gè)元素多一個(gè)的子數(shù)組，例如，當(dāng)輸入數(shù)組已經(jīng)是正序或逆序時(shí)，如果每次都選擇最左端或最右端的元素作為基準(zhǔn)。這樣，每次遞歸調(diào)用會(huì)將問(wèn)題規(guī)模從n減小到n-1，遞歸深度為n，且每一層都有n次比較（理論上，但實(shí)際交換次數(shù)更多）。這種劃分方式的時(shí)間復(fù)雜度為O(n^2)。2.C++/Java代碼實(shí)現(xiàn)（以C++為例，使用優(yōu)先隊(duì)列實(shí)現(xiàn)最小堆）：```c++//Dijkstra算法核心部分-C++示例//使用優(yōu)先隊(duì)列（最小堆）實(shí)現(xiàn)#include<vector>#include<queue>#include<climits>//INT_MAX#include<utility>//std::pair//假設(shè)圖用鄰接表表示，邊的權(quán)重為非負(fù)整數(shù)//graph[u]存儲(chǔ)頂點(diǎn)u的所有鄰接邊，每條邊表示為{v,weight}//例如：graph[0]={{1,10},{2,3}}voiddijkstra(conststd::vector<std::vector<std::pair<int,int>>>&graph,ints,std::vector<int>&dist){intn=graph.size();dist.assign(n,INT_MAX);//初始化距離為無(wú)窮大dist[s]=0;//源點(diǎn)距離自身為0//使用優(yōu)先隊(duì)列（最小堆），存儲(chǔ){當(dāng)前距離,頂點(diǎn)編號(hào)}//pair的第一元素是距離，第二元素是頂點(diǎn)//std::priority_queue默認(rèn)是大根堆，需要比較器使其成為小根堆std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<>>pq;pq.push({0,s});while(!pq.empty()){auto[current_dist,u]=pq.top();//獲取距離最小的