2026年程序員算法專項(xiàng)考核試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.給定一個(gè)長度為n的整數(shù)數(shù)組，要求找出其中出現(xiàn)次數(shù)超過n/2的元素（假設(shè)一定存在）。以下算法中，時(shí)間復(fù)雜度最優(yōu)且空間復(fù)雜度為O(1)的是A.哈希表統(tǒng)計(jì)頻率B.排序后取中位數(shù)C.Boyer-Moore投票算法D.分治法求眾數(shù)答案：C解析：Boyer-Moore投票算法只需一次遍歷，維護(hù)候選元素與計(jì)數(shù)器，空間固定為兩個(gè)變量，滿足O(1)額外空間。2.對(duì)一棵包含n個(gè)節(jié)點(diǎn)的二叉搜索樹進(jìn)行中序遍歷，得到的序列性質(zhì)為A.嚴(yán)格遞減B.非嚴(yán)格遞增C.先序逆序D.層次序答案：B解析：BST中序遍歷產(chǎn)生非嚴(yán)格遞增序列，允許重復(fù)值時(shí)相等節(jié)點(diǎn)相鄰。3.在32位無符號(hào)整數(shù)范圍內(nèi)，計(jì)算x的y次方對(duì)232取模，y可為0~232?1。下列做法不會(huì)溢出且效率最高的是A.快速冪+模乘B.自然溢出后截?cái)郈.任意精度大整數(shù)D.查表預(yù)計(jì)算答案：A解析：快速冪將指數(shù)二分，模乘保證中間結(jié)果不超32位，時(shí)間O(logy)。4.對(duì)一張稠密無向圖求所有點(diǎn)對(duì)最短路徑，頂點(diǎn)數(shù)V=500，邊權(quán)非負(fù)。最優(yōu)選擇A.Dijkstra×V輪B.Bellman-Ford×V輪C.Floyd-WarshallD.0-1BFS答案：C解析：V=500時(shí)V3=1.25×10?，現(xiàn)代CPU可在1s內(nèi)完成；Dijkstra×V用斐波那堆為O(V2logV)≈1.5×10?×log500≈2.7×10?，但實(shí)際常數(shù)大且實(shí)現(xiàn)復(fù)雜，F(xiàn)loyd更直接。5.以下關(guān)于并查集按秩合并與路徑壓縮的說法正確的是A.二者同時(shí)使用導(dǎo)致最壞復(fù)雜度退化到O(n)B.二者同時(shí)使用單次操作攤還O(α(n))C.路徑壓縮后不可再按秩合并D.按秩合并需額外保存節(jié)點(diǎn)深度答案：B解析：Tarjan證明二者結(jié)合后單次操作反阿克曼函數(shù)α(n)，近乎常數(shù)。6.對(duì)長度為n的隨機(jī)數(shù)組做快速排序，樞軸總是選首元素，若數(shù)組已升序，則時(shí)間復(fù)雜度為A.Θ(nlogn)B.Θ(n2)C.Θ(n)D.Θ(logn)答案：B解析：最壞情況劃分極度不平衡，退化為鏈?zhǔn)竭f歸，次數(shù)1+2+…+n。7.給定兩個(gè)長度均為n的已排序數(shù)組，求它們合并后的中位數(shù)，要求O(logn)時(shí)間。應(yīng)使用A.二分查找+分治B.雙指針歸并C.快速選擇D.堆答案：A解析：在兩條數(shù)組上同時(shí)對(duì)第k小元素二分，每次排除k/2規(guī)模，復(fù)雜度O(logn)。8.若哈希表采用開放尋址+線性探測，裝載因子α=0.9，則一次不成功查找的期望探查次數(shù)約為A.0.9B.5.5C.10D.50答案：B解析：公式(1+1/(1?α)2)/2≈(1+100)/2=50.5，但線性探測集群嚴(yán)重，實(shí)際經(jīng)驗(yàn)值約5.5次。9.對(duì)一張有向無環(huán)圖，拓?fù)渑判蚴褂肒ahn算法（入度表+BFS）時(shí)，若隊(duì)列改用棧，則輸出序列A.仍為合法拓?fù)湫駼.必然逆字典序C.可能含環(huán)D.唯一確定答案：A解析：棧只是改變同一層節(jié)點(diǎn)選擇順序，最終仍是合法拓?fù)湫颍灰氕h(huán)。10.在Manacher算法中，輔助數(shù)組P[i]表示A.以i為中心的最長回文半徑（含中心）B.以i為起點(diǎn)的最長回文長度C.以i為終點(diǎn)的最長回文長度D.以i為中心的最長回文半徑（不含中心）答案：A解析：P[i]記錄回文半徑，含中心字符，故總長度2P[i]?1。二、不定項(xiàng)選擇題（每題3分，共15分，多選少選均不得分）11.關(guān)于跳表(SkipList)的正確描述有A.期望高度O(logn)B.支持插入、刪除、查找平均O(logn)C.可替代平衡樹實(shí)現(xiàn)有序映射D.最壞查詢復(fù)雜度O(n)答案：ABCD解析：跳表隨機(jī)層級(jí)，期望O(logn)，最壞退化為鏈；功能與平衡樹等價(jià)。12.以下算法中，利用“分治+遞歸”思想的有A.歸并排序B.快速傅里葉變換C.Karatsuba乘法D.堆排序答案：ABC解析：堆排序?qū)龠x擇排序的堆化優(yōu)化，無分治遞歸拆分。13.對(duì)帶負(fù)權(quán)邊但無負(fù)環(huán)的圖，可正確求單源最短路徑的算法有A.Bellman-FordB.SPFAC.DijkstraD.拓?fù)渑判?松弛答案：AB解析：Dijkstra無法處理負(fù)權(quán)；拓?fù)渑判蛑贿m用于DAG。14.關(guān)于字符串匹配KMP算法，正確的有A.預(yù)處理next數(shù)組時(shí)間O(m)B.匹配階段時(shí)間O(n)C.next數(shù)組僅與模式串有關(guān)D.可擴(kuò)展到多模式匹配形成AC自動(dòng)機(jī)答案：ABCD解析：KMP核心為next數(shù)組，AC自動(dòng)機(jī)在其基礎(chǔ)上加fail指針。15.以下數(shù)據(jù)結(jié)構(gòu)支持O(logn)時(shí)間合并兩個(gè)集合的有A.Treap（隨機(jī)堆+BST）B.SplayTreeC.左偏堆（LeftistHeap）D.并查集答案：AC解析：Splay無保證合并log；并查集只支持近似常數(shù)合并，非log。三、填空題（每空3分，共15分）16.對(duì)n個(gè)元素的二叉堆執(zhí)行k次刪除堆頂操作，總時(shí)間復(fù)雜度為______。答案：O(klogn)解析：每次刪除下沉高度?logn?，k次即klogn。17.采用莫隊(duì)算法處理離線區(qū)間詢問，若塊長取______，則時(shí)間復(fù)雜度最優(yōu)為O((n+q)√n)。答案：√n解析：塊長√n時(shí)，左右指針移動(dòng)總距離最小。18.對(duì)一張n點(diǎn)m邊的帶權(quán)無向圖，使用Kruskal求最小生成樹，并查集路徑壓縮后總時(shí)間復(fù)雜度為______。答案：O(mα(n))解析：排序邊O(mlogm)，并查集m次操作O(mα(n))，m≥n?1。19.在字典樹(Trie)中，若字符集大小為26，插入長度為L的字符串，最壞節(jié)點(diǎn)新建數(shù)為______。答案：L解析：每層若無公共前綴則需新建，最多L節(jié)點(diǎn)。20.對(duì)0~n?1的排列，使用ST表（SparseTable）做區(qū)間最值查詢，預(yù)處理的時(shí)空復(fù)雜度分別為______和______。答案：O(nlogn)，O(nlogn)解析：ST表基于倍增，每層n個(gè)元素，共logn層。四、算法設(shè)計(jì)題（共30分）21.（10分）給定一棵n個(gè)節(jié)點(diǎn)的無根樹，邊權(quán)為1。定義f(u)為節(jié)點(diǎn)u到其最遠(yuǎn)節(jié)點(diǎn)的距離（樹的高度）。要求對(duì)每個(gè)u求f(u)，n≤2×10?。答案：兩次BFS/DFS。步驟：1)從任意節(jié)點(diǎn)s出發(fā)找最遠(yuǎn)點(diǎn)a；2)從a出發(fā)找最遠(yuǎn)點(diǎn)b，記錄a到各點(diǎn)距離da；3)從b出發(fā)找最遠(yuǎn)點(diǎn)，記錄距離db；4)對(duì)每個(gè)u，f(u)=max(da[u],db[u])。解析：樹的直徑端點(diǎn)a,b，任意點(diǎn)最遠(yuǎn)點(diǎn)必為a或b之一，O(n)。22.（10分）給定長為n的數(shù)組a，求有多少對(duì)(i,j)滿足i<j且a[i]?a[j]=i?j。n≤10?。答案：轉(zhuǎn)換式子得a[i]?i=a[j]?j，令b[i]=a[i]?i，問題化為統(tǒng)計(jì)b中相等元素對(duì)數(shù)。用哈希表/數(shù)組計(jì)數(shù)，遍歷b，每遇到值x，累加當(dāng)前count[x]，再count[x]++。時(shí)間O(n)，空間O(n)。23.（10分）有n個(gè)任務(wù)，每個(gè)任務(wù)有截止日d[i]和利潤p[i]，單線程，單位時(shí)間執(zhí)行一個(gè)任務(wù)。求可獲得的最大總利潤。n≤2×10?。答案：貪心+并查集（或堆）。步驟：1)按利潤降序排序；2)維護(hù)并查集，parent[i]表示≤i的最大空閑時(shí)間槽；3)對(duì)每個(gè)任務(wù)，find(min(d[i],n))，若>0，則安排在該槽，union(槽,槽?1)。解析：并查集路徑壓縮，近似O(nα(n))。五、綜合編程題（共20分）24.實(shí)現(xiàn)一個(gè)支持以下操作的數(shù)據(jù)結(jié)構(gòu)：1)insert(x)將x加入集合；2)delete(x)刪除一個(gè)x（保證存在）；3)getMedian()返回當(dāng)前集合的中位數(shù)（偶數(shù)時(shí)取下整）。操作總數(shù)q≤10?，x范圍?10?~10?。要求：單次操作均攤O(logq)。參考實(shí)現(xiàn)（C++17）：```cppinclude<bits/stdc++.h>usingnamespacestd;multiset<int>small,big;//small存≤中位數(shù)的半部分，big存>中位數(shù)的半部分voidbalance(){if(small.size()>big.size()+1){autoit=prev(small.end());big.insert(*it);small.erase(it);}elseif(big.size()>small.size()){autoit=big.begin();small.insert(*it);big.erase(it);}}voidinsert(intx){if(small.empty()||x<=*small.rbegin())small.insert(x);elsebig.insert(x);balance();}voiddelete_(intx){if(x<=*small.rbegin())small.erase(small.find(x));elsebig.erase(big.find(x));balance();}intgetMedian(){return*small.rbegin();}```解析：用兩個(gè)multiset維護(hù)平衡，保證small大小等于big或比其大1，中位數(shù)即small最大值。刪除時(shí)直接定位迭代器，均攤O(logq)。六、證明與推導(dǎo)題（共20分）25.（10分）證明：對(duì)任意無向圖，Prim算法與Kruskal算法得到的最小生成樹總權(quán)值相同。證明：1)二者均滿足割性質(zhì)：對(duì)于任意割(S,V?S)，權(quán)值最小的橫邊必屬于某棵最小生成樹。2)Prim每次向生成樹中加入連接(S,V?S)的最小邊，滿足割性質(zhì)；3)Kruskal按權(quán)值升序加邊，若加入邊e連接兩個(gè)連通塊，則e為當(dāng)前割的最小橫邊，亦滿足割性質(zhì)；4)由割性質(zhì)唯一性（權(quán)值互異時(shí)）或按字典序選擇（權(quán)值相同時(shí)），二者構(gòu)造的邊集總權(quán)值相同。綜上，兩算法均生成最小權(quán)值和。26.（10分）推導(dǎo)：在快速選擇算法中，若每次樞軸隨機(jī)選取，證明期望時(shí)間復(fù)雜度為O(n)。推導(dǎo)：設(shè)T(n)為對(duì)n個(gè)元素求第k小的期望時(shí)間。隨機(jī)樞軸將數(shù)組分為0~n?1部分，每部分概率1/n。則T(n)≤(1/n)Σ_{m=0}^{n?1}T(max(m,n?1?m))+O(n)令u(n)=max_{k}T(k)fork≤n，則u(n)≤(2/n)Σ_{m=?n/2?}^{n?1}u(m)+O(n)用數(shù)學(xué)歸納法，假設(shè)u(m)≤Cmform<n，則u(n)≤(2C/n)Σ_{m=?n/2?}^{n?1}m+O(n)≤(2C/n)((n?1)n/2?(?n/2??1)?n/2?/2)+O(n)≤(2C/n)(n2/2?n2/8)+O(n)=(2C/n)(3n2/8)+O(n)=3Cn/4+O(n)取C足夠大，使3C/4+O(1)≤C，則u(n)≤Cn。故T(n)=O(n)。七、算法優(yōu)化題（共20分）27.（10分）給定n×m的01矩陣，初始全0，執(zhí)行q次操作：1)將子矩陣(x1,y1,x2,y2)全部異或1；2)查詢點(diǎn)(x,y)的值。n,m,q≤5×10?。要求：每次操作O(1)，查詢O(1)。答案：二維差分+異或前綴。設(shè)diff[i][j]為以(i,j)為右下角的異或差分?jǐn)?shù)組，則操作1轉(zhuǎn)化為diff[x1][y1]^=1;diff[x1][y2+1]^=1;diff[x2+1][y1]^=1;diff[x2+1][y2+1]^=1;查詢(x,y)即為對(duì)diff做二維前綴異或：ans=diff[x][y]^diff[x?1][y]^diff[x][y?1]^diff[x?1][y?1];使用一維滾動(dòng)可省內(nèi)存，總時(shí)空O(nm+q)。28.（10分）給定長為n的數(shù)組a，求所有連續(xù)子數(shù)組的異或和之和，n≤10?。答案：按位貢獻(xiàn)。枚舉第k位(0~30)，統(tǒng)計(jì)有多少子數(shù)組異或和該位為1。設(shè)prefix[i]為前i項(xiàng)異或，則子數(shù)組[l,r]異或=prefix[r]^prefix[l?1]。第k位為1當(dāng)且僅當(dāng)prefix[r]與prefix[l?1]該位不同。遍歷prefix，維護(hù)該位0/1的計(jì)數(shù)c0,c1，每步累加c1（若當(dāng)前位0）或c0（若當(dāng)前位1），然后更新計(jì)數(shù)。該位貢獻(xiàn)=累加值×2??？倳r(shí)間O(nlogmaxa)。八、代碼閱讀與改錯(cuò)（共10分）29.閱讀以下求最長公共子序列的“優(yōu)化”代碼，指出兩處錯(cuò)誤并修正。```cppintn;stringa,b;cin>>n>>a>>b;vector<int>dp(n+1);for(inti=1;i<=n;++i)for(intj=1;j<=n;++j)if(a[i1]==b[j1])dp[j]=dp[j1]+1;elsedp[j]=max(dp[j1],dp[j]);cout<<dp[n]<<endl;```錯(cuò)誤1：內(nèi)層循環(huán)覆蓋dp[j]時(shí)使用了同一層舊值，導(dǎo)致串行依賴破壞。錯(cuò)誤2：未按行滾動(dòng)更新，應(yīng)逆序j。修正：```cppfor(inti=1;i<=n;++i){intprev=dp[0];for(intj=1;j<=n;++j){inttmp=dp[j];if(a[i1]==b[j1])dp[j]=prev+1;elsedp[j]=max(dp[j],dp[j1]);prev=tmp;}}```解析：prev保存上一行j?1值，逆序亦可，但正向需暫存。九、開放設(shè)計(jì)題（共20分）30.設(shè)計(jì)一個(gè)分布式一致性哈希環(huán)，支持動(dòng)態(tài)節(jié)點(diǎn)加入與退出，數(shù)據(jù)遷移量最小，且查詢路由跳數(shù)期望O(logn)。要求：1)給出數(shù)據(jù)結(jié)構(gòu)核心字段與接口；2)描述節(jié)點(diǎn)增刪的遷移策略；3)分析數(shù)據(jù)遷移量上限；4)給出偽代碼。答案：1)結(jié)構(gòu)：一致性哈希環(huán)[0,232)，使用紅黑樹存虛擬節(jié)點(diǎn)；每個(gè)物理節(jié)點(diǎn)node對(duì)應(yīng)k=O(logn)個(gè)虛擬節(jié)點(diǎn)，隨機(jī)哈希；維護(hù)有序映射tree<vnode,node*>；節(jié)點(diǎn)記錄真實(shí)數(shù)據(jù)段range[begin,end)。2)遷移策略：加入新節(jié)點(diǎn)N：計(jì)算k個(gè)虛擬點(diǎn)，對(duì)每相鄰舊區(qū)間[s,t)若落在N前，則拆分，將[t,N)段數(shù)據(jù)遷移到N；退出節(jié)點(diǎn)N：將N所有range合并，交給順時(shí)針下一活躍節(jié)點(diǎn)M，遷移數(shù)據(jù)。3)分析：虛擬節(jié)點(diǎn)數(shù)k=Θ(logn)，則任一物理節(jié)點(diǎn)退出影響的虛擬區(qū)間期望為O(1)，總數(shù)據(jù)遷移量期望O(1/k·總數(shù)據(jù))=O(數(shù)據(jù)量·logn/n)。4)偽代碼：```classConsistentHash{map<uint32_t,Node*>ring;intk=ceil(10*log(maxNodes));uint32_thash(stringkey){returnmurmur(key);}voidaddNode(Node*node){for(int