2026年acm竞赛试题及答案

2026年acm竞赛试题及答案

一、单项选择题（总共10题，每题2分）1.归并排序的时间复杂度为（）。A.O(n)B.O(nlogn)C.O(n²)D.O(n³)2.优先队列通常使用哪种数据结构实现？（）A.数组B.链表C.堆D.哈希表3.Dijkstra算法在以下哪种图中无法正确计算单源最短路径？（）A.无向图B.有向图C.带负权边的图D.带正权边的图4.强连通分量（SCC）的定义适用于（）。A.无向图B.有向图C.树结构D.所有图5.最长公共子序列（LCS）问题通常使用哪种算法解决？（）A.贪心算法B.动态规划C.分治算法D.回溯算法6.KMP算法的核心是利用（）避免重复匹配。A.哈希表B.后缀数组C.部分匹配表（next数组）D.前缀树7.若a≡bmodm，c≡dmodm，则以下结论错误的是（）。A.a+c≡b+dmodmB.a-c≡b-dmodmC.a×c≡b×dmodmD.a/c≡b/dmodm8.以下排序算法中，稳定的是（）。A.快速排序B.堆排序C.归并排序D.希尔排序9.活动选择问题的最优解通常通过（）获得。A.动态规划B.贪心算法C.回溯法D.分支限界法10.广度优先搜索（BFS）通常使用（）作为辅助数据结构。A.栈B.队列C.优先队列D.哈希表二、填空题（总共10题，每题2分）1.快速排序的平均时间复杂度是__________。2.Floyd-Warshall算法的时间复杂度是__________。3.数组[3,1,4,1,5,9,2,6]的最长递增子序列（LIS）长度是__________。4.Dijkstra算法中优先队列通常存储的是节点的__________。5.KMP算法中next数组的长度等于__________。6.0-1背包问题的状态转移方程通常表示为__________。7.拓扑排序仅适用于__________图。8.快速幂算法的时间复杂度是__________。9.并查集通过路径压缩优化后，查找操作的时间复杂度近似为__________。10.BFS遍历图时，节点的访问顺序满足__________特性。三、判断题（总共10题，每题2分）1.快速排序是稳定的排序算法。（）2.Dijkstra算法可以处理包含负权边的图。（）3.动态规划的状态转移方程必须覆盖所有可能的子问题。（）4.KMP算法的时间复杂度为O(n+m)（n为主串长度，m为模式串长度）。（）5.拓扑排序的结果是唯一的。（）6.堆排序的空间复杂度为O(1)。（）7.无权图中，BFS可以找到从起点到终点的最短路径。（）8.贪心算法总能得到问题的最优解。（）9.并查集仅能处理连通性问题。（）10.Floyd-Warshall算法无法处理包含负权环的图。（）四、简答题（总共4题，每题5分）1.简述KMP算法中next数组的作用。2.动态规划与分治算法的主要区别是什么？3.说明Dijkstra算法的核心步骤。4.如何判断一个图是否为二分图？五、讨论题（总共4题，每题5分）1.比较深度优先搜索（DFS）与广度优先搜索（BFS）的优缺点。2.讨论0-1背包问题的空间优化方法。3.分析快速排序在最坏情况下的时间复杂度及改进策略。4.如何用并查集解决动态连通性问题？答案一、单项选择题1-5：BCCBB6-10：CDCBB二、填空题1.O(nlogn)2.O(n³)3.44.当前最短距离5.模式串长度6.dp[j]=max(dp[j],dp[j-w[i]]+v[i])（逆序）7.有向无环（DAG）8.O(logn)9.O(1)（阿克曼函数反函数）10.先进先出（FIFO）三、判断题1-5：××√√×6-10：√√××√四、简答题1.next数组记录模式串每个位置的最长相等前缀后缀长度。匹配失败时，利用next数组跳过不必要的比较，将模式串右移，减少主串指针回溯，提升匹配效率。2.动态规划处理重叠子问题，通过存储子问题解避免重复计算；分治算法处理不重叠子问题，递归求解后合并结果，不存储中间解。3.步骤：初始化距离数组（起点为0，其余为无穷大）；使用优先队列选取当前距离最小的节点；遍历其邻接节点，更新最短距离；重复直至所有节点处理完毕。4.使用BFS或DFS着色，将节点染成两种颜色，若相邻节点颜色相同则不是二分图；若所有相邻节点颜色不同则是二分图。五、讨论题1.DFS空间复杂度低（栈实现），适合探索深层路径，但可能陷入无限循环；BFS按层遍历（队列实现），适合找最短路径，但空间复杂度高（存储每层节点）。2.0-1背包可通过一维数组优化空间：用dp[j]表示容量j的最大价值，逆序遍历容量（避免重复选同一物品），将二维状态压缩为一维，空间复杂度从O(nm)降为O(m)。3.最坏情况（如已排序数组）时间