2026年acm程序设计大赛试题及答案

2026年acm程序设计大赛试题及答案第一部分：单项选择题（本大题共15小题，每小题2分，共30分。在每小题给出的四个选项中，只有一项是符合题目要求的）

1.在算法分析中，若一个算法的时间复杂度为O()，当问题规模n增加到原来的2倍时，算法运行时间大约增加到原来的多少倍？

A.2倍

B.4倍

C.8倍

D.16倍

2.以下关于栈的数据结构描述中，错误的是：

A.栈遵循“后进先出”（LIFO）的原则。

B.栈的插入和删除操作只能在栈顶进行。

C.栈可以用数组或链表来实现。

D.栈在递归函数调用中不起作用。

3.在一棵二叉树中，第5层（根节点为第1层）上最多有多少个节点？

A.8

B.16

C.15

D.32

4.快速排序算法在平均情况下的时间复杂度是：

A.O(n)

B.O(nlogn)

C.O()

D.O(logn)

5.给定一个无向图，若该图是连通的且有n个顶点，则其生成树中边的数量为：

A.n

B.n−1

C.n+1

D.2n

6.以下哪种排序算法是不稳定的？

A.归并排序

B.冒泡排序

C.快速排序

D.插入排序

7.在哈希表中，解决冲突的常用方法不包括：

A.开放定址法

B.链地址法

C.再哈希法

D.广度优先搜索法

8.字符串"ababa"的KMP算法中（假设模式串为自身），部分匹配值（Next数组）的最后一个值通常是：

A.0

B.1

C.2

D.3

9.Dijkstra算法用于解决图论中的哪类问题？

A.最小生成树

B.单源最短路径

C.多源最短路径

D.关键路径

10.若有序表为[1,3,5,7,9,11,13,15]，使用二分查找算法查找值为7的元素，比较次数为：

A.2

B.3

C.4

D.5

11.以下关于堆的描述，正确的是：

A.最小堆中，任意节点的值都小于或等于其左右子节点的值。

B.堆一定是完全二叉树。

C.堆的插入操作时间复杂度为O(n)。

D.堆排序的空间复杂度为O(n)。

12.动态规划的核心思想不包括：

A.最优子结构

B.重叠子问题

C.贪心选择性质

D.状态转移方程

13.在网络流问题中，Ford-Fulkerson算法通过寻找什么来计算最大流？

A.最短路径

B.增广路径

C.欧拉回路

D.关键路径

14.两个n×n的矩阵相乘，常规算法的时间复杂度为：

A.O(n)

B.O()

C.O()

D.O(nlogn)

15.在十进制数2026对应的二进制表示中，末尾连续的0的个数是：

A.0

B.1

C.2

D.3

第二部分：多项选择题（本大题共5小题，每小题3分，共15分。在每小题给出的四个选项中，有多项是符合题目要求的。全部选对得3分，部分选对得1分，有选错得0分）

1.以下哪些算法属于分治法的典型应用？

A.归并排序

B.快速排序

C.二分查找

D.Prim算法

2.对于一个有V个顶点和E条边的连通无向图，使用邻接表存储时，以下说法正确的有：

A.空间复杂度为O(V+E)。

B.适合存储稀疏图。

C.判断两个顶点之间是否有边，时间复杂度一定是O(1)。

D.遍历所有边的时间复杂度为O(E)。

3.以下关于平衡二叉搜索树（AVL树）和红黑树的描述，正确的有：

A.它们都是为了保持二叉搜索树的平衡，避免退化为链表。

B.AVL树的平衡条件比红黑树更严格，查找效率通常更高。

C.红黑树的插入和删除操作通常比AVL树更快。

D.它们的最坏情况查找时间复杂度都是O(logn)。

4.NP完全问题包括以下哪些？

A.旅行商问题（TSP）的判定版本

B.背包问题的判定版本

C.最短路径问题

D.图着色问题

E.整数线性规划

5.在C++STL中，以下哪些容器不是关联容器？

A.vector

B.list

C.map

D.set

E.deque

第三部分：填空题（本大题共10空，每空2分，共20分）

1.在位运算中，表达式`x&(x1)`的常见作用是清除二进制数中最低位的______。

2.一个深度为h（根节点深度为0）的满二叉树，其节点总数为1，则其叶子节点个数为______。

3.在图的遍历中，______算法通常使用队列来实现，而______算法通常使用栈（或递归）来实现。

4.已知斐波那契数列F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)，计算F(5)的值为______。

5.在字符串匹配中，Boyer-Moore算法通常在预处理阶段通过______规则和好后缀规则来跳过不必要的比较。

6.若一个算法的空间复杂度为O(logn)，这通常意味着使用了______策略。

7.在计算几何中，判断点P在向量AB→的左侧、右侧还是共线，通常通过计算______的符号来确定。

8.对于n个元素进行全排列，其排列总数为______（用阶乘表示）。

9.在线段树中，查询区间[L,R]和的时间复杂度为______。

第四部分：简答题（本大题共4小题，每小题10分，共40分）

1.请简述贪心算法与动态规划的主要区别，并分别举出一个经典的应用实例。

2.已知一个无向图的邻接矩阵如下，请写出从顶点A出发，使用Prim算法生成最小生成树的过程中，依次被选入生成树的边。

邻接矩阵（权值，INF表示无穷大）：

ABCDE

A[0,4,INF,2,INF]

B[4,0,3,INF,5]

C[INF,3,0,6,1]

D[2,INF,6,0,3]

E[INF,5,1,3,0]

3.解释什么是“大O表示法”，并说明O(1)、O(logn)、O(n)、O(nlogn)在实际程序中的效率差异。

4.请描述快速排序的分区思想，并给出一个对数组`[3,1,4,1,5,9,2,6]`进行一趟快速排序（以最左元素3为基准）后的结果。

第五部分：综合应用题/编程题（本大题共5小题，共245分。要求写出核心算法思路、时间复杂度分析及完整代码实现）

1.（40分）子数组最大和

给定一个整数数组`nums`，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：输入:[-2,1,-3,4,-1,2,1,-5,4]，输出:6，解释:连续子数组[4,-1,2,1]的和最大，为6。

要求：时间复杂度O(n)。

2.（50分）合并区间

给定一个区间的集合，合并所有重叠的区间。

示例：输入:intervals=[[1,3],[2,6],[8,10],[15,12]]，输出:[[1,6],[8,10],[15,18]]。

解释:区间[1,3]和[2,6]重叠,将它们合并为[1,6]。

要求：先对区间按起始位置排序，然后线性扫描合并。

3.（50分）二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：二叉树:[3,9,20,null,null,15,7]，返回:[[3],[9,20],[15,7]]。

要求：使用队列实现BFS。

4.（50分）最长回文子串

给你一个字符串`s`，找到`s`中最长的回文子串。

示例：输入:"babad"，输出:"bab"或"aba"是有效的答案。

要求：可以使用动态规划或中心扩展法，时间复杂度不得高于O()。

5.（55分）岛屿数量

给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例：

输入：

11000

11000

00100

00011

输出：3

要求：使用DFS或BFS遍历网格。

---

###2026年ACM程序设计大赛试题及答案详细内容

####第一部分：单项选择题答案及解析

1.答案：B

解析：时间复杂度O()意味着运行时间T∝。当n变为2n时，新的运行时间∝(2n=4。因此是原来的4倍。

2.答案：D

解析：栈是“后进先出”的数据结构，A正确；操