2026年acm入门题库及答案

2026年acm入门题库及答案

一、单项选择题，(总共10题，每题2分)1.在C++中，若已声明inta=3,b=4;则表达式(a^b)<<1的值为A.14B.7C.12D.12.对长度为n的顺序表执行一次删除操作，最坏时间复杂度为A.O(1)B.O(logn)C.O(n)D.O(n²)3.下列排序算法中，稳定且平均时间复杂度为O(nlogn)的是A.快速排序B.堆排序C.归并排序D.希尔排序4.若一棵二叉树的前序遍历为ABDEC，中序遍历为DBEAC，则后序遍历为A.DEBCAB.DBEACC.ABDECD.DABEC5.在并查集路径压缩后，单次查找的均摊时间复杂度为A.O(1)B.O(logn)C.O(α(n))D.O(n)6.使用Dijkstra算法求单源最短路径时，要求边的权值A.必须为正B.必须非负C.可为负D.必须为整数7.若哈希表采用链地址法，负载因子α越大，则A.冲突概率降低B.查找长度一定减小C.平均查找长度增大D.与查找长度无关8.在KMP算法中，next数组的作用是A.存储主串信息B.存储模式串前缀后缀最长公共长度C.存储匹配成功位置D.存储字符出现次数9.对一张无向图进行深度优先搜索时，发现某条边指向已访问且非父节点，则该边为A.树边B.前向边C.后向边D.横叉边10.在32位系统中，若定义intp=(int)malloc(16);则sizeof(p)的值为A.2B.4C.8D.16二、填空题，(总共10题，每题2分)11.若循环队列存储在数组Q[0..m-1]中，队头指针front，队尾指针rear，则队列长度为________。12.对n个元素进行二分查找，最大比较次数为________。13.快速排序的最坏时间复杂度为________。14.一棵有n个节点的完全二叉树，其叶子节点数最少为________。15.若图的邻接矩阵为对称矩阵，则该图一定是________图。16.在堆中，若根节点存储在A[1]，则A[k]的右子节点下标为________。17.使用栈实现递归函数调用时，系统需要保存的信息包括参数、返回地址和________。18.给定intx=15;则x&(-x)的值为________。19.若并查集按秩合并，则树高最大不超过________。20.在C++中，若vector<int>v(10)调用默认构造函数，则v.capacity()至少为________。三、判断题，(总共10题，每题2分)21.冒泡排序在最好情况下的时间复杂度为O(n)。22.二叉搜索树的中序遍历结果一定升序。23.哈希表在平均情况下插入、删除、查找均为O(1)。24.若图采用邻接表存储，则求入度需要遍历整张表。25.在最大堆中，根节点一定是整个序列的最大值。26.深度优先搜索一定可以得到最短路径。27.对于任意无向图，其生成树边数等于顶点数。28.KMP算法的最坏时间复杂度为O(n+m)。29.使用longlong类型可以精确存储十进制小数0.1。30.在C++中，map的底层实现为哈希表。四、简答题，(总共4题，每题5分)31.简述贪心算法与动态规划的核心区别，并各举一例经典问题。32.说明拓扑排序的基本思想，并给出判断有向图是否有环的方法。33.描述链式前向星存储图的原理，并指出其相比邻接表的优势。34.解释快速幂算法如何利用二进制拆分将时间复杂度降至O(logn)。五、讨论题，(总共4题，每题5分)35.讨论在ACM竞赛中为何通常使用“scanf/printf”而非“cin/cout”，并给出加速cin/cout的两种常见手段。36.结合实例讨论在极端数据下递归深度过大引发栈溢出的解决方案。37.分析并查集“路径压缩”与“按秩合并”两种优化同时使用时对复杂度的影响。38.针对n≤1e5、m≤2e5的无向图，讨论如何在内存限制128MB下高效统计每个点的度并输出所有度为偶数的节点编号。答案与解析一、单项选择题1.A2.C3.C4.A5.C6.B7.C8.B9.C10.B二、填空题11.(rear-front+m)%m12.ceil(log2(n+1))或floor(log2n)+113.O(n²)14.ceil(n/2)15.无向16.2k+117.局部变量18.119.log2n20.10三、判断题21.√22.√23.√24.√25.√26.×27.×28.√29.×30.×四、简答题31.贪心每步局部最优且不回溯，如Huffman编码；动态规划记录子问题全局最优，如0-1背包。32.每次选入度为0的节点输出并删边；若最终输出数小于顶点数则存在环。33.用head数组存首边，edge结构体存to、w、next，遍历同链表；优势是连续内存、cache友好、边排序方便。34.将指数b拆成二进制，如b=13=1101₂，通过平方累积把a^1、a^2、a^4、a^8…乘到结果，循环次数等于b的二进制长度。五、讨论题35.scanf/printf解析格式串快；加速cin/cout可关同步：ios::sync_with_stdio(false)，并取消cin与cout绑定tie(0)。36.改用显式栈模拟递归，或改迭代版算法；对DFS可写手动栈结构保存当前遍历边指针。37.两种