2026年acm选拔试题及答案

2026年acm选拔试题及答案

一、单项选择题（总共10题，每题2分）1.快速排序算法的平均时间复杂度是（）A.O(n)B.O(nlogn)C.O(n²)D.O(logn)2.以下数据结构中，遵循“后进先出”原则的是（）A.队列B.栈C.链表D.数组3.Dijkstra算法主要用于解决（）问题A.图的深度优先遍历B.最短路径C.拓扑排序D.最小生成树4.二进制数1011对应的十进制数是（）A.9B.10C.11D.125.逻辑运算中，若A=true，B=false，则A∧B的结果是（）A.trueB.falseC.不确定D.16.二叉树的中序遍历顺序是（）A.根-左-右B.左-根-右C.左-右-根D.根-右-左7.动态规划算法的核心特性是（）A.贪心选择B.最优子结构和重叠子问题C.分治D.递归8.以下属于稳定排序算法的是（）A.快速排序B.选择排序C.冒泡排序D.堆排序9.若有指针p指向变量a，那么p表示（）A.p的地址B.a的地址C.a的值D.p的值10.集合A={1,2,3}，集合B={2,3,4}，则A∩B是（）A.{1,2,3,4}B.{2,3}C.{1,4}D.空集二、填空题（总共10题，每题2分）1.栈的进栈顺序是A、B、C、D，若出栈顺序是B、C、A、D，则中间的操作是：进A、进B、出B、进C、出C、____、出A、进D、出D。2.一棵二叉树有n个节点，其中度为2的节点数是k，则叶子节点数是____。3.冒泡排序算法的最坏时间复杂度是____。4.有n个顶点的无向完全图，其边数是____。5.动态规划求解斐波那契数列时，状态转移方程通常是dp[i]=____。6.递归函数求n的阶乘（n!）时，终止条件是当n=0或n=1时，返回____。7.哈希表解决冲突的常用方法之一是____（填“开放地址法”或“冒泡法”）。8.队列的基本操作原则是____（填“先进先出”或“后进先出”）。9.十六进制数A对应的二进制数是____。10.逻辑异或运算中，1XOR1的结果是____。三、判断题（总共10题，每题2分）1.时间复杂度O(n)比O(nlogn)更高。（）2.链表插入元素时不需要移动其他元素。（）3.栈可以用于检查括号是否匹配。（）4.深度优先遍历（DFS）通常使用队列实现。（）5.动态规划算法利用了重叠子问题的性质。（）6.选择排序是稳定的排序算法。（）7.空指针（NULL）表示不指向任何内存地址。（）8.集合A和集合B的并集是包含A和B中所有元素的集合。（）9.递归深度过深可能导致栈溢出错误。（）10.哈希表的查找时间复杂度始终是O(1)。（）四、简答题（总共4题，每题5分）1.简述快速排序算法的基本思想。2.简述图的拓扑排序的适用条件及基本步骤。3.简述动态规划算法的两个核心要素及其含义。4.简述链表和数组的主要优缺点对比。五、讨论题（总共4题，每题5分）1.讨论贪心算法与动态规划算法的适用场景及主要区别。2.讨论图论中深度优先遍历（DFS）和广度优先遍历（BFS）的应用场景差异。3.讨论在实际编程中选择排序算法的主要依据。4.讨论哈希表中开放地址法和链地址法两种冲突解决策略的优缺点。答案一、单项选择题1.B2.B3.B4.C5.B6.B7.B8.C9.C10.B二、填空题1.出A2.k+13.O(n²)4.n(n-1)/25.dp[i-1]+dp[i-2]6.17.开放地址法8.先进先出9.101010.0三、判断题1.错2.对3.对4.错5.对6.错7.对8.对9.对10.错四、简答题答案1.快速排序基于分治思想。首先选基准元素（如数组首元素或中间元素），通过一趟排序将数组分成两部分：左部分元素均≤基准，右部分均≥基准。然后递归地对左右子数组重复上述过程，直到子数组长度为1或0。最终通过不断分割和排序子数组，得到全局有序数组。2.拓扑排序适用于有向无环图（DAG）。步骤：①计算所有节点的入度；②将入度为0的节点入队；③取出队首节点，输出该节点，并遍历其邻接节点，将邻接节点入度减1；④若邻接节点入度变为0，入队；⑤重复③-④直到队空。若输出节点数等于总节点数，完成拓扑排序；否则图含环，无法拓扑排序。3.动态规划核心要素是最优子结构和重叠子问题。最优子结构指原问题的最优解包含子问题的最优解，即通过子问题最优解可构造原问题最优解。重叠子问题指不同子问题包含相同的子子问题，动态规划通过缓存子问题结果（如用数组存储），避免重复计算，提升效率。4.数组优点：随机访问快（O(1)通过索引访问），存储密度高；缺点：插入删除需移动元素（O(n)），长度固定（静态数组）。链表优点：插入删除无需移动元素（O(1)找到位置后），长度动态可变；缺点：随机访问慢（O(n)需遍历），存储密度低（节点需存指针）。五、讨论题答案1.贪心算法适用于具有贪心选择性质的问题（局部最优→全局最优），如霍夫曼编码、活动选择。动态规划适用于有最优子结构和重叠子问题的问题，如最长公共子序列、背包问题。区别：贪心自顶向下，每次选局部最优，无回溯；动态规划自底向上（或自顶向下带记忆化），缓存子问题解，需解决所有子问题。贪心不处理重叠子问题，动态规划通过缓存避免重复计算。2.DFS用栈实现，适合探索所有路径或深度结构，如迷宫求解、拓扑排序（递归）、连通分量查找。BFS用队列实现，适合找无权图最短路径、层次遍历（二叉树层序）、广域搜索（社交网络好友推荐）。DFS易陷入深度，空间复杂度O(深度)；BFS按层扩展，空间复杂度O(节点数)，但能保证最短路径。3.选择排序算法依据：①数据规模：小规模用插入排序（简单），大规模用快速/归并排序；②数据有序性：接近有序用插入/冒泡排序；③稳定性：需稳定用冒泡/插入/归并；④空间：空间紧张用堆排序（O(1)），不紧张用归并；⑤编程复杂度：简单场景用冒泡/插入，复杂用快速/归并。4.开