2026年計(jì)算機(jī)編程競(jìng)賽：算法設(shè)計(jì)與編程實(shí)戰(zhàn)實(shí)務(wù)題一、單選題（共5題，每題2分，總計(jì)10分）題目：1.在快速排序算法中，選擇樞軸元素的不同方法會(huì)影響算法的（）。A.時(shí)間復(fù)雜度B.空間復(fù)雜度C.穩(wěn)定性D.以上都是2.以下哪種數(shù)據(jù)結(jié)構(gòu)最適合用于實(shí)現(xiàn)LRU（最近最少使用）緩存算法？（）A.隊(duì)列B.棧C.哈希表+鏈表D.樹(shù)3.在圖的深度優(yōu)先搜索（DFS）中，如果遇到一個(gè)已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，則說(shuō)明該圖（）。A.是有向圖B.是無(wú)向圖C.含有環(huán)D.沒(méi)有環(huán)4.在二分查找算法中，要求待查找序列必須滿(mǎn)足的條件是（）。A.有序且允許重復(fù)B.有序且無(wú)重復(fù)C.無(wú)序且允許重復(fù)D.無(wú)序且無(wú)重復(fù)5.動(dòng)態(tài)規(guī)劃適用于解決哪些類(lèi)型的問(wèn)題？（）A.貪心問(wèn)題B.分治問(wèn)題C.最優(yōu)化問(wèn)題D.回溯問(wèn)題二、填空題（共5題，每題2分，總計(jì)10分）題目：1.在歸并排序中，每次合并兩個(gè)子數(shù)組的時(shí)間復(fù)雜度為_(kāi)_______。2.在Dijkstra算法中，用于更新最短路徑的優(yōu)先級(jí)隊(duì)列通常采用________數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。3.決策樹(shù)算法中，常用的屬性選擇度量有________和________。4.堆排序的時(shí)間復(fù)雜度是________，空間復(fù)雜度是________。5.在圖的廣度優(yōu)先搜索（BFS）中，通常使用________來(lái)記錄節(jié)點(diǎn)的訪問(wèn)狀態(tài)。三、簡(jiǎn)答題（共5題，每題4分，總計(jì)20分）題目：1.簡(jiǎn)述快速排序和歸并排序的區(qū)別，并說(shuō)明各自的時(shí)間復(fù)雜度。2.解釋貪心算法的基本思想，并舉例說(shuō)明其適用場(chǎng)景。3.描述二叉搜索樹(shù)（BST）的插入操作過(guò)程。4.解釋什么是圖的拓?fù)渑判?，并說(shuō)明其應(yīng)用場(chǎng)景。5.說(shuō)明動(dòng)態(tài)規(guī)劃與分治算法的主要區(qū)別。四、編程題（共3題，每題10分，總計(jì)30分）題目：1.字符串最長(zhǎng)公共子序列給定兩個(gè)字符串`str1`和`str2`，請(qǐng)編寫(xiě)一個(gè)函數(shù)計(jì)算它們的最長(zhǎng)公共子序列的長(zhǎng)度。例如：-`str1="ABCBDAB"`，`str2="BDCABB"`，最長(zhǎng)公共子序列為`BCAB`，長(zhǎng)度為4。2.N皇后問(wèn)題編寫(xiě)一個(gè)函數(shù)解決N皇后問(wèn)題，即在一個(gè)N×N的棋盤(pán)上放置N個(gè)皇后，使它們互不攻擊。要求輸出所有可能的擺法。例如：-N=4時(shí)，有2種擺法。3.最小生成樹(shù)（Prim算法）給定一個(gè)無(wú)向連通圖，請(qǐng)使用Prim算法計(jì)算其最小生成樹(shù)，并輸出邊集。圖的存儲(chǔ)方式為鄰接矩陣。例如：-圖的鄰接矩陣為：0206020385030076800905790最小生成樹(shù)邊集為：`(0,1,2),(1,2,3),(1,4,5)`，總權(quán)值為17。答案與解析一、單選題答案1.D-快速排序的樞軸選擇會(huì)影響分區(qū)均衡性，進(jìn)而影響時(shí)間復(fù)雜度；空間復(fù)雜度與遞歸棧深度相關(guān)；穩(wěn)定性與樞軸選擇無(wú)關(guān)。2.C-哈希表用于O(1)時(shí)間查詢(xún)，鏈表用于維護(hù)順序，結(jié)合兩者實(shí)現(xiàn)LRU緩存。3.C-DFS遇到已訪問(wèn)節(jié)點(diǎn)說(shuō)明存在環(huán)，無(wú)論圖是否為有向圖。4.B-二分查找要求序列有序且無(wú)重復(fù)，否則無(wú)法正確判斷目標(biāo)是否存在。5.C-動(dòng)態(tài)規(guī)劃用于解決最優(yōu)化問(wèn)題，通過(guò)子問(wèn)題分解和重疊子問(wèn)題解決。二、填空題答案1.O(n)-每次合并兩個(gè)子數(shù)組需要遍歷所有元素。2.堆（優(yōu)先隊(duì)列）-Dijkstra算法需要快速找到最小距離節(jié)點(diǎn)，堆結(jié)構(gòu)適合實(shí)現(xiàn)。3.信息增益（ID3）、基尼系數(shù)（C4.5）-常用于決策樹(shù)屬性選擇。4.O(nlogn),O(1)-堆排序時(shí)間復(fù)雜度與建堆和調(diào)整堆有關(guān)，空間復(fù)雜度為原地排序。5.隊(duì)列-BFS使用隊(duì)列按層次遍歷圖節(jié)點(diǎn)。三、簡(jiǎn)答題答案1.快速排序vs歸并排序-快速排序：分治思想，平均O(nlogn)，最壞O(n^2)；原地排序，不穩(wěn)定。-歸并排序：分治思想，穩(wěn)定，時(shí)間復(fù)雜度O(nlogn)；需要額外空間。2.貪心算法思想-每次選擇當(dāng)前最優(yōu)解，不保證全局最優(yōu)，但適用于某些問(wèn)題（如最小生成樹(shù)、霍夫曼編碼）。3.BST插入操作-從根節(jié)點(diǎn)開(kāi)始比較，小于走左子樹(shù)，大于走右子樹(shù)，空位插入新節(jié)點(diǎn)。4.拓?fù)渑判?對(duì)有向無(wú)環(huán)圖（DAG）節(jié)點(diǎn)按依賴(lài)關(guān)系線性排序，用于任務(wù)調(diào)度、依賴(lài)解析。5.動(dòng)態(tài)規(guī)劃vs分治-動(dòng)態(tài)規(guī)劃記錄子問(wèn)題解避免重復(fù)計(jì)算，分治遞歸求解子問(wèn)題后合并。四、編程題答案1.最長(zhǎng)公共子序列pythondeflcs(str1,str2):dp=[[0](len(str2)+1)for_inrange(len(str1)+1)]foriinrange(1,len(str1)+1):forjinrange(1,len(str2)+1):ifstr1[i-1]==str2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])returndp[-1][-1]2.N皇后問(wèn)題pythondefsolve_n_queens(n):defdfs(row,cols,diagonals1,diagonals2):ifrow==n:result.append(cols)returnforcolinrange(n):diag1=row-coldiag2=row+colifcolnotincolsanddiag1notindiagonals1anddiag2notindiagonals2:cols.add(col)diagonals1.add(diag1)diagonals2.add(diag2)dfs(row+1,cols,diagonals1,diagonals2)cols.remove(col)diagonals1.remove(diag1)diagonals2.remove(diag2)result=[]dfs(0,set(),set(),set())returnresult3.Prim算法最小生成樹(shù)pythondefprim(matrix):n=len(matrix)in_mst=[False]nkey=[float('inf')]nkey[0]=0parent=[-1]nfor_inrange(n):u=min(range(n),key=lambdax:key[x]ifnotin_mst[x]elsefloat('inf'))in_mst[u]=Trueforvinrange(n):ifmatrix[u][v]>0andnotin_mst[v]andmatr