2026年程序员算法专项考核试题及答案

2026年程序员算法专项考核试题及答案一、单项选择题（每题2分，共20分）1.给定一个长度为n的整数数组，要求找出其中出现次数超过n/2的元素（假设一定存在）。以下算法中，时间复杂度最优且空间复杂度为O(1)的是A.哈希表统计频率B.排序后取中位数C.Boyer-Moore投票算法D.分治法求众数答案：C解析：Boyer-Moore投票算法只需一次遍历，维护候选元素与计数器，空间固定为两个变量，满足O(1)额外空间。2.对一棵包含n个节点的二叉搜索树进行中序遍历，得到的序列性质为A.严格递减B.非严格递增C.先序逆序D.层次序答案：B解析：BST中序遍历产生非严格递增序列，允许重复值时相等节点相邻。3.在32位无符号整数范围内，计算x的y次方对2³²取模，y可为0~2³²−1。下列做法不会溢出且效率最高的是A.快速幂+模乘B.自然溢出后截断C.任意精度大整数D.查表预计算答案：A解析：快速幂将指数二分，模乘保证中间结果不超32位，时间O(logy)。4.对一张稠密无向图求所有点对最短路径，顶点数V=500，边权非负。最优选择A.Dijkstra×V轮B.Bellman-Ford×V轮C.Floyd-WarshallD.0-1BFS答案：C解析：V=500时V³=1.25×10⁸，现代CPU可在1s内完成；Dijkstra×V用斐波那堆为O(V²logV)≈1.5×10⁵×log500≈2.7×10⁶，但实际常数大且实现复杂，Floyd更直接。5.以下关于并查集按秩合并与路径压缩的说法正确的是A.二者同时使用导致最坏复杂度退化到O(n)B.二者同时使用单次操作摊还O(α(n))C.路径压缩后不可再按秩合并D.按秩合并需额外保存节点深度答案：B解析：Tarjan证明二者结合后单次操作反阿克曼函数α(n)，近乎常数。6.对长度为n的随机数组做快速排序，枢轴总是选首元素，若数组已升序，则时间复杂度为A.Θ(nlogn)B.Θ(n²)C.Θ(n)D.Θ(logn)答案：B解析：最坏情况划分极度不平衡，退化为链式递归，次数1+2+…+n。7.给定两个长度均为n的已排序数组，求它们合并后的中位数，要求O(logn)时间。应使用A.二分查找+分治B.双指针归并C.快速选择D.堆答案：A解析：在两条数组上同时对第k小元素二分，每次排除k/2规模，复杂度O(logn)。8.若哈希表采用开放寻址+线性探测，装载因子α=0.9，则一次不成功查找的期望探查次数约为A.0.9B.5.5C.10D.50答案：B解析：公式(1+1/(1−α)²)/2≈(1+100)/2=50.5，但线性探测集群严重，实际经验值约5.5次。9.对一张有向无环图，拓扑排序使用Kahn算法（入度表+BFS）时，若队列改用栈，则输出序列A.仍为合法拓扑序B.必然逆字典序C.可能含环D.唯一确定答案：A解析：栈只是改变同一层节点选择顺序，最终仍是合法拓扑序，不引入环。10.在Manacher算法中，辅助数组P[i]表示A.以i为中心的最长回文半径（含中心）B.以i为起点的最长回文长度C.以i为终点的最长回文长度D.以i为中心的最长回文半径（不含中心）答案：A解析：P[i]记录回文半径，含中心字符，故总长度2P[i]−1。二、不定项选择题（每题3分，共15分，多选少选均不得分）11.关于跳表(SkipList)的正确描述有A.期望高度O(logn)B.支持插入、删除、查找平均O(logn)C.可替代平衡树实现有序映射D.最坏查询复杂度O(n)答案：ABCD解析：跳表随机层级，期望O(logn)，最坏退化为链；功能与平衡树等价。12.以下算法中，利用“分治+递归”思想的有A.归并排序B.快速傅里叶变换C.Karatsuba乘法D.堆排序答案：ABC解析：堆排序属选择排序的堆化优化，无分治递归拆分。13.对带负权边但无负环的图，可正确求单源最短路径的算法有A.Bellman-FordB.SPFAC.DijkstraD.拓扑排序+松弛答案：AB解析：Dijkstra无法处理负权；拓扑排序只适用于DAG。14.关于字符串匹配KMP算法，正确的有A.预处理next数组时间O(m)B.匹配阶段时间O(n)C.next数组仅与模式串有关D.可扩展到多模式匹配形成AC自动机答案：ABCD解析：KMP核心为next数组，AC自动机在其基础上加fail指针。15.以下数据结构支持O(logn)时间合并两个集合的有A.Treap（随机堆+BST）B.SplayTreeC.左偏堆（LeftistHeap）D.并查集答案：AC解析：Splay无保证合并log；并查集只支持近似常数合并，非log。三、填空题（每空3分，共15分）16.对n个元素的二叉堆执行k次删除堆顶操作，总时间复杂度为______。答案：O(klogn)解析：每次删除下沉高度⌊logn⌋，k次即klogn。17.采用莫队算法处理离线区间询问，若块长取______，则时间复杂度最优为O((n+q)√n)。答案：√n解析：块长√n时，左右指针移动总距离最小。18.对一张n点m边的带权无向图，使用Kruskal求最小生成树，并查集路径压缩后总时间复杂度为______。答案：O(mα(n))解析：排序边O(mlogm)，并查集m次操作O(mα(n))，m≥n−1。19.在字典树(Trie)中，若字符集大小为26，插入长度为L的字符串，最坏节点新建数为______。答案：L解析：每层若无公共前缀则需新建，最多L节点。20.对0~n−1的排列，使用ST表（SparseTable）做区间最值查询，预处理的时空复杂度分别为______和______。答案：O(nlogn)，O(nlogn)解析：ST表基于倍增，每层n个元素，共logn层。四、算法设计题（共30分）21.（10分）给定一棵n个节点的无根树，边权为1。定义f(u)为节点u到其最远节点的距离（树的高度）。要求对每个u求f(u)，n≤2×10⁵。答案：两次BFS/DFS。步骤：1)从任意节点s出发找最远点a；2)从a出发找最远点b，记录a到各点距离da；3)从b出发找最远点，记录距离db；4)对每个u，f(u)=max(da[u],db[u])。解析：树的直径端点a,b，任意点最远点必为a或b之一，O(n)。22.（10分）给定长为n的数组a，求有多少对(i,j)满足i<j且a[i]−a[j]=i−j。n≤10⁵。答案：转换式子得a[i]−i=a[j]−j，令b[i]=a[i]−i，问题化为统计b中相等元素对数。用哈希表/数组计数，遍历b，每遇到值x，累加当前count[x]，再count[x]++。时间O(n)，空间O(n)。23.（10分）有n个任务，每个任务有截止日d[i]和利润p[i]，单线程，单位时间执行一个任务。求可获得的最大总利润。n≤2×10⁵。答案：贪心+并查集（或堆）。步骤：1)按利润降序排序；2)维护并查集，parent[i]表示≤i的最大空闲时间槽；3)对每个任务，find(min(d[i],n))，若>0，则安排在该槽，union(槽,槽−1)。解析：并查集路径压缩，近似O(nα(n))。五、综合编程题（共20分）24.实现一个支持以下操作的数据结构：1)insert(x)将x加入集合；2)delete(x)删除一个x（保证存在）；3)getMedian()返回当前集合的中位数（偶数时取下整）。操作总数q≤10⁵，x范围−10⁹~10⁹。要求：单次操作均摊O(logq)。参考实现（C++17）：```cppinclude<bits/stdc++.h>usingnamespacestd;multiset<int>small,big;//small存≤中位数的半部分，big存>中位数的半部分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();}```解析：用两个multiset维护平衡，保证small大小等于big或比其大1，中位数即small最大值。删除时直接定位迭代器，均摊O(logq)。六、证明与推导题（共20分）25.（10分）证明：对任意无向图，Prim算法与Kruskal算法得到的最小生成树总权值相同。证明：1)二者均满足割性质：对于任意割(S,V−S)，权值最小的横边必属于某棵最小生成树。2)Prim每次向生成树中加入连接(S,V−S)的最小边，满足割性质；3)Kruskal按权值升序加边，若加入边e连接两个连通块，则e为当前割的最小横边，亦满足割性质；4)由割性质唯一性（权值互异时）或按字典序选择（权值相同时），二者构造的边集总权值相同。综上，两算法均生成最小权值和。26.（10分）推导：在快速选择算法中，若每次枢轴随机选取，证明期望时间复杂度为O(n)。推导：设T(n)为对n个元素求第k小的期望时间。随机枢轴将数组分为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)用数学归纳法，假设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)(n²/2−n²/8)+O(n)=(2C/n)(3n²/8)+O(n)=3Cn/4+O(n)取C足够大，使3C/4+O(1)≤C，则u(n)≤Cn。故T(n)=O(n)。七、算法优化题（共20分）27.（10分）给定n×m的01矩阵，初始全0，执行q次操作：1)将子矩阵(x1,y1,x2,y2)全部异或1；2)查询点(x,y)的值。n,m,q≤5×10⁵。要求：每次操作O(1)，查询O(1)。答案：二维差分+异或前缀。设diff[i][j]为以(i,j)为右下角的异或差分数组，则操作1转化为diff[x1][y1]^=1;diff[x1][y2+1]^=1;diff[x2+1][y1]^=1;diff[x2+1][y2+1]^=1;查询(x,y)即为对diff做二维前缀异或：ans=diff[x][y]^diff[x−1][y]^diff[x][y−1]^diff[x−1][y−1];使用一维滚动可省内存，总时空O(nm+q)。28.（10分）给定长为n的数组a，求所有连续子数组的异或和之和，n≤10⁶。答案：按位贡献。枚举第k位(0~30)，统计有多少子数组异或和该位为1。设prefix[i]为前i项异或，则子数组[l,r]异或=prefix[r]^prefix[l−1]。第k位为1当且仅当prefix[r]与prefix[l−1]该位不同。遍历prefix，维护该位0/1的计数c0,c1，每步累加c1（若当前位0）或c0（若当前位1），然后更新计数。该位贡献=累加值×2ᵏ。总时间O(nlogmaxa)。八、代码阅读与改错（共10分）29.阅读以下求最长公共子序列的“优化”代码，指出两处错误并修正。```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;```错误1：内层循环覆盖dp[j]时使用了同一层旧值，导致串行依赖破坏。错误2：未按行滚动更新，应逆序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值，逆序亦可，但正向需暂存。九、开放设计题（共20分）30.设计一个分布式一致性哈希环，支持动态节点加入与退出，数据迁移量最小，且查询路由跳数期望O(logn)。要求：1)给出数据结构核心字段与接口；2)描述节点增删的迁移策略；3)分析数据迁移量上限；4)给出伪代码。答案：1)结构：一致性哈希环[0,2³²)，使用红黑树存虚拟节点；每个物理节点node对应k=O(logn)个虚拟节点，随机哈希；维护有序映射tree<vnode,node*>；节点记录真实数据段range[begin,end)。2)迁移策略：加入新节点N：计算k个虚拟点，对每相邻旧区间[s,t)若落在N前，则拆分，将[t,N)段数据迁移到N；退出节点N：将N所有range合并，交给顺时针下一活跃节点M，迁移数据。3)分析：虚拟节点数k=Θ(logn)，则任一物理节点退出影响的虚拟区间期望为O(1)，总数据迁移量期望O(1/k·总数据)=O(数据量·logn/n)。4)伪代码：```classConsistentHash{map<uint32_t,Node*>ring;intk=ceil(10*log(maxNodes));uint32_thash(stringkey){returnmurmur(key);}voidaddNode(Node*node){for(int