2026年acm初赛试题及答案

2026年acm初赛试题及答案

一、单项选择题（每题2分，共20分）1.在C++中，若声明inta[10]={0};，则a[5]的值为A.随机值B.5C.0D.未定义2.对长度为n的已排序数组进行二分查找，最坏比较次数为A.nB.log₂nC.nlognD.√n3.下列排序算法中，平均时间复杂度为O(nlogn)且稳定的是A.快速排序B.归并排序C.堆排序D.希尔排序4.若图G用邻接矩阵存储，判断两点是否相邻的时间复杂度为A.O(1)B.O(n)C.O(m)D.O(n+m)5.在并查集路径压缩后，单次查找近似时间复杂度为A.O(1)B.O(logn)C.O(α(n))D.O(n)6.一棵有2026个节点的完全二叉树，其叶子节点数为A.1012B.1013C.1014D.10157.使用KMP算法进行模式匹配，预处理next数组的时间复杂度为A.O(n)B.O(m)C.O(n+m)D.O(n×m)8.在模998244353下，7的逆元为A.856870817B.142606337C.998244346D.不存在9.若网络流图中每条边容量为正整数，则最大流算法结束时，残量网络中A.不存在增广路B.源汇不连通C.所有边满流D.最小割为010.对一棵带权无向树求直径，最优算法时间复杂度为A.O(n²)B.O(nlogn)C.O(n)D.O(n√n)二、填空题（每题2分，共20分）11.若哈希表采用链地址法，装载因子为0.75，则平均成功查找长度理论上界为________。12.快速选择算法求第k小元素，最坏时间复杂度为________。13.对n个不同元素进行堆排序，交换次数的最坏上界为________。14.若G为n个顶点的有向无环图，则其拓扑排序方案数最多为________。15.在模运算下，(a×b)modm等价于[(amodm)×(bmodm)]mod________。16.后缀数组SA中，排名为i与i+1的后缀的最长公共前缀长度存储在________数组中。17.对长度为n的序列做ST表预处理，空间复杂度为________。18.若二分图左右部节点数均为n，最大匹配数为n，则该图存在________匹配。19.在Prim算法中，每次加入生成树的新边满足________性质。20.若FFT将多项式乘法复杂度降至O(nlogn)，则其单位根需满足________条件。三、判断题（每题2分，共20分，正确写“T”，错误写“F”）21.线段树区间更新必须采用延迟标记才能保持O(logn)复杂度。22.对任意无向图，BFS树深度不大于DFS树深度。23.若一个NP问题可在多项式时间归约到某问题A，则A必为NP-hard。24.在整数二分中，mid=(l+r)>>1可能因溢出导致死循环。25.使用高斯消元求解异或方程组时，行交换不影响解集。26.若图G存在欧拉回路，则其所有顶点度数必为偶数。27.在可持久化线段树中，每次更新都会复制O(n)个节点。28.对同一序列，不同稳定排序算法产生的逆序数一定相等。29.若凸包算法返回共线点，则Andrew算法需额外去重。30.网络流中，增广路的瓶颈容量等于该路径最小残量。四、简答题（每题5分，共20分）31.简述Dijkstra算法为何不能处理负权边，并给出反例。32.说明如何利用单调队列在O(n)时间内求滑动窗口最大值。33.给出并查集按秩合并与路径压缩同时使用时，最坏复杂度证明思路。34.描述利用扩展欧几里得求解线性同余方程ax≡b(modm)的步骤。五、讨论题（每题5分，共20分）35.讨论在10⁵节点、10⁶边的稀疏图上，求所有点对最短路径的可行方案及取舍。36.比较线段树、树状数组、分块在区间求和场景下的优劣，并给出适用条件。37.分析在字符串匹配中，哈希与自动机两种思路的时空权衡及冲突处理。38.探讨在动态图环境下维护最小生成树的挑战与现有算法思路。答案与解析一、单项选择题1.C2.B3.B4.A5.C6.B7.B8.A9.A10.C二、填空题11.1+α=1.7512.O(n²)13.nlogn14.n!15.m16.LCP17.O(nlogn)18.完美19.最小堆（或割）20.2的整数次幂且存在原根三、判断题21.T22.F23.F24.T25.T26.T27.F28.T29.T30.T四、简答题31.Dijkstra贪心选取当前最短路径，负权可能使已确定最短距离被后续更新。反例：三点0→1权3，0→2权4，1→2权-2，先选1后无法回退。32.维护双端队列存下标，保证队头为窗口最大；新元素从队尾弹出小于它的元素，保持单调降；队头出窗则弹出。每元素进出一次，O(n)。33.定义势函数Φ=Σrank[x]，路径压缩使节点直接指向根，秩不变，Φ下降；按秩合并使小树挂大树，秩增但次数受限；总操作摊还O(α(n))。34.先用exgcd求d=gcd(a,m)；若d∤b则无解；否则得ax₀+my₀=d，解x=x₀·(b/d)mod(m/d)，共d个解模m。五、讨论题35.FloydO(n³)超时；可多次DijkstraO(nmlogn)仍高；转而求中心性，用Johnson重权O(nm+n²logn)或分层采样，权衡精度与耗时。36.线段树支持任意区间操作O(logn)但常数大；树状数组只能可逆操作，常数小；分块O(√n)易实现，适合离线或更新少场景。37.哈希O(n+